How would you make an iterator as a key of hash_map?

Question

How would you make an iterator as a key of hash_map?
How would you define it under gcc, Microsoft c++?

E.g.

    vector<string>::iterator i;
    hash_map<vector<string>::iterator, int> h;

or

    list<string>::iterator i;
    hash_map<list<string>::iterator, int> h;

THis gives an error as iterators are not predefined as string and other types are...

Blockquote

**What!?** _[expletives deleted]_ I was typing an answer before. You have deleted that question. I therefore couldn't post my answer. Now you post the exact same question? I'm not answering again. **Next time, edit your question**? — sehe, Sep 29 '11 at 15:13
What is wrong with what you're doing? Is it giving error? (BTW, beware of vector's iterator; they get invalidated when the vector resizes itself). — Nawaz, Sep 29 '11 at 15:13
What results do you want if you have two different iterators referring to the same object? Should those compare equal or not? What about if you have two iterators referring to different objects with the same value? — Jerry Coffin, Sep 29 '11 at 15:17
@Nawaz: technically, they get invalidated on _reallocation_. However, the sematic problem might already arise, when the elements of the vectors are changed (e.g. swapped or shifted) — sehe, Sep 29 '11 at 15:18
@Nawaz: you know that. It is just more accurate to say on reallocation. Resizing doesn't necessarily change capacity. In fact, sometimes you have to go through hoops to reduce capacity. — sehe, Sep 29 '11 at 15:24
@Nawaz: when `reserve()` is called for more than the current capacity. So what's your point about `resize()`? ;-p — Steve Jessop, Sep 29 '11 at 15:29
@SteveJessop: I think `reserve()` only allocates the memory, and `resize()` allocates and initialize the memory by inserting newly default-created elements to the vector. — Nawaz, Sep 29 '11 at 15:31
two different iterators to the same object? How is that likely? If two iterators refer to the same object, they should be equal , I think — Aftershock, Sep 29 '11 at 15:32

score 4 · Answer 1 · edited May 23 '17 at 10:34

4

It is not a good idea to store vector's iterators of use them as keys in an associative container because vector's iterators are unstable, that is, they get invalidated on insert, remove, resize, push_back an so on (see Iterator invalidation rules).

Plain index is much safer in this regard:

hash_map<size_t, int> h;

You can convert an index to an iterator by simply:

size_t index = ...
std::vector<std::string> vec(...);
std::vector<std::string>::iterator i = vec.begin() + index;

And iterator back to index:

index = i - vec.begin();

edited May 23 '17 at 10:34

Community

1
1

answered Sep 29 '11 at 15:17

Maxim Egorushkin

131,725
17
180
271

1

http://stackoverflow.com/questions/6438086/iterator-invalidation-rules/6438087#6438087 – Maxim Egorushkin Sep 29 '11 at 15:28
@Aftershock: list's iterators are much more stable, they're only invalidated if the element they refer to is removed. Which is just as well, since you can't efficiently convert between indexes and iterators. The bad news is, how are you going to define a `hash` function on any kind of iterator? I don't think you can. – Steve Jessop Sep 29 '11 at 15:30
I mean how would you put a list iterator as a key? – Aftershock Sep 29 '11 at 15:35
@Aftershock: indeed, that is the problem. I think that what you want is out of the question even before we worry about how long the iterators are valid. – Steve Jessop Sep 29 '11 at 15:36

score 2 · Answer 2 · answered Sep 29 '11 at 15:16

2

FWIW:

using iterators in that way is NOT robust. Iterators get invalidates on certain operations that act on the container. Your hash_map keys will be invalidated from that moment.

I suggest using

hash_map<string, int> h;

or

vector<string*> i;
hash_map<string*, int> h;

or even

vector<shared_ptr<string> > i;
hash_map<shared_ptr<string>, int> h;

answered Sep 29 '11 at 15:16

sehe

374,641
47
450
633

Clear, not planning to change the data behind it. ( I did not downvote it) – Aftershock Sep 29 '11 at 15:19
**What?!** so now you downvote the answer, even after having me type it up twice. Go figure. Stackoverflow would veeeery quickly stop working this way. – sehe Sep 29 '11 at 15:20
@Aftershock: ok, sry about that. I'm very interested to know why somebody found it necessary to downvote it :) – sehe Sep 29 '11 at 15:25

score 1 · Accepted Answer · answered Sep 29 '11 at 15:37

1

If you know what you're doing (e.g. if the iterators are taken from a non-modifiable container), you can try to exploit the fact that &*it should be unique for each element:

typedef std::string my_container;
typedef my_container::const_iterator my_iterator;

struct IteratorHasher
{
  std::size_t operator()(const my_iterator & it) const
  {
    return hasher(&*it);
  }
private:
  std::hash<const char *> hasher;
};

Usage:

int main()
{
   std::unordered_map<my_iterator, int, IteratorHasher> mymap;

   std::string hello("hello");
   mymap[hello.begin()] = 3;
}

answered Sep 29 '11 at 15:37

Kerrek SB

464,522
92
875
1,084

Also included in "know what you're doing" is not to put end iterators into the unordered_map. – Steve Jessop Sep 29 '11 at 15:39
@Aftershock: You are not allowed to dereference any `end()` iterator. All of this is a very peculiar idea: If you're just talking about random-access containers, you'd be much better off making the *index* the key in the map rather than an iterator. – Kerrek SB Sep 29 '11 at 15:45

How would you make an iterator as a key of hash_map?

3 Answers3