Which sorted STL container to use for fast insert and find with a special key?

Question

Hi,

I have some data with a key associated with each data item. The key is made of two parts: let's call them color and id. I want to iterate the container by color to speed up rendering and I also want to find items in the container by id alone.

I tried using std::map for this with a key

class MyKey {
public:
  int color;
  int id;
  bool operator<(...)
  bool operator==(...)
};

But I cannot provide a < operator that would keep the data sorted by color and at the same time allow map::find to work on id alone (i.e. no information about color).

I want both the insert and find operations to be fast (e.g. O(log(n))).

Any ideas what kind of container I could use to implement this?

Answer 1

Try Boost.BiMap, it's a map with 2 views.

Otherwise there is the more complicated Boost.MultiIndex.

Answer 2

Adapt the example here from Boost.Multi_index based on the following modifications:

typedef multi_index_container<
    MyKey,
    indexed_by<ordered_unique<identity<MyKey> >,
    ordered_non_unique<member<MyKey,int,&MyKey::color> >
  > 
> DataSet;

Answer 3

If you'd rather write your own than use Boost (dumb in my opinion) you can make a class that holds two maps. One to map color and the other to map ID. The map values would be pointers. You'd define insert and find operations for your new class. The insert would new a data struct and insert the pointer into both maps. The find operations would locate the item using either map as appropriate. For delete/remove operations it is a little trickier: you'd need to look up the data struct by a map, then remove it from both maps, probably by using the data in the data struct to find the other map entry.