Выбор контейнера STL с уникальностью и который сохраняет упорядочивание вставки

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.

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.

Вы можете сделать это:

• Создать обертку вокруг вашего класса элементов с двумя членами: ваш элемент и индекс. Давайте назовем это «InsertedElement». Индексом будет порядок вставки.

• Определите оператор сравнения для этого класса, который учитывает только ваш элемент, но не индекс. Это обеспечит уникальность элементов, помня их порядок вставки.

• Оберните std :: set и счетчик вставки в другом классе. Затем, когда вы хотите вставить новый элемент, либо:

• Он уже существует, ничего не делать.
• Он не вставляет его в карту, давая ему текущий максимальный индекс + 1.

Что-то например:

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

    ...
};

Как уже говорили другие, ни один контейнер STL не может сделать это. Мне нравится ответ Нила Баттерворта. Другой вариант - использовать как набор, так и вектор. Когда вы идете на вставку, проверьте, есть ли элемент в наборе. Если это так, вы не можете вставить, так как это нарушит ваши требования уникальности. Если это не так, добавьте его в набор, а затем вставьте его в вектор. Это легко реализовать и можно обернуть в один класс. Компромисс - увеличенные накладные расходы памяти. Но вы торгуете этим за увеличенное время вычислений, выполняя поиск по одному вектору. Все зависит от количества данных, с которыми вы работаете в проблемной области, а также от ваших ограничений времени и памяти (если есть).

Если у вас уже установлен буст, мне нравится эта опция. В противном случае, почему бы просто не использовать список или вектор и добавить проверку (find (k) == std :: npos) при вставке? Я полагаю, что он может быть довольно медленным в действительно очень большом списке, но в большинстве случаев он будет работать просто отлично.

Ну, у меня когда-то была похожая ситуация. Одна вещь, которая пришла мне в голову: «Могу ли я использовать мульти-ключи»? Некоторое время я гуглил и нашел пример, используя std :: set. Итак, если у вас нет доступа к форсированию (я рекомендую это, нет смысла заново изобретать колесо); Вы можете попробовать что-то вроде приведенного ниже примера. Я думаю, что вы можете использовать вторичный ключ в качестве позиции вставки (автоинкремент). Из примера, который я нашел в интернете; я приспособил это для своих нужд. Это модифицированная версия того же самого.

Cavaet: он использует макросы. Я знаю, что они злые в целом , но я думаю, что это нормально.

#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,