473,325 Members | 2,870 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,325 software developers and data experts.

iterator as key for unordered_map

Hi,
I has a vector<intand 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
Jun 27 '08 #1
6 5755
abir wrote:
Hi,
I has a vector<intand 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
Jun 27 '08 #2
On Jun 24, 10:39 am, Kai-Uwe Bux <jkherci...@gmx.netwrote:
abir wrote:
Hi,
I has a vector<intand 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
Jun 27 '08 #3
abir <ab*******@gmail.comwrites:
Hi,
I has a vector<intand 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__
Jun 27 '08 #4
On Jun 24, 12:46 pm, p...@informatimago.com (Pascal J. Bourguignon)
wrote:
abir <abirba...@gmail.comwrites:
Hi,
I has a vector<intand 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
Jun 27 '08 #5
On Jun 24, 7:39 am, Kai-Uwe Bux <jkherci...@gmx.netwrote:
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:ja*********@gmail.com
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
Jun 27 '08 #6
On Jun 24, 1:14 am, abir <abirba...@gmail.comwrote:
Hi,
I has a vector<intand 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.
Jun 27 '08 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

38
by: Grant Edwards | last post by:
In an interview at http://acmqueue.com/modules.php?name=Content&pa=showpage&pid=273 Alan Kay said something I really liked, and I think it applies equally well to Python as well as the languages...
26
by: Michael Klatt | last post by:
I am trying to write an iterator for a std::set that allows the iterator target to be modified. Here is some relvant code: template <class Set> // Set is an instance of std::set<> class...
14
by: shawnk | last post by:
I searched the net to see if other developers have been looking for a writable iterator in C#. I found much discussion and thus this post. Currently (C# 2) you can not pass ref and out arguments...
4
by: Paulo Matos | last post by:
HI all, I'm using unordered_map from TR1. I have a table variable which is a private member of a template class: template<typename K, typename D, typename EQ> class FooClass { public:
0
by: mailforpr | last post by:
Hi. Let me introduce an iterator to you, the so-called "Abstract Iterator" I developed the other day. I actually have no idea if there's another "Abstract Iterator" out there, as I have never...
16
by: mailforpr | last post by:
How do I do that? The thing is, the only information I have about the iterator is the iterator itself. No container it is belonging to or anything. Like template<Iteratorvoid...
6
by: Rares Vernica | last post by:
Hi, I am using tr1/unordered_map in my code. My code compiled ok on g++ (GCC) 4.1.2 (Ubuntu 4.1.2-0ubuntu1). Now I need to compile my code on g++ (GCC) 4.0.3 (Ubuntu 4.0.3-1ubuntu5). I get...
5
by: abir | last post by:
Hi, I want a user defined key for tr1 unordered_map. My classes are, template<typename T> struct work{ int count; work(int count) : count(count){} }; template<typename W>
2
by: marek.vondrak | last post by:
Hi, I am wondering if there are any functional differences between SGI's hash_map and tr1's unordered_map. Can these two containers be interchanged? What would it take to switch from hash_map to...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.