Choosing a STL container with uniqueness and which keeps insertion ordering

There might be a good built in way to do this, but one rather simple way is to use both a hash_map and a list. Check the hash_map before each insertion, then insert into both. You'll want to encapsulate this in a class, probably.

No standard library container gives you what you want directly. I would start with a std::vector and write a free function to do the insert which does the find and the push_back for you. If this suffices, go no further. If you have performance problems, think about a more complicated solution.

You could do this:

• Create a wrapper around your element class with two members: your element, and an index. Let's call it 'InsertedElement'. The index will be the insertion order.

• Define comparison operator for this class, which only takes into account your element, but not the index. This will ensure the uniqueness of elements, while remembering their insertion order.

• Wrap a std::set and an insertion counter in another class. Then, when you want to insert a new element, either:

• It already exists, nothing to do.
• It does not: insert it in the map while giving it the current max index + 1.

Something like:

class CMagicContainer { public: std::set<InsertedElement> collection; int indexGenerator; ... }; 

Implement a wrapper class over the container you choose (e.g. list, vector, deque), and rewrite the insertion/push_back methods to check that the inserted element is unique before inserting the element.

Unfortunately,I don't know any STL container to match your criteria.

As others have said, no single STL container can do this. I like Neil Butterworth's answer. Another option would be to use both a set and a vector. When you go to insert, check to see if the element is in the set. If it is, you can't insert as that would violate your uniqueness requirement. If it isn't, add it to the set and then insert it into the vector. This is easy to implement and can be wrapped into a single class. The tradeoff is increased memory overhead. But you trade that for increased computation time by doing the find yourself on the single vector. It all depends on how much data you are working with in your problem domain and your time and memory constraints (if any).

If you already have boost installed, I like that option. Otherwise, why not just use a list or vector and add a check (find(k) == std::npos) on insertion? I suppose it could get kind of slow on a really, reallly large list, but for most cases it would work just fine.

Well, i once had a similar situation. One thing that came in my mind was 'can i use multi-keys'? I googled for a while, and found a sample using std::set. So, if you do not have access to boost (i recommend it, there is no point re-inventing the wheel); you can try something like the below example. I think you can use the secondary key as the position of insertion (auto-increment). From the example that i found on internet; i tailored it for my needs. This one is a modified version of the same.

Cavaet: It is using macros. I know they are evil in general, but this use is o.k. i guess.

#include <set> #include <functional> #include <iostream> #include <algorithm> #include <iterator> #include <string> #define MULTIKEYDEF(NAME,TYPE) \ inline TYPE const & NAME() const { return d_##NAME; } \ inline void NAME(TYPE const & t) { d_##NAME = t; } \ TYPE d_##NAME; \ class T##NAME \ : public std::unary_function<Tmultikey*,bool> { \ private: \ TYPE d_compare; \ public: \ T##NAME(TYPE t) : d_compare(t) {} \ T##NAME(T##NAME const & self) \ : d_compare(self.d_compare) {} \ bool operator()(Tmultikey * mk) { \ return d_compare == mk->##NAME(); \ } \ inline TYPE const& name() const { return d_compare; } \ } class Tmultikey { public: // Actual keys // Can be accessed through d_primary and d_secondary, // or primary() and secondary() MULTIKEYDEF(primary , std::string); MULTIKEYDEF(secondary, unsigned int); // Mandatory bool operator < (Tmultikey const& mk) const { if(primary() < mk.primary()) return true; else if(primary() == mk.primary()) { return secondary() < mk.secondary(); } return false; } // Constructor Tmultikey(std::string p, unsigned int s) : d_primary(p), d_secondary(s) {} // Eraser for std::set template<typename Compare> static void erase(std::set<Tmultikey> & c, Compare op) { typename std::set<Tmultikey>::iterator pos = c.begin(); while(pos != c.end()) { if(op(&(*pos))) { c.erase(pos++); } else ++pos; } } // Eraser for std::set template<typename Compare> static std::set<Tmultikey>::iterator find_ex(std::set<Tmultikey> & c, Compare op) { typename std::set<Tmultikey>::iterator pos = c.begin(); while(pos != c.end()) { if(op(&(*pos))) { break; } else ++pos; } return pos; } }; int main(int argc, char* argv[]) { std::set<Tmultikey> mkset; mkset.insert(Tmultikey("1",5)); mkset.insert(Tmultikey("6",4)); mkset.insert(Tmultikey("3",7)); mkset.insert(Tmultikey("1",6)); std::set<Tmultikey>::iterator bg = mkset.begin(); for (;bg != mkset.end(); ++bg) { std::cout<<(*bg).primary()<<std::endl; } Tmultikey::erase(mkset,Tmultikey::Tsecondary(4)); //Tmultikey::erase(mkset,Tmultikey::Tprimary("1")); std::cout<<"After erase ....\n"; bg = mkset.begin(); for (;bg != mkset.end(); ++bg) { std::cout<<(*bg).primary()<<std::endl; } bg = mkset.find(Tmultikey("3",7)); if (bg != mkset.end()) { std::cout<<"Absolute Find:"<<(*bg).primary()<<" "<<(*bg).secondary()<<std::endl; } //bg = Tmultikey::find_ex(mkset,Tmultikey::Tprimary("1")); bg = Tmultikey::find_ex(mkset,Tmultikey::Tsecondary(5)); if (bg != mkset.end()) { std::cout<<"Partial Find:"<<(*bg).primary()<<" "<<(*bg).secondary()<<std::endl; } else { std::cout<<"Partial Find: FAILED\n"; } return 0; } 

HTH,