8

is there, in the c++ "Standard Library", any "Associative" (i.e. "Key-Value") Container/Data Structure, that has the ability, to preserve order, by order of insertion?

I have seen several topics on this, however, it seems, most before C++11.

Some suggest using "boost::multi_index", but, if at all possible, I would "rather" use standard containers/structures.

I see that C++11 has several, apparently, "unordered" associative containers :link.

Are any of these, by some way, "configurable", such that they are only sorted by insertion order?

Thanks!

C

Improve this question
6
  • 2
    Just use an unordered_map and a vector together Commented Sep 21, 2013 at 5:29
  • 1
    Are you looking for std::vector< std::pair< K , V > >? Commented Sep 21, 2013 at 5:46
  • So You want equivalent of Java's LinkedHashMap? Commented Sep 21, 2013 at 6:30
  • @aaronman that works only if you do not modify map with functions that expect a normal map interface. Also removals in the middle will then be a lot slower, needing to shift entire vector. If neither is a concern, then sure. Commented Sep 21, 2013 at 9:16
  • 1
    I use boost::MultiIndex for this and it works well. Although in some cases I would like to not have the extra dependency. Commented Sep 21, 2013 at 12:12

3 Answers 3

Reset to default
4

No.

You are mixing linear access with random. Not very good bed fellows.

Just use both a vector/list (i.e. order of insertion) along with a map using an index into the former.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

They are very good bedfellows, very nice to have when, need this, and having such container is trivial implementation-wise, too. If C++ does not have one, I am a bit surprised. Example: docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html
@hyde - It is just linking two data structures together. Two - not one.
Hashmap already is a combination of several data structures internally, so I don't see what difference that makes... Insertion ordered hashmap still needs quite a bit of code, should be wrapped inside one class and must of course provide exactly same interface as normal unordered hashmap. Note that keeping insertion order does not affect algorithmic efficiency, unlike keeping sorted order.
1

No; such capability was apparently sacrificed in the name of performance.

The order of equivalent items is required to be preserved across operations including rehashes, but there's no way to specify the original order. You could, in theory, use std::rotate or the like to permute the objects into the desired order after each insertion. Obviously impractical, but it proves the lack of capability is a little arbitrary.

Your best bet is to keep the subsequences in inner containers. You may use an iterator adaptor to iterate over such a "deep" container as if it were a single sequence. Such a utility can probably be found in Boost.

Improve this answer

Comments

1

No. In unordered maps too, there are not stored according to the order of insertion.

You can use vector to keep the track of the key!

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.