What Container Type(s) to use?

[LB]

I need a recommendation on how to implement a container type/what existing container type(s) to use for this situation: I need to have a list of objects that may or may not be the same, and each object needs to have, or be associated with, a name. No two objects in the list may have the same name, but I can't use a map because I need to maintain an exact, unsorted order.

Basically, is/are there already a container/containers that are designed for this, or will I just have to do something like a vector<pair<string, MyType> > and make sure no two have the same name when inserting/renaming?

EDIT: Essentially, I'm looking for something similar to an unsorted map container...

[Disch]

My first instinct would be to have a map<string,MyType>

Then have a separate vector< map<string,MyType>::iterator > to keep the unsorted order.

[LB]

Thanks, that'll work perfectly. :)

EDIT: What about invalidating iterators? What should I do then? Would it be better to use a vector<string> to maintain the order?

EDIT: I did some testing with this code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include <iostream> #include <map> using namespace std; int main() { map<int, int> test; test[725] = 1337; map<int, int>::iterator it = test.begin(); test[1337] = 725; map<int, int>::iterator er = test.find(1337); map<int, int>::reverse_iterator rt = test.rbegin(); //Naughty! cout << it->first << " = " << it->second << endl; cout << er->first << " = " << er->second << endl; cout << rt->first << " = " << rt->second << endl << endl; for(unsigned long i = 0; i < 100000; ++i) { if(i != 725 && i != 1337) { test[i] = i; } } cout << it->first << " = " << it->second << endl; cout << er->first << " = " << er->second << endl; cout << rt->first << " = " << rt->second << endl; cin.sync(); cin.ignore(); }

725 = 1337 1337 = 725 1337 = 725 725 = 1337 1337 = 725 99999 = 99999

And it's problem solved, again. I just have to make sure not to use reverse iterators with rbegin(), as apparently the reverse iterator can move, even when it shouldn't.

[m4ster r0shi]

Another option -> http://www.boost.org/doc/libs/1_46_1/libs/multi_index/doc/index.html

[LB]

Thanks, I'll look into that.

I would like to know, however, why my output differs like that. Why is the reverse iterator changing what it points to, whereas the normal iterators are not?

[Zhuge]

That's strange. I get the same output as you, but when pausing and checking in the debugger for VS2008 "rt" has a strange value. I'm not sure what the problem is.

[m4ster r0shi]

You could also do it the other way around -> Use a list<T> and a map<string, list<T>::iterator>.

A list iterator is more likely to remain valid (though, you can't be sure) as you operate on your container.

[1yR4jE8b]

boost::unordered_map does exactly what you want.

[m4ster r0shi]

I think he wants to maintain the order the objects are inserted in his container.

The boost way would be to use a multi-index container like this:

struct MyElement
{
    MyType val;
    string id;
};

typedef multi_index_container<
  MyElement,
  indexed_by<
    sequenced<>, // list-like indexing
    ordered_unique<member<MyElement, string, &MyElement::id> > // key->val indexing
  >
> my_container;