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;
}

have KeyIterator hold a pointer to the map, and have an iterator wrapper class to wrap the map's iterators, forwarding calls to ++, ==, --, etc. Should be relatively straightforward, although having it templated on only the key type will require some type erasure magic — Bwmat
– Bwmat, Commented Oct 5, 2011 at 20:46
Hey @John: I don't see any point wrapping into another class, seriously. Moreover, looking @ Mark Ransom's & Mooing Duck's answers, I don't see much improvement, still starts @ begin() and ends at end(). — Viet
– Viet, Commented Oct 5, 2011 at 23:15

Mooing Duck · Accepted Answer · 2011-10-05 20:54:52Z

3

#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.

answered Oct 5, 2011 at 20:54

Mooing Duck

67.6k19 gold badges107 silver badges169 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Mooing Duck Over a year ago

I just now noticed this compiled and ran on codepad and I didn't qualify std::string. What the?

sehe Over a year ago

because codepad inserts all kind of stuff, including using namespace std. See codepad.org/sKvDs2Et. Unfortunately I can't quite work out how I got the contents of prelude.h before. I don't know where it's located, and cpp can not be invoked as you can tell.

sehe Over a year ago

oh... Go ideone instead (also has C# and C++0x and many other nice bits. No boost of course :))

Cubbi Over a year ago

@sehe ideone has boost, but only in plain C++, not C++0x mode. And only header-only boost libraries can be used.

sehe Over a year ago

@Cubbi: thx for the notice. I'm absolutely sure I tried Spirit several times. I'll recheck next time

|

Mark Ransom · Accepted Answer · 2011-10-06 16:07:07Z

3

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; 
}

edited Oct 6, 2011 at 16:07

answered Oct 5, 2011 at 20:49

Mark Ransom

310k44 gold badges423 silver badges660 bronze badges

8 Comments

Mr. Boy Over a year ago

Well that's the iterator itself, but don't we need a container so we can loop over the contents from begin() to end()?

Mooing Duck Over a year ago

I wish the map iterator had typedefs for the types it points to... You mean like std::iterator_traits<iterator_type>::value_type?

Mark Ransom Over a year ago

@MooingDuck, thank you! I was expecting a typedef on the iterator type itself, forgot completely about iterator_traits (I've never used it).

Mark Ransom Over a year ago

@John, you just use KeyIterator(mymap.begin()) or KeyIterator(mymap.end()).

Mr. Boy Over a year ago

@MarkRansom - I updated my question, either I misunderstand your answer or the question was badly explained.

|

UncleBens · Accepted Answer · 2011-10-05 20:49:20Z

0

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.

answered Oct 5, 2011 at 20:49

UncleBens

41.4k6 gold badges62 silver badges90 bronze badges

Collectives™ on Stack Overflow

Creating a STL map key-iterator

3 Answers 3

6 Comments

8 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

6 Comments

8 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related