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

Paul Thomas 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.
xander345 said…
if you like c++ you can compile it online here: http://codecompiler.info/

32, 64 - windows & Linux - and more programming languages

Popular posts from this blog

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 two r…

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 c…

Want speed? Use constexpr meta-programming!

It's official: C++11 has two meta-programming languages embedded in it! One is based on templates and other one using constexpr. Templates have been extensively used for meta-programming in C++03. C++11 now gives you one more option of writing compile-time meta-programs using constexpr. The capabilities differ, however.

The meta-programming language that uses templates was discovered accidently and since then countless techniques have been developed. It is a pure functional language which allows you to manipulate compile-time integral literals and types but not floating point literals. Most people find the syntax of template meta-programming quite abominable because meta-functions must be implemented as structures and nested typedefs. Compile-time performance is also a pain point for this language feature.

The generalized constant expressions (constexpr for short) feature allows C++11 compiler to peek into the implementation of a function (even classes) and perform optimizations i…