std::map without sorted iteration

[jason.cipriani]

Is there something that is like an std::map (unique key -> value, fast
lookup, insert, and erase), but iterating through the elements goes in
the order you added them in, rather than sorted by key? I don't need
fast lookup of an element given an index, it only matters that the
elements are not reordered.

Thanks,
Jason

 

[Daniel Pitts]

Is there something that is like an std::map (unique key -> value, fast
lookup, insert, and erase), but iterating through the elements goes in
the order you added them in, rather than sorted by key? I don't need
fast lookup of an element given an index, it only matters that the
elements are not reordered.

Thanks,
Jason

Then why use a map at all? If all you care about is order, try std::vector.

If you care about uniqueness of keys then use a std::set to keep track
of keys and a std::vector to keep track of order.

 

[Barry]

Is there something that is like an std::map (unique key -> value, fast
lookup, insert, and erase), but iterating through the elements goes in
the order you added them in, rather than sorted by key? I don't need
fast lookup of an element given an index, it only matters that the
elements are not reordered.

Sounds like hash table is your need.
in C++, tr1::unordered_map

 

[Daniel Pitts]

Sounds like hash table is your need.
in C++, tr1::unordered_map

does unordered_map guarantee insertion-order iteration?

 

[jason.cipriani]

Then why use a map at all? If all you care about is order, try std::vector.

I need fast key-based look up of items as well as preserving the
original order. I also need fast insertion/removal of items.

I've decided to use a map<string,list<Item>::iterator>; that is I
maintain a linked list of items in the original insertion order, and
store the list nodes in a map for fast look up. The overhead of having
to remove items from the linked list when items are removed from the
map is negligible. This gives me what I want and seems to be working
fine.

Thanks,
Jason

 

[coal]

Is there something that is like an std::map (unique key -> value, fast
lookup, insert, and erase), but iterating through the elements goes in
the order you added them in, rather than sorted by key? I don't need
fast lookup of an element given an index, it only matters that the
elements are not reordered.

Probably Boost.MultiIndex
http://www.boost.org/doc/libs/1_35_0/libs/multi_index/doc/index.html

or Boost.Intrusive.

Brian Wood
Ebenezer Enterprises
www.webEbenezer.net

 

[Kai-Uwe Bux]

Is there something that is like an std::map (unique key -> value, fast
lookup, insert, and erase), but iterating through the elements goes in
the order you added them in, rather than sorted by key? I don't need
fast lookup of an element given an index, it only matters that the
elements are not reordered.

Maybe the post at

http://groups.google.com/group/comp.lang.c++/browse_frm/thread/145f963a6c125d1f/645ba08d10deb39d

contains an idea you can use.


Best

Kai-Uwe Bux

 

[Barry]

unordered_map does not guarantee that iteration order is the same as
insertion order.

I was aware of this, I thought the OP just wanted to avoid sorting to
improve performance ;-)

guaranteeing the iteration order practically needs to borrow extra
storage to maintain the insertion order, like LinkedHashMap in Java,
which uses double-linked list.

in other post, someone suggested Boost.MultiIndex, maybe adding an auto
incremented integral key to maintain the insertion order like the
database auto id.

 

[jason.cipriani]

I thought the OP just wanted to avoid sorting to
improve performance ;-)

I should have been more clear. Performance is important but
maintaining original insertion order is also a priority, I was looking
for a good balance.

guaranteeing the iteration order practically needs to borrow extra
storage to maintain the insertion order, like LinkedHashMap in Java,
which uses double-linked list.

In the end I've gone with a solution very much like that, similar to
what Kai-Uwe Bux posted:

Kai-Uwe Bux wrote elsethread (snipped):

http://groups.google.com/group/comp.lang.c++/browse_frm/thread/145f963a6c125d1f/645ba08d10deb39d

A map where the nodes are also in a linked list. It's solved my
problem nicely.

Thanks again,
Jason

 

[Barry]

I should have been more clear. Performance is important but
maintaining original insertion order is also a priority, I was looking
for a good balance.


In the end I've gone with a solution very much like that, similar to
what Kai-Uwe Bux posted:

Kai-Uwe Bux wrote elsethread (snipped):


A map where the nodes are also in a linked list. It's solved my
problem nicely.

Darn! How could I ignore post from Kai-Uwe Bux!