8

我有一堆充满重复的数据，我想消除重复。你知道，例如 [1, 1, 3, 5, 5, 5, 7] 变成 [1, 3, 5, 7]。

看起来我可以使用 std::map 或 std::set 来处理这个问题。但是我不确定（a）简单地将所有值插入容器中是否更快，或者（b）检查它们是否已经存在于容器中并且仅在它们不存在时才插入 - 插入是否非常有效？即使有更好的方法......你能建议一种快速的方法吗？

另一个问题 - 如果我存储在其中的数据不像整数那么微不足道，而是一个自定义类，std::map 如何管理正确存储（散列？）数据以便通过运算符快速访问 [ ]？

4

5 回答 5

11

std::map不使用散列。 std::unordered_map确实如此，但那是 C++11。 std::map并且std::set都使用您提供的比较器。类模板具有此比较器的默认值，归结为operator<比较，但您可以提供自己的比较器。

如果您不需要同时存储键和值（看起来不需要），您应该只使用 a std::set，因为这样更合适。

该标准没有说明maps 和sets 在幕后使用什么数据结构，只是说明某些操作具有一定的时间复杂性。实际上，我知道的大多数实现都使用树。

如果您使用operator[]or insert，在时间复杂性方面没有区别，但如果找不到该项目，我会在执行 a 之前使用insertor后跟 an 。后者意味着两个单独的搜索将一个项目插入到集合中。operator[]searchinsert

于 2012-10-10T19:01:22.247 回答
7

对insert()任何关联容器执行 afind()查看对象是否存在，然后插入该对象。只需将元素插入 an 即可std::set<T>合理有效地消除重复项。

根据您的集合的大小以及重复值与唯一值的比率，将对象放入std::vector<T>,std::sort()然后std::unique()与 with 一起使用std::vector<T>::erase()以消除重复值可能会更快。

于 2012-10-10T19:00:18.177 回答
2

你应该做多少次？

如果插入是通常的：

//*/
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
于 2012-10-10T19:00:19.070 回答
0

假设 和 的常见实现策略std::map，std::set即平衡二叉搜索树，插入和查找都必须进行树遍历以找到键所在的位置。因此，查找失败然后插入的速度大约是插入的两倍。

std::map 如何正确存储（散列？）数据以便通过 operator[] 快速访问？

通过您指定的比较函数（或者std::less，如果您重载operator<自定义类型，则该函数有效）。无论如何，std::map都不std::set是哈希表。

于 2012-10-10T18:59:19.940 回答
0

std::set据我所知，std::map它们都被实现为红黑树。并且可能只使用插入会更快（然后两者都因为你会加倍查找时间）。

也map和set使用operator <. 只要您的班级定义了operator <它就可以将它们用作键。

于 2012-10-10T19:01:41.257 回答