2

Is there any data structure (C++03, or Boost) can keep the insert order and capable of lookup by key. I am currently doing it in this way:

struct Foo {
  vector<string> v;  // keep the key order by insert time
  map<string, string> m;  // <key, value>
};

Foo foo;
foo.v.push_back("key1");
foo.m["key1"] = "value1";
foo.v.push_back("key2");
foo.m["key2"] = "value2";

With this, I can keep the order I want in the vector object, and still be able to quickly lookup with the map object. The downside is I have to maintain both the vector object and map object, which smells.

Stan
  • 37,207
  • 50
  • 124
  • 185
  • You can use a vector with [std::find](http://www.cplusplus.com/reference/algorithm/find/). Lookup by key will not be efficient, though. – memo1288 Nov 21 '13 at 06:59
  • What's wrong with just using a structure like this that has a map and a vector? You can make a class that abstracts `insert`, `find` and `delete` away so that `insert` puts the k,v in the map and pushes on the vector, `delete` removes from the map and vector and `find` does a lookup on the map. I guess the biggest question is: what will you be using this structure for and why is the insert order important? – Vinay Nov 21 '13 at 07:05
  • possible duplicate of [A std::map that keep track of the order of insertion?](http://stackoverflow.com/questions/1098175/a-stdmap-that-keep-track-of-the-order-of-insertion) – Vinay Nov 21 '13 at 07:12

2 Answers2

2

A possible option is the Boost Multi-index containers library. I've used them in the past when I've had similar requirements. It takes a bit to get used to the template setup, but it works well afterwards.

edA-qa mort-ora-y
  • 30,295
  • 39
  • 137
  • 267
0

You can only have organization oriented by one property, so if you want lookup by time of insertion and you want lookup by string then you need two data structures

if you need to iterate by string order - then a map is fine - but if you will iterate by time and only lookup by string than a std::unordered_map will be faster

if you aren't doing many insertions/deletions then std::vector is fine - otherwise consider a std::list

also consider having one structure contain an iterator into the second so you can easily delete from both, most likely put the vector iterator in the unordered_map

list<string, string> insertOrder
unordered_map<string, list<string, string>::iterator> fastLookup

You can wrap this in a template<K,V> class so you can reuse it for other classes and keep the coordination in one place

Glenn Teitelbaum
  • 10,108
  • 3
  • 36
  • 80
  • I think this is wrong. You _can_ implement an order preserving hash. CRuby made hashes order preserving in 1.9 (though unfortunately not by specification, and not in the 64 bit implementation if I remember correctly). So @Stan's question remains open: has anybody published an order-preserving hash in C++? – Joachim W Nov 21 '13 at 07:06
  • @JoachimWuttke - I believe that this basically is the same thing, but uses classes from std. The order preserving hash has a hash that has pointers into the linked list as nodes – Glenn Teitelbaum Nov 21 '13 at 07:11