Что в настоящее время наиболее широко используется набор множеств в C ++

Question

Я ищу набор контейнеров в C ++.Я хочу что-то, где я мог бы добавить элементы, но они не будут повторяться более одного раза, и поиск в этой коллекции будет O (1).Что является текущим дефакто-кросс-компиляторомЯ видел некоторые в boost (например, mpl), и они есть в будущих стандартах c ++, но что лучше использовать сейчас и здесь?

РЕДАКТИРОВАТЬ

Пример сохранения вектора в контейнере boost :: unordered_set.Так что для меня это, кажется, вполне соответствует моим потребностям, но у меня будет много данных, поэтому, если кто-то сразу увидит потенциальную ошибку, вы можете прокомментировать, что может пойти не так.Опять же, все элементы будут иметь отсортированный вектор без указателей.

vector<string> values1;
values1.push_back("aaa");
values1.push_back("bbb");
values1.push_back("ccc");

vector<string> values2;
values2.push_back("aa");
values2.push_back("bbb");
values2.push_back("ccc");

vector<string> values3;
values3.push_back("aaa");
values3.push_back("bbb");

vector<string> values4;
values4.push_back("aaa");
values4.push_back("bbb");
values4.push_back("ccc");
values4.push_back("ddd");

vector<string> values5;
values5.push_back("aaa");
values5.push_back("bbb");
values5.push_back("ccc");


vector<string> values6;
values6.push_back("aaa");
values6.push_back("bbb");
values6.push_back("ccc");
values6.push_back("ddd");

boost::unordered_set<vector<string> > collection;
collection.insert(values1); // 1
cout << collection.size() << endl;
collection.insert(values2); // 2
cout << collection.size() << endl;
collection.insert(values3); // 3
cout << collection.size() << endl;
collection.insert(values4); // 4
cout << collection.size() << endl;
collection.insert(values5); // 4
cout << collection.size() << endl;
collection.insert(values6); // 4
cout << collection.size() << endl;

Answer 1

Вы можете использовать std :: unordered_set , если у вас есть совместимый с C ++ 0x компилятор, который его поддерживает.

Если вы не находитесь в такой ситуации, перехваты доступны в Microsoft VC ++ как stdext :: hash_set или в общем случае с использованием boost :: unordered_set .Последний вариант - ваш лучший выбор для мобильности в настоящее время, ожидая более широкой доступности C ++ 0x.Как отмечается в комментариях @Nemo, также широко распространена поддержка std::tr1::unordered_set в качестве альтернативы использованию Boost.

[std::set будет O (log n), так как он основан надерево поиска.Чтобы получить O (1), вам нужно использовать контейнер на основе хеш-таблицы с должным учетом эффективной реализации хеш-функции для ваших объектов-членов.]

Answer 2

C ++ 03: boost::unordered_set

C ++ 0x: std::unordered_set

Более старые реализации (stdext::hash_set в VC ++) не являются кросс-компиляторами.

Примечание: boost::unordered_set интерфейс был повторно использован для std::unordered_set, поэтому миграция также проста

edit: интересные дополнения ==> если производительностьбеспокойство, и вам нужен быстрый тест на отсутствие, вам может быть интересно поискать Bloom Filters.

Answer 3

Вам нужно использовать набор, основанный на хеш-таблице, чтобы получить O (1) время поиска (т. Е. Постоянное время поиска), чтобы оно составляло std::unordered_set и / или boost::unordered_set. Текущие C ++ 03 std::set и std::multiset основаны на дереве RB и поэтому имеют время поиска O (log n).

Answer 4

Вы также можете взглянуть на класс HashSet из библиотек Poco C ++ .