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…

Understanding Fold Expressions

C++17 has an interesting new feature called fold expressions. Fold expressions offer a compact syntax to apply a binary operation to the elements of a parameter pack. Here’s an example. template <typename... Args> auto addall(Args... args) { return (... + args); } addall(1,2,3,4,5); // returns 15. This particular example is a unary left fold. It's equivalent to ((((1+2)+3)+4)+5). It reduces/folds the parameter pack of integers into a single integer by applying the binary operator successively. It's unary because it does not explicitly specify an init (a.k.a. identity) argument. So, let add it. template <typename... Args> auto addall(Args... args) { return (0 + ... + args); } addall(1,2,3,4,5); // returns 15. This version of addall is a binary left fold. The init argument is 0 and it's redundant (in this case). That's because this fold expression is equivalent to (((((0+1)+2)+3)+4)+5). Explicit identity elements will come in handy a little la…

Folding Monadic Functions

In the previous two blog posts (Understanding Fold Expressions and Folding Functions) we looked at the basic usage of C++17 fold expressions and how simple functions can be folded to create a composite one. We’ll continue our stride and see how "embellished" functions may be composed in fold expressions.

First, let me define what I mean by embellished functions. Instead of just returning a simple value, these functions are going to return a generic container of the desired value. The choice of container is very broad but not arbitrary. There are some constraints on the container and once you select a generic container, all functions must return values of the same container. Let's begin with std::vector.
// Hide the allocator template argument of std::vector. // It causes problems and is irrelevant here. template <class T> struct Vector : std::vector<T> {}; struct Continent { }; struct Country { }; struct State { }; struct City { }; auto get_countries…