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

Question

Я не могу решить, какой контейнер STL использовать в следующем случае:

1. Я хочу сохранить порядок вставки элементов
2. Элементы в контейнере должны быть уникальными.

Есть ли готовый контейнер для этого? Я не хочу использовать вектор, а затем выполнить std::find перед выполнением push_back каждый раз.

Answer 1

Boost MultiIndex должно быть в состоянии делать именно то, что вы хотите - вы можете просто использовать один последовательный индекс, чтобы получить требование «упорядочено по вставке», и либо hashed_unique, либо ordered_unique индекс для получения требования уникальности.

Answer 2

Возможно, для этого есть хороший встроенный способ, но один довольно простой способ - использовать как hash_map, так и список. Проверяйте hash_map перед каждой вставкой, затем вставляйте в обе. Возможно, вам захочется инкапсулировать это в классе.

Answer 3

Ни один стандартный контейнер библиотеки не дает вам то, что вы хотите напрямую. Я бы начал с std :: vector и написал свободную функцию для вставки, которая выполняет поиск и push_back для вас. Если этого достаточно, не иди дальше. Если у вас проблемы с производительностью, подумайте о более сложном решении.

Answer 4

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

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

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

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

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

Что-то вроде:

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

    ...
};

Answer 5

Ну, у меня когда-то была похожая ситуация. Одна вещь, которая пришла мне в голову: «Могу ли я использовать мульти-ключи»? Некоторое время я гуглил и нашел пример, используя 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;
}

НТН,

Answer 6

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

Answer 7

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

Answer 8

Реализуйте класс-оболочку над выбранным вами контейнером (например, list, vector, deque) и перепишите методы insert / push_back, чтобы убедиться, что вставленный элемент уникален перед вставкой элемента.

К сожалению, я не знаю ни одного контейнера STL, соответствующего вашим критериям.