C ++ std :: map или std :: set - эффективно вставлять дубликаты

У меня есть куча данных, полная дубликатов, и я хочу удалить дубликаты. Вы знаете, например [1, 1, 3, 5, 5, 5, 7] становится [1, 3, 5, 7].

Похоже, я могу использовать либо std :: map, либо std :: set, чтобы справиться с этим. Однако я не уверен, быстрее ли (а) просто вставить все значения в контейнер или (б) проверить, существуют ли они уже в контейнере, и вставлять только в том случае, если их нет - вставки очень эффективны? Даже если есть способ получше ... не могли бы вы предложить быстрый способ сделать это?

Другой вопрос - если данные, которые я храню в них, не такие тривиальные, как целые числа, а вместо этого являются настраиваемым классом, как std :: map удается правильно хранить (хэшировать?) Данные для быстрого доступа с помощью оператора [ ]?


c++ performance stdmap stdset
person Gigi    schedule 10.10.2012    source источник
comment
set было бы более подходящим, поскольку вам не нужно связанное значение с каждым элементом. Я собираюсь предположить, что проверка и последующая вставка в набор будет медленнее, чем простая вставка, потому что в первом случае вам придется выполнять два ключевых поиска.   -  person GWW    schedule 10.10.2012
comment
По определению любой из них будет проверять за вас при выполнении вставки. Т.е. они будут делать то, что вы в противном случае сделали бы с другим контейнером: проверить наличие. Лично я бы пошел с набором, если вы специально не сопоставляете что-то с чем-то другим.   -  person WhozCraig    schedule 10.10.2012
comment
Всегда ли данные отсортированы? Поскольку похоже, что вам нужен std :: unique, а не новый контейнер   -  person Mooing Duck    schedule 10.10.2012
comment
Нет, это не отсортировано. Однако мне нужен контейнер, чтобы возвращать результаты из исходного набора данных (который я должен сохранить нетронутым).   -  person Gigi    schedule 10.10.2012
comment
Спасибо всем за ответы. К сожалению, я не могу отметить их все. :)   -  person Gigi    schedule 10.10.2012

Ответы (5)


arrow_upward
11
arrow_downward

std::map не использует хеширование. std::unordered_map есть, но это C ++ 11. std::map и std::set используют предоставленный вами компаратор. В шаблонах классов есть значения по умолчанию для этого компаратора, что сводится к operator< сравнению, но вы можете указать свои собственные.

Если вам не нужны и ключ, и значение для хранения (похоже, что вам этого не нужно), вы должны просто использовать std::set, так как это более уместно.

Стандарт не говорит, какие структуры данных maps и sets используют под капотом, только то, что определенные действия имеют определенные временные сложности. На самом деле, большинство известных мне реализаций используют дерево.

Если вы используете operator[] или insert, с точки зрения сложности времени нет никакой разницы, но я бы использовал insert или operator[] до того, как сделал search, за которым следует insert, если элемент не найден. Последнее будет означать два отдельных поиска, чтобы вставить элемент в набор.

person John Dibling    schedule 10.10.2012

arrow_upward
7
arrow_downward

insert() на любом из связанных контейнеров выполняет find(), чтобы увидеть, существует ли объект, а затем вставляет объект. Простая вставка элементов в std::set<T> должна достаточно эффективно избавиться от дубликатов.

В зависимости от размера вашего набора и соотношения дубликатов к уникальным значениям, может быть быстрее поместить объекты в std::vector<T>, std::sort(), а затем использовать std::unique() вместе с std::vector<T>::erase(), чтобы избавиться от дубликатов.

person Dietmar Kühl    schedule 10.10.2012
comment
insert() [...] выполняет find() [но если не найдено] вставляет ... - форматирование стиля кода find() может быть воспринято некоторыми читателями как вызов find() API-вызова, в то время как реализации insert(x) не будут буквально использовать .find(x), поскольку, когда он отсутствует, нет записи (итератора до), где поиск был прекращен, что необходимо для пропуска другого путешествия по дереву O (logN) для фактической вставки. Вы можете приблизиться с lower_bound, за которым следует insert перегрузка с использованием итератора hint, но реализации insert будут обрабатывать это внутренне для оптимальной производительности. - person Tony Delroy; 30.07.2015

arrow_upward
2
arrow_downward

Сколько раз вы должны это делать?

Если вставка обычная:

//*/
std::set<int> store;
/*/
// for hash:
std::unordered_set<int> store;
//*/
int number;

if ( store.insert(number).second )
{
  // was not in store
}

Если заполнить один раз:

std::vector<int> store;
int number;

store.push_back(number);
std::sort(store.begin(),store.end());
store.erase(std::unique(store.begin(),store.end()),store.end() );

// elements are unique
person Naszta    schedule 10.10.2012

arrow_upward
0
arrow_downward

Предполагая общую стратегию реализации для std::map и std::set, то есть сбалансированные бинарные деревья поиска, и вставка, и поиск должны выполнять обход дерева, чтобы найти место, где должен быть ключ. Таким образом, неудачный поиск с последующей вставкой будет примерно в два раза медленнее, чем простая вставка.

как std :: map удается правильно хранить (хешировать?) данные для быстрого доступа через operator []?

С помощью указанной вами функции сравнения (или std::less, которая работает, если вы перегружаете operator< на свой настраиваемый тип). В любом случае std::map и std::set не хеш-таблицы.

person Fred Foo    schedule 10.10.2012

arrow_upward
0
arrow_downward

std::set и std::map оба реализованы как красно-черное дерево, насколько мне известно. И, вероятно, использование только вставки будет быстрее (тогда и то и другое, потому что вы удвоите время поиска).

Также map и set используют operator <. Пока ваш класс определил operator <, он сможет использовать их как ключи.

person tozka    schedule 10.10.2012