iterator as key for unordered_map

[abir]

Hi,
I has a vector<int> and i want to have some additional data
associated with a few locations in the vector.
i.e I want to have unordered_map<vector<int>::iterator, MyClass>
so that given a location, i can fetch the data from MyClass object.
Though the indices (or even pointers) can be stored in case of vector,
I want a general solution.

How can I have a hash function for vector<T>::iterator or any other
iterator ?

Thanks
abir

 

[Kai-Uwe Bux]

Hi,
I has a vector<int> and i want to have some additional data
associated with a few locations in the vector.
i.e I want to have unordered_map<vector<int>::iterator, MyClass>
so that given a location, i can fetch the data from MyClass object.
Though the indices (or even pointers) can be stored in case of vector,
I want a general solution.

Beware that iterators into a vector are invalidated when the vector
reallocates. That can cause some grief. This will not happen when you store
indices.

How can I have a hash function for vector<T>::iterator or any other
iterator ?

You can convert an iterator iter to a T* by &(*iter). For pointer types,
there is a hash in C++0X. (I am not sure if there is any formal requirement
that &(*iter) does not change as long as the underlying container remains
unchanged; however, I do not know of any STL implementation where objects
governed by a container move about without reason.)


Best

Kai-Uwe Bux

 

[abir]

Beware that iterators into a vector are invalidated when the vector
reallocates. That can cause some grief. This will not happen when you store
indices.


You can convert an iterator iter to a T* by &(*iter). For pointer types,
there is a hash in C++0X. (I am not sure if there is any formal requirement
that &(*iter) does not change as long as the underlying container remains
unchanged; however, I do not know of any STL implementation where objects
governed by a container move about without reason.)

Best

Kai-Uwe Bux

Thanks for reply.
In this case i enforced that iterators remain valid. Hopefully, thus
object remains in the same location in memory.So the solution proposed
works!
Iterator invalidation is the biggest problem I face, as i have many
cross referenced containers.
Many a times I need storable iterators (like Pix from Doug Lea )
which are generalized index rather than generalized pointer. So that,
they can remain valid as long as the element is available & its
relative position is fixed wrt container. Even some Pix can remain
valid as long as the element is available in container (irrespective
of whether some element is removed from either side of the pointee). I
have several of them handcrafted. I don't know why standard or boost
don't give such a library! Perhaps no one faces problem like me

thanks
abir

 

[Pascal J. Bourguignon]

Hi,
I has a vector<int> and i want to have some additional data
associated with a few locations in the vector.
i.e I want to have unordered_map<vector<int>::iterator, MyClass>
so that given a location, i can fetch the data from MyClass object.
Though the indices (or even pointers) can be stored in case of vector,
I want a general solution.

How can I have a hash function for vector<T>::iterator or any other
iterator ?

This is not advisable. Iterators are quite volatile, meaning that
they're invalidated by a lot of operations (eg. for vectors, by
insert or erase).

I would use instead a vector<pair<int,AdditionnalOptionalData*> >.

Of course, properly encapsulated in an abstraction, for example:

// pseudo-code:
class VectorOfIntWithOptionalData{
protected:
std::vector<std:air<int,AdditionnalOptionalData*> > data;
public:
// ...
int& operator[](size_t index) { return data[index].first; }
bool hasOptionalData(size_t index) { return data[index].second!=0; }
AdditionnalOptionalData* optionalData(size_t index) { return data[index].second; }
};

 

[abir]

Hi,
I has a vector<int> and i want to have some additional data
associated with a few locations in the vector.
i.e I want to have unordered_map<vector<int>::iterator, MyClass>
so that given a location, i can fetch the data from MyClass object.
Though the indices (or even pointers) can be stored in case of vector,
I want a general solution.

How can I have a hash function for vector<T>::iterator or any other
iterator ?

This is not advisable. Iterators are quite volatile, meaning that
they're invalidated by a lot of operations (eg. for vectors, by
insert or erase).

I would use instead a vector<pair<int,AdditionnalOptionalData*> >.

Of course, properly encapsulated in an abstraction, for example:

// pseudo-code:
class VectorOfIntWithOptionalData{
protected:
std::vector<std:air<int,AdditionnalOptionalData*> > data;
public:
// ...
int& operator[](size_t index) { return data[index].first; }
bool hasOptionalData(size_t index) { return data[index].second!=0; }
AdditionnalOptionalData* optionalData(size_t index) { return data[index].second; }

};

This is an alternative, but not a good solution for me. I am using
unordered_map because i don't want to store optional data pointer for
each element of vector. Vector size is huge (a few million) while the
optional data are small ( in hundreds only), they are some "special"
points in the vector.
The solution is of course using
unordered_map<size_t,AdditionalOptionalData> , where first parameter
is vector index rather than iterator. But, that is not a general, and
doesn't work with many containers.
Has someone implemented generalized index (Pix , from my previous
post) concept ? They are not volatile & very much storable (but need
to be intrusive for container which supports insert, erase &
push_front/ pop_front )

Thanks
abir

 

[James Kanze]

abir wrote:

(I am not sure if there is any formal requirement that
&(*iter) does not change as long as the underlying container
remains unchanged; however, I do not know of any STL
implementation where objects governed by a container move
about without reason.)

Each of the containers makes certain guarantees with regards to
the validity of pointers or references to its elements, just as
it does with regards to the validity of iterators. Thus, for
example, "An insertion at either end of the deque invalidates
all the iterators to the deque, but has no effect on the
validity of references to elements of the deque." (I cite this
one, because it is the only case I know of off hand where the
validity of references is different from that of iterators.)
Note that the result of *iter is a reference, so &*iter depends
only on the validity of this reference.

 

[W Karas]

Hi,
I has a vector<int> and i want to have some additional data
associated with a few locations in the vector.
i.e I want to have unordered_map<vector<int>::iterator, MyClass>
so that given a location, i can fetch the data from MyClass object.
Though the indices (or even pointers) can be stored in case of vector,
I want a general solution.

How can I have ahashfunction for vector<T>::iterator or any other
iterator ?

Thanks
abir

Another option you could consider would be the boost
pseudo-intrusive hash table template.