Choice of std:: Container

Hello all,

I'm trying to pin down the kind of container I need to select, and if there isn't one that works, to determine what I need to write my own that isn't too slow. Here are the requirements :

- Associative. I need it to work like a std::map in the way it can be used to return some value object based on a unique key object ( keys are unique in this scenario ).
- Unordered. I don't want the container ordering my pairs based on their keys.
- end() deletion, begin() insertion. I need to effectively be able to push() onto the end and pop() from the beginning - hence the unordered criterion above.

I came across unordered_map from C++11, but it's still ordering the objects by key, even when I provide a hint, unless I'm doing it wrong :

Code:

---

unordered_map <int, int> umap;

umap.insert(pair <int, int> (1, 123));
umap.insert(pair <int, int> (3, 345));
umap.insert(pair <int, int> (2, 234));

---

When I iterate from begin() to end(), my output is

Code:

---

123
234
345

---

I've also used

Code:

---

umap.insert(umap.end(), pair <int, int> (1, 123));

---

as a hint, to no avail.

Any suggestions would be hugely appreciated. Thank you !

(AFAIK) The point of std::unordered_map is that you do not get a reliable order of iteration, but I'm not sure about that.
(Giving more elements, I see that the results are not sorted w.r.t 'first' )

How fast do you need search to be ?
Unless ordered (/ stored down a tree), I think, the best is linear.
In that case, using std::deque<std::pair<int,int> > internally and making a class wrapping up your functionality would be okay.

Quote:

---

Here are the requirements

---

O_o

Why?

I can tell you how to get the behavior you require, but only if you tell me why and what you are trying to do.

I can't fathom a reality where you need those requirements; they make no sense when you put them together.

I'm reading "I want a dictionary that has no notion of order while still having some canonical notion of "beginning" and "ending"." and my brain is starting to reject all reality.

Quote:

---

The point of std::unordered_map is that you do not get a reliable order of iteration, but I'm not sue about that.

---

That's a side effect.

The "point" of the horrendously named facility is providing an associative container that has better complexity guarantees over `std::map' when used properly.

Soma

Quote:

---

Originally Posted by Korhedron

- Associative. I need it to work like a std::map in the way it can be used to return some value object based on a unique key object ( keys are unique in this scenario ).
- Unordered. I don't want the container ordering my pairs based on their keys.

---

It sounds like you mean "in order" (the order you add them in), like a vector, and not "unordered". This is going to be an issue with an associative key-value container, because, eg, the reason std::map orders the keys is not to conveniently sort them for the user; it's to make the associative look-ups efficient -- it is logarithmic, using an in-order tree, and not linear, going thru a list of unordered values. That makes a huge difference esp. if the map is large. And as phantomotap points out, the "unorderedness" of an unordered map just means the order cannot be predicted or relied upon by the user -- they almost certainly are kept in a specific order to maximize the efficiency of look-ups, but that order does not equate to a linear sort. So when you add an element to an unordered_map, it may end up anywhere -- but that spot is not random, it is according to the logic of the underlying implementation (which you should not try to decipher, predict, depend upon, etc).

If you need to maintain an order not conducive to look-ups, you can either abandon associative containers, use a vector, and just do linear look-ups yourself, or you could combine the two in some kind of class which stores the key-value pairs in a map, but when they are added, also pushes a pointer to the pair onto a vector. The iterator for the class iterates the vector, so the order is preserved, but the [] look-up uses the map. You may want to use a further pair or struct as the map value to keep track of the index in the vector for when an element is deleted.

If it is important to prevent duplicate keys, using just a vector will also require you to wrap it in a class and iterate every time something is added -- at that point you might as well just use the combined map/vector.

Quote:

---

sounds like you mean "in order"

---

It is already too late for that!

My brain was already bruised trying to escape from imaging a "use case" for undirected dictionaries.

Soma

Quote:

---

Originally Posted by phantomotap

imaging a "use case" for undirected dictionaries.

---

How about a map of (Author, Book) pairs? [Edit: (Book, Author) actually]
...you remove those you've finished reading
...and insert those you just bought
...and read them in the order they are bought

Quote:

---

How about a map of (Author, Book) pairs?

---

O_o

That's actually a very clear set of guidelines to form both a queue and a map.

That's a good case for doing what Mk27 said only using a queue (as you said) instead of a vector.

[Edit]
^_^

Has anyone noticed that post four keeps getting longer?
[/Edit]

Soma

Quote:

---

Originally Posted by phantomotap

Has anyone noticed that post four keeps getting longer?

---

It's forum OCD. I always re-read them to catch mistakes and think, "well you should also point out..."

That 1 hour edit limit turned out to be a blessing in disguise. I have so much extra free time now, I'm building a sun room over the front deck.