C++ Truths: using std::copy on std::map iterator pair

Sometimes it is useful to be able iterate over all the elements of a std::map using standard algorithms like std::copy(), std::count(), std::min_element(), std::max_element(). These standard functions do not work out of the box using std::map::iterator. For example, if you want to print all the elements of a map to standard output, you can’t use the following popular copy-ostream_iterator idiom.

std::map m;
std::copy (m.begin(), m.end(), std::ostream_iterator(std::cout, “\n”));
// does not compile

This is because value_type of the map::iterator is a pair. In other words, if iter is a map::iterator then *iter gives pair and not U. If we could somehow get hold of pair::second (i.e. type U) instead of pair all the above mentioned algorithms can be used out of the box.

The approach I took to solve this problem is to write an iterator adaptor that behaves likes any general bidirectional_iterator. In general, this approach allows map iterators to be used wherever Iterator-Pair idiom is useful. The code given below is kind of long but quite straight forward and idiomatic in nature.

#include

#include
#include
#include
#include #include

template
class StdMapIteratorAdaptor
/* To make the custom iterator behave like a standard iterator by exposing
required iterator_traits */
: public
std::iterator typename BiDirIter::value_type::second_type>
{
BiDirIter iter_;
public:

explicit StdMapIteratorAdaptor(BiDirIter const & iter = BiDirIter())
: iter_(iter) {}

bool operator == (StdMapIteratorAdaptor const & rhs) const {
return (iter_ == rhs.iter_);
}

bool operator != (StdMapIteratorAdaptor const & rhs) const {
return !(*this == rhs);
}

/* Return type is const to make it work with map::const_iterator */
typename BiDirIter::value_type::second_type const & operator * () {
return iter_->second;
}

typename BiDirIter::value_type::second_type const & operator * () const {
return iter_->second;
}

typename BiDirIter::value_type::second_type const * operator -> () const {
return &(iter_->second);
}

// Pre-increment
StdMapIteratorAdaptor & operator ++ () {
++iter_;
return *this;
}

// Post-increment
const StdMapIteratorAdaptor operator ++ (int) {
StdMapIteratorAdaptor temp (iter_);
++iter_;
return temp;
}

// Pre-decrement
StdMapIteratorAdaptor & operator — () {
–iter_;
return *this;
}

// Post-decrement
const StdMapIteratorAdaptor operator — (int) {
StdMapIteratorAdaptor temp (iter_);
–iter_;
return temp;
}
};

/* An helper function to save some typing of tedious nested C++ types
It is very similar to std::make_pair function */
template
StdMapIteratorAdaptor
make_map_iterator_adaptor (BiDirIter const & iter)
{
return StdMapIteratorAdaptor (iter);
}

int main(void)
{
typedef std::map StrIntMap;
StrIntMap months;

months[“january”] = 31;
months[“february”] = 28;
months[“march”] = 31;
months[“april”] = 30;
months[“may”] = 31;
months[“june”] = 30;
months[“july”] = 31;
months[“august”] = 31;
months[“september”] = 30;
months[“october”] = 31;
months[“november”] = 30;
months[“december”] = 31;

StrIntMap const & m = months;

StdMapIteratorAdaptor begin (m.begin());
StdMapIteratorAdaptor end (m.end());
std::copy(begin, end, std::ostream_iterator (std::cout, ” “));
std::cout << std::endl; std::list l(make_map_iterator_adaptor(m.begin()),
make_map_iterator_adaptor(m.end()));

std::copy (l.begin(), l.end(), std::ostream_iterator (std::cout, ” “));
std::cout << std::endl;
std::copy (make_map_iterator_adaptor(months.begin()),
make_map_iterator_adaptor(months.end()),
std::ostream_iterator (std::cout, ” “));

return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *