Creating a STL map key-iterator

Question

Often, you have a map like map<string,X> where the key is the name of the mapped value, and you need an API which lets consumers see all the names... to populate a GUI list-box for example. You can build a vector and return it as an API call but this is rather inefficient. You could just return a reference to the map, but then the values are also accessible and you might not want that.

So how could you write a compliant class, KeyIterator, which wraps map and provides standard iterator access to the keys in that map.

e.g:

map<string,X> m= ...
KeyIterator<string> ki(m);
for(KeyIterator<string>::iterator it=ki.begin();it!=ki.end();++it)
 cout << *it;

KeyIterator should be lightweight so you can return it from a method with virtually no overhead.

edit: I'm not sure I explained perfectly, let me give a better use-case (semi-pseudo):

class PersonManager
{
 private:
  map<string,Person> people;
 public:
  //this version has to iterate the map, build a new structure and return a copy
  vector<string> getNamesStandard();

  //this version returns a lightweight container which can be iterated
  //and directly wraps the map, allowing access to the keys
  KeyIterator<string> getNames();
};

void PrintNames(PersonManager &pm)
{
 KeyIterator<string> names = pm.getNames();
 for(KeyIterator<string>::iterator it=names.begin();it!=names.end();++it)
  cout << *it << endl;
}

Answer 1

template<typename iterator_type>
class KeyIterator
{
    iterator_type iterator;
public:
    typedef typename std::iterator_traits<iterator_type>::value_type::first_type value_type;
    KeyIterator(iterator_type i) : iterator(i) {}
    value_type operator*() { return iterator->first; }
    KeyIterator & operator++() { ++iterator; return *this; }
    bool operator!=(const KeyIterator & right) const { return iterator != right.iterator; }
    // ...
};

Edit: After seeing your edit I realize this isn't exactly what you asked for. You confused me by calling your class a KeyIterator, a more appropriate name would be KeyContainer. You won't be able to template it just on the key type, since it's going to have to contain some kind of reference to the map; you'll need the full definition of the map.

Your request overcomplicates the problem because you must define two different types, KeyIterator and KeyIterator::iterator.

Here's your sample code using my class:

class PersonManager
{
private:
    map<string,Person> people;
public:
    //this version has to iterate the map, build a new structure and return a copy 
    vector<string> getNamesStandard(); 

    //this version returns a lightweight container which can be iterated 
    //and directly wraps the map, allowing access to the keys 
    KeyIterator<map<string,Person>::iterator> getNamesBegin(); 
    KeyIterator<map<string,Person>::iterator> getNamesEnd(); 
}; 

void PrintNames(PersonManager &pm) 
{ 
    KeyIterator<map<string,Person>::iterator> it = pm.getNamesBegin();
    KeyIterator<map<string,Person>::iterator> end = pm.getNamesEnd();
    for(it; it!=end; ++it) 
        cout << *it << endl; 
}

Answer 2

#include <map>
#include <string>
#include <iterator>

template <class map>
class KeyIterator { 
    typename map::const_iterator iter_;
public:
    KeyIterator() {}
    KeyIterator(typename map::iterator iter) :iter_(iter) {}
    KeyIterator(typename map::const_iterator iter) :iter_(iter) {}
    KeyIterator(const KeyIterator& b) :iter_(b.iter_) {}
    KeyIterator& operator=(const KeyIterator& b) {iter_ = b.iter_; return *this;}
    KeyIterator& operator++() {++iter_; return *this;}
    KeyIterator operator++(int) {return KeyIterator(iter_++);}
    const typename map::key_type& operator*() {return iter_->first;}
    bool operator==(const KeyIterator& b) {return iter_==b.iter_;}
    bool operator!=(const KeyIterator& b) {return iter_!=b.iter_;}
};

int main() {
    std::map<std::string,int> m;
    KeyIterator<std::map<std::string,int> > ki;
    for(ki=m.begin(); ki!=m.end(); ++ki)
        cout << *ki;
}

http://codepad.org/4wxFGGNV
Doesn't get much more lightweight than that. However, it requires the iterator to be templated on the map type, instead of the key type, which means you have to give out some implementation details if you were attempting to hide internals.

Answer 3

I guess the main problem is that you want only one template argument instead of two: KeyIterator<string> instead of KeyIterator<string, X>.

To achieve that, you might need a technique called type erasure. This will involve dynamic allocation and virtual method calls, though.

If it is the latter, you can just wrap a map<string, X>::const_iterator, make dereferencing return a reference to the key and provide constructor(s) that take map's iterators.