Why doesn’t std::map provide key_iterator and value_iterator?

Question

I am working in a C++03 environment, and applying a function to every key of a map is a lot of code:

const std::map<X,Y>::const_iterator end = m_map.end();
for (std::map<X,Y>::const_iterator element = m_map.begin(); element != end; ++element)
{
   func( element->first );
}

If a key_iterator existed, the same code could take advantage of std::for_each:

std::for_each( m_map.key_begin(), m_map.key_end(), &func );

So why isn’t it provided? And is there a way to adapt the first pattern to the second one?

You can init both `it` and `end` inside the loop header like `for(iterator it=c.begin(), end=c.end(); ...)` in order to reduce the "lot of code" a bit. That said, providing the iterators you suggest would also make me wonder if they provide a different order or number of elements than the plain iterators, which could in turn make code less clear. — Ulrich Eckhardt, Nov 17 '13 at 11:32
The answer to "why doesn't the C++ standard library have X" is nearly always "they didn't get around to adding it". For something to be added to the library, someone has to write a proposal for it, the committee has to discuss it and approve it, and that just didn't happen. It's not there because no one put it there. — jalf, Nov 17 '13 at 11:35
Random links after a quick search: http://stackoverflow.com/questions/1443793/iterate-keys-in-a-c-map, http://stackoverflow.com/questions/7667343/creating-a-stl-map-key-iterator, http://stackoverflow.com/questions/110157/how-to-retrieve-all-keys-or-values-from-a-stdmap, http://stackoverflow.com/questions/259240/iterator-adapter-to-iterate-just-the-values-in-a-map — gx_, Nov 17 '13 at 11:35
look at `boost::transform_iterator`. it's about 3 lines of code to slice of the key or value of the `std::pair`. if you are patient enough I'll paste the code when I have access to it. — Alexander Oh, Nov 17 '13 at 12:02
[boost::adaptors::map_keys](http://www.boost.org/doc/libs/release/libs/range/doc/html/range/reference/adaptors/reference/map_keys.html) is even fewer lines of code. — Cubbi, Nov 17 '13 at 15:19

score 5 · Accepted Answer · answered Nov 17 '13 at 11:30

Yes, it is a silly shortcoming. But it's easily rectified: you can write your own generic key_iterator class which can be constructed from the map (pair) iterator. I've done it, it's only a few lines of code, and it's then trivial to make value_iterator too.

score 0 · Answer 2 · answered Nov 17 '13 at 11:42

There is no need for std::map<K, V> to provide iterators for the keys and/or the values: such an iterator can easily be built based on the existing iterator(s). Well, it isn't as easy as it should/could be but it is certainly doable. I know that Boost has a library of iterator adapters.

The real question could be: why doesn't the standard C++ library provide iterator adapters to project iterators? The short answer is in my opinion: because, in general, you don't want to modify the iterator to choose the property accessed! You rather want to project or, more general, transform the accessed value but still keep the same notion of position. Formulated different, I think it is necessary to separate the notion of positioning (i.e., advancing iterator and testing whether their position is valid) from accessing properties at a given position. The approach I envision is would look like this:

std::for_each(m_map.key_pm(), m_map.begin(), m_map.end(), &func);

or, if you know the underlying structure obtained from the map's iterator is a std::pair<K const, V> (as is the case for std::map<K, V> but not necessarily for other containers similar to associative containers; e.g., a associative container based on a b-tree would benefit from splitting the key and the value into separate entities):

std::for_each(_1st, m_map.begin(), m_map.end(), &func);

My STL 2.0 page is an [incomplete] write-up with a bit more details on how I think the standard C++ library algorithms should be improved, including the above separation of iterators into positioning (cursors) and property access (property maps).

score 0 · Answer 3 · answered Nov 17 '13 at 12:11

So why isn’t it provided?

I don't know.

And is there a way to adapt the first pattern to the second one?

Alternatively to making a “key iterator” (cf. my comment and other answers), you can write a small wrapper around func, e.g.:

class FuncOnFirst { // (maybe find a better name)
public:
    void operator()(std::map<X,Y>::value_type const& e) const { func(e.first); }
};

then use:

std::for_each( m_map.begin(), m_map.end(), FuncOnFirst() );

Slightly more generic wrapper:

class FuncOnFirst { // (maybe find a better name)
public:
    template<typename T, typename U>
    void operator()(std::pair<T, U> const& p) const { func(p.first); }
};

marko · Answer 4 · 2013-11-17T14:00:21.957

There is no need for key_iterator or value_iterator as value_type of a std::map is a std::pair<const X, Y>, and this is what function (or functor) called by for_each() will operate on. There is no performance gain to be had from individual iterators as the pair is aggregated in the underlying node in the binary tree used by the map.

Accessing the key and value through a std::pair is hardly strenuous.

#include <iostream>
#include <map>

typedef std::map<unsigned, unsigned> Map;

void F(const Map::value_type &v)
{
    std::cout << "Key: " << v.first << " Value: " << v.second << std::endl;
}

int main(int argc, const char * argv[])
{
    Map map;

    map.insert(std::make_pair(10, 20));
    map.insert(std::make_pair(43, 10));
    map.insert(std::make_pair(5, 55));

    std::for_each(map.begin(), map.end(), F);

    return 0;
}

Which gives the output:

Key: 5 Value: 55
Key: 10 Value: 20
Key: 43 Value: 10
Program ended with exit code: 0

Why doesn’t std::map provide key_iterator and value_iterator?

4 Answers4