Iterator for C++11 map values (simple and transparent)

Question

I am looking for a simple way to create an iterator for the values of a map in C++11.

This method should be simple and transparent: simple in that it should be easy to implement, and transparent in that the client should not know the values come from a map, not a set.

This question has been asked several times before. Many of these questions predate C++11 and use boost, which I do not want to use. Some are not simple, John Ahlgren's solution here, http://john-ahlgren.blogspot.com/2013/10/how-to-iterate-over-values-of-stdmap.html , for example requires a page of code to write a custom iterator.

The others are not transparent, i.e., clearly one can write:

map<string,foo> mymap;
for (auto it=mymap.begin();it!=mymap.end();++it){
  Foo val= it->second;
  ...
 }

However, I do not want to do this because I do not want the client to have to know of the data representation.

The problem comes up as follows.

I have a bunch of objects uniquely indexed with a long "key". Sometimes I want to manipulate sets of these objects. Other times I want to retrieve an object given its key.

I cannot use the "set" class directly for several reasons, chief among which is that it does not store mutable instances, and these instances must be mutable (except, obviously, for the key).

So, I have decided to store all my objects in a giant global hashtable:

map<long,Foo> all_the_objects;

I then do not work with set<Foo> at all. Instead I work with set<long> and use an adaptor to simulate a set of Foo, i.e.,

class SetOfFoo{
  private: set<long> theKeys;
  public:
    void insert(const & Foo);
    size_t size() return theKeys.size();
    bool is_member(const & Foo)
      {return theKeys.find(Foo.key)
          != theKeys.end;}
    Foo & insert(const & Foo val){
       long key=val.key;
       all_the_objects[key]=val;
       return all_the_objects[key];
     }
    ...::iterator begin() {???}
}

In other words, the client of the SetOfFoo class does not know or need to know that SetOfFoo is implemented as as set of keys.

I also cannot just make a Vector myself in the adaptor class, because one cannot store references in C++ collections.

Is it really impossible to make a simple, transparent way to iterate over map<> values? I find it hard to believe, as this is a very common need and is trivial to do in every language I have seen that has hashtables. I just don't understand how this can be hard.

Answer 1

it's pretty trivial.

Here's an extremely simplistic version that minimally solves the problem for a map of ints to strings. You can either rewrite for the types you want or templatise it as you wish.

#include <map>
#include <iostream>
#include <iterator>
#include <string>
#include <algorithm>

struct map_value_iterator : public std::map<int, std::string>::const_iterator
{
    map_value_iterator(std::map<int, std::string>::const_iterator src)
    : std::map<int, std::string>::const_iterator(std::move(src))
    {

    }

    // override the indirection operator
    const std::string& operator*() const {
        return std::map<int, std::string>::const_iterator::operator*().second;
    }
};


using namespace std;


int main()
{
    map<int, string> myMap { {1, "Hello" }, { 2, "World" } };

    copy(map_value_iterator(begin(myMap)), map_value_iterator(end(myMap)), ostream_iterator<string>(cout , " "));
    cout << endl;

    return 0;
}

Program output:

Compiling the source code....
$g++ -std=c++11 main.cpp -o demo -lm -pthread -lgmpxx -lgmp -lreadline 2>&1

Executing the program....
$demo 
Hello World 

Answer 2

You can do something like the following (C++98):

#include <iostream>
#include <map>
#include <string>
#include <algorithm>

#include "util/pair_iterator.hpp"

template<class T> inline T const& constify(T& t) { return t; }

int main()
{
    using namespace std;
    using namespace util;

    map<int, string> m;
    m[0] = "alice";
    m[1] = "bob";
    m[2] = "carol";
    m[3] = "dave";
    m[4] = "eve";

    copy(
          over_second(m.begin())
        , over_second(m.end())
        , ostream_iterator<string>(cout, "\n")
        );

    copy(
          over_first(m.begin())
        , over_first(m.end())
        , ostream_iterator<int>(cout, "\n")
        );

    // const iterators check

    copy(
          over_second(constify(m).begin())
        , over_second(constify(m).end())
        , ostream_iterator<string>(cout, "\n")
        );

    copy(
          over_first(constify(m).begin())
        , over_first(constify(m).end())
        , ostream_iterator<int>(cout, "\n")
        );
}

Here is an implementation:

// util/pair_iterator.hpp
#include <iterator>

#include "boost/iterator/transform_iterator.hpp"
#include "boost/type_traits/remove_reference.hpp"
#include "boost/type_traits/is_const.hpp"
#include "boost/mpl/if.hpp"

namespace util {

namespace aux {

template<class T> struct dereference_type
    : boost::remove_reference<typename std::iterator_traits<T>::reference>
{
};

template<class PairT>
struct first_extracter
{
    typedef typename boost::mpl::if_<
          boost::is_const<PairT>
        , typename PairT::first_type const
        , typename PairT::first_type
        >::type result_type;
    result_type& operator()(PairT& p) const { return p.first; }
};

template<class PairT>
struct second_extracter
{
    typedef typename boost::mpl::if_<
          boost::is_const<PairT>
        , typename PairT::second_type const
        , typename PairT::second_type
        >::type result_type;
    result_type& operator()(PairT& p) const { return p.second; }
};

} // namespace aux {

template<class IteratorT>
inline
boost::transform_iterator<aux::first_extracter<typename aux::dereference_type<IteratorT>::type>, IteratorT>
over_first(IteratorT const& i)
{
    typedef aux::first_extracter<typename aux::dereference_type<IteratorT>::type> extracter;
    return boost::transform_iterator<extracter, IteratorT>(i, extracter());
}

template<class IteratorT>
inline
boost::transform_iterator<aux::second_extracter<typename aux::dereference_type<IteratorT>::type>, IteratorT>
over_second(IteratorT const& i)
{
    typedef aux::second_extracter<typename aux::dereference_type<IteratorT>::type> extracter;
    return boost::transform_iterator<extracter, IteratorT>(i, extracter());
}

} // namespace util