Skip to main content

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 <std::string, int> m;
std::copy (m.begin(), m.end(), std::ostream_iterator<int>(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<T,U>::iterator then *iter gives pair<T,U> and not U. If we could somehow get hold of pair::second (i.e. type U) instead of pair<T,U> 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 <map>
#include <iostream>
#include <algorithm>
#include <string>
#include <list>
#include <iterator>

template <class BiDirIter>
class StdMapIteratorAdaptor
/* To make the custom iterator behave like a standard iterator by exposing
required iterator_traits */
: public
std::iterator <std::bidirectional_iterator_tag,
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 <class BiDirIter>
StdMapIteratorAdaptor <BiDirIter>
make_map_iterator_adaptor (BiDirIter const & iter)
{
return StdMapIteratorAdaptor<BiDirIter> (iter);
}

int main(void)
{
typedef std::map <std::string, int> 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 <StrIntMap::const_iterator> begin (m.begin());
StdMapIteratorAdaptor <StrIntMap::const_iterator> end (m.end());
std::copy(begin, end, std::ostream_iterator <int> (std::cout, " "));
std::cout << std::endl;

std::list<int> l(make_map_iterator_adaptor(m.begin()),
make_map_iterator_adaptor(m.end()));

std::copy (l.begin(), l.end(), std::ostream_iterator <int> (std::cout, " "));
std::cout << std::endl;
std::copy (make_map_iterator_adaptor(months.begin()),
make_map_iterator_adaptor(months.end()),
std::ostream_iterator <int> (std::cout, " "));

return 0;
}

Comments

Anonymous said…
boost::iterator library can help you trim that code right down to the essentials (well, almost - this is C++ after all). My preference would be to use transform_iterator in this case - something like (not tested!):

boost::make_transform_iterator(m.begin(), boost::bind(&StrIntMap::value_type::second, _1)
samm said…
You can also use std::tr1::bind if you don't want to use boost::iterator. The following code should work, though it's untested.

for_each(map.begin(), map.end(), bind(&printf, "%d\n", bind(&Map::value_type::second, _1)));
Sumant said…
That makes sense. Thanks guys!
Peter_APIIT said…
Why need to inherit from iterator and not Bidirectional iterator ?

public std::iterator std::bidirectional_iterator_tag

Is this mean we inherit properties from Bidirectional because tag shows that ?

What is best approach to code map iterator ?
Sumant said…
Inheriting from the iterator class is the standard way of implementing iterators in C++. Earlier, non-standard way of implementing iterators was to inherit from bidirectional_iterator or forward_iterator and so on. That way has been replaced by the iterator class template. Please see the definition section of bidirectional_iterator here. More information on iterator class template is here.

The tag only identifies the concept modeled by the user-defined iterator. In the example shown, bidirection_iterator_tag identifies that the StdMapIteratorAdapter is a model of BidirectionalIterator concept. By doing so, we are also reusing iterator_traits

As far the best way is concerned, I'll certainly take a look at boost::iterator library as suggested by Paul.

Popular Content

Unit Testing C++ Templates and Mock Injection Using Traits

Unit testing your template code comes up from time to time. (You test your templates, right?) Some templates are easy to test. No others. Sometimes it's not clear how to about injecting mock code into the template code that's under test. I've seen several reasons why code injection becomes challenging. Here I've outlined some examples below with roughly increasing code injection difficulty. Template accepts a type argument and an object of the same type by reference in constructor Template accepts a type argument. Makes a copy of the constructor argument or simply does not take one Template accepts a type argument and instantiates multiple interrelated templates without virtual functions Lets start with the easy ones. Template accepts a type argument and an object of the same type by reference in constructor This one appears straight-forward because the unit test simply instantiates the template under test with a mock type. Some assertion might be tested in

Multi-dimensional arrays in C++11

What new can be said about multi-dimensional arrays in C++? As it turns out, quite a bit! With the advent of C++11, we get new standard library class std::array. We also get new language features, such as template aliases and variadic templates. So I'll talk about interesting ways in which they come together. It all started with a simple question of how to define a multi-dimensional std::array. It is a great example of deceptively simple things. Are the following the two arrays identical except that one is native and the other one is std::array? int native[3][4]; std::array<std::array<int, 3>, 4> arr; No! They are not. In fact, arr is more like an int[4][3]. Note the difference in the array subscripts. The native array is an array of 3 elements where every element is itself an array of 4 integers. 3 rows and 4 columns. If you want a std::array with the same layout, what you really need is: std::array<std::array<int, 4>, 3> arr; That's quite annoying for

Covariance and Contravariance in C++ Standard Library

Covariance and Contravariance are concepts that come up often as you go deeper into generic programming. While designing a language that supports parametric polymorphism (e.g., templates in C++, generics in Java, C#), the language designer has a choice between Invariance, Covariance, and Contravariance when dealing with generic types. C++'s choice is "invariance". Let's look at an example. struct Vehicle {}; struct Car : Vehicle {}; std::vector<Vehicle *> vehicles; std::vector<Car *> cars; vehicles = cars; // Does not compile The above program does not compile because C++ templates are invariant. Of course, each time a C++ template is instantiated, the compiler creates a brand new type that uniquely represents that instantiation. Any other type to the same template creates another unique type that has nothing to do with the earlier one. Any two unrelated user-defined types in C++ can't be assigned to each-other by default. You have to provide a