Choosing a STL container

Question

I am unable to decide which STL container to use in the following case:

(1). I want to preserve the order of insertion of the elements

(2). The elements in the container have to be unique.

Is there any readymade container available for this? I don't want to use a vector and then perform a std::find before doing a push_back every time.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

Boost MultiIndex Should be able to do exactly what you want - you can just use one sequenced index to get the "ordered by insertion order" requirement, and either a hashed_unique or ordered_unique index to get the uniqueness requirement.

Answer 5

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).

Answer 6

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.

Answer 7

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;

    ...
};

Answer 8

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,