0

when creating an iterator of a vector, the iterator itself is a pointer to the values held by the vector. therefore *iterator is actually the value held by the vector.

so I have two questions:

  1. when using an iterator on a map, what is the iterator actually? I mean, what is it's inner implementation? is it like a struct that holds different data members?

  2. If I want to implement my own iterator, which holds several data members, what am I actually returning when creating an iterator?

greg phillip
  • 151
  • 1
  • 7
  • I don't understand your second question at all. Can you rephrase it? You should usually ask one question per question though. – eerorika Sep 01 '14 at 11:35

4 Answers4

0
  1. Depends on implementation. Usually, std::map is implemented as a balanced binary search tree. In that case, the iterator would likely point to a node in the tree.
eerorika
  • 232,697
  • 12
  • 197
  • 326
0
  1. The iterator of a std::map is a structure that references the key-value-pairs saved in your map. The standard iterator which you get with i.e begin() or end() is a bidirectional iterator. This means that your can call ++i and --i operators on the iterator object to move for/backward between the items saved in your map.
  2. Why do you want to implement your own iterator? Maybe creating a class or struct saving it to a std::vector<T> will do what you want?! you can access the iterator by std::vector<T>::iterator. If you really want to implement your own iterator, you should ask yourself the question if it should work for your own data structures as a test, or if you want to be compatible with i.e. std data structures. If its the latter, you should derive from a iterator implementation and modify it the way of your needs. Look at this answer as well.
Community
  • 1
  • 1
lifeOfPI
  • 318
  • 1
  • 8
0

The iterator itself is a pointer to the values held by the vector.

Vector iterator is not a pointer to value but a class with operator * implemented, which returns the value held by the container and pointed out by your iterator. In case of map you can access key and value using first and second fields:

map<string, int> wheelMap;
wheelMap["Car"] = 4;

map<string, int>::iterator itWheel = wheelMap.begin();
cout << itWheel ->first << ":" << itWheel ->second << endl;  //This will print: Car:4

Map iterator has also other operators implemented: +, ++, -, --, ->, ==, !=. Additionally vector has also the operator [] implemented to get the values by index.

kappa
  • 627
  • 2
  • 10
  • 21
  • 1
    It really depends on the implementation and iterator type if the vector iterators are just pointer to the element or a class. – JarkkoL Sep 01 '14 at 12:00
0

I implemented std::map-like container as red-black-tree (like often sited being used for std::map implementation) and only thing the iterator implementation needs (both const and non-const versions) is pointer to the tree node. Each tree node contains pointers to the two children and parent (plus color bit) which is enough to traverse the tree to either direction. In general it depends on the container & iterator types (and implementation) though what kind of data is needed to implement its functionality. E.g. my deque iterators have pointer to the container and index of the element, but it's really implementation specific how the iterators are implemented and what data they need.

JarkkoL
  • 1,898
  • 11
  • 17