iterator as key for unordered_map

Discussion in 'C++' started by abir, Jun 24, 2008.

  1. abir

    abir Guest

    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
    abir, Jun 24, 2008
    #1
    1. Advertising

  2. abir

    Kai-Uwe Bux Guest

    abir wrote:

    > 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
    Kai-Uwe Bux, Jun 24, 2008
    #2
    1. Advertising

  3. abir

    abir Guest

    On Jun 24, 10:39 am, Kai-Uwe Bux <> wrote:
    > abir wrote:
    > > 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


    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
    abir, Jun 24, 2008
    #3
  4. abir <> writes:

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


    --
    __Pascal Bourguignon__
    Pascal J. Bourguignon, Jun 24, 2008
    #4
  5. abir

    abir Guest

    On Jun 24, 12:46 pm, (Pascal J. Bourguignon)
    wrote:
    > abir <> writes:
    > > 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::pair<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; }
    >
    > };
    >
    > --
    > __Pascal Bourguignon__


    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
    abir, Jun 24, 2008
    #5
  6. abir

    James Kanze Guest

    On Jun 24, 7:39 am, Kai-Uwe Bux <> wrote:
    > 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.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Jun 24, 2008
    #6
  7. abir

    W Karas Guest

    On Jun 24, 1:14 am, abir <> wrote:
    > 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.
    W Karas, Jun 26, 2008
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Paulo Matos

    Template problem with unordered_map

    Paulo Matos, Aug 3, 2006, in forum: C++
    Replies:
    4
    Views:
    455
    Paulo Matos
    Aug 3, 2006
  2. Rares Vernica

    error with tr1 unordered_map iterator

    Rares Vernica, Feb 24, 2007, in forum: C++
    Replies:
    6
    Views:
    1,803
  3. abir
    Replies:
    3
    Views:
    1,134
  4. Replies:
    2
    Views:
    6,616
  5. Replies:
    3
    Views:
    1,814
Loading...

Share This Page