производительность — C ++ std :: map или std :: set — эффективно вставлять дубликаты
У меня есть куча данных, полная дубликатов, и я хочу удалить дубликаты. Вы знаете, например, [1, 1, 3, 5, 5, 5, 7] становится [1, 3, 5, 7].
Похоже, я могу использовать либо std :: map или std :: set для обработки этого. Однако я не уверен, быстрее ли (а) просто вставить все значения в контейнер или (б) проверить, существуют ли они уже в контейнере, и вставить только, если их нет — вставки очень эффективны? Даже если есть лучший способ … можете ли вы предложить быстрый способ сделать это?
Другой вопрос — если данные, которые я храню в них, не так тривиальны, как целые числа, а представляют собой пользовательский класс, как std :: map удается правильно хранить (хеш?) Данные для быстрого доступа через operator [ ]?
Решение
std::map не использует хеширование std::unordered_map делает, но это C ++ 11. std::map а также std::set оба используют компаратор, который вы предоставляете. Шаблоны классов имеют значения по умолчанию для этого компаратора, который сводится к operator< сравнение, но вы можете предоставить свой собственный.
Если вам не нужны ни ключ, ни значение для хранения (похоже, вам это не нужно), вам просто нужно использовать std::set, так как это более уместно.
Стандарт не говорит, что структуры данных mapс и setИспользование под капотом, только что определенные действия имеют определенные временные сложности. В действительности, большинство реализаций, которые я знаю, используют дерево.
Не имеет значения, сложность во времени, если вы используете operator[] или же insert, но я бы использовал insert или же operator[] прежде чем я сделал search с последующим insert если предмет не найден. Последнее подразумевает два отдельных поиска для вставки элемента в набор.
Другие решения
insert() на любом из связанных контейнеров делает find() чтобы увидеть, существует ли объект, а затем вставляет объект. Просто вставив элементы в std::set<T> Следует избавиться от дубликатов достаточно эффективно.
В зависимости от размера вашего набора и отношения дубликатов к уникальным значениям, может быть быстрее поместить объекты в std::vector<T>, std::sort() затем, а затем использовать std::unique() вместе с std::vector<T>::erase() чтобы избавиться от дубликатов.
Сколько раз вы должны это сделать?
Если вставка обычная:
//*/
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
Предполагая общую стратегию реализации std::map а также std::setто есть сбалансированные деревья бинарного поиска, и вставка, и поиск должны выполнить обход дерева, чтобы найти место, где должен находиться ключ. Поэтому неудачный поиск с последующей вставкой будет примерно в два раза медленнее, чем просто вставка.
Как std :: map удается правильно хранить (хеш?) данные для быстрого доступа через оператора []?
С помощью функции сравнения, которую вы указываете (или std::less, который работает, если вы перегружаете operator< на ваш пользовательский тип). В любом случае, std::map а также std::set являются не хеш-таблицы
std::set а также std::map оба реализованы как красное черное дерево, насколько я знаю. И, вероятно, использование только вставки будет быстрее (тогда и то и другое, потому что вы удвоите время поиска).
Также map а также set использование operator <, Пока ваш класс определил operator < Он мог бы использовать их в качестве ключей.