什么是在std vector中只出现一次的元素复制的最有效方法？

Question

什么是在std vector中只出现一次的元素复制的最有效方法？

15

我有一个元素如下的std向量：

[0 , 1 , 2 , 0 , 2 , 1 , 0 , 0 , 188 , 220 , 0 , 1 , 2 ]

如何高效地查找并复制此向量中仅出现一次的元素，而又不使用 O(n^2) 的暴力算法？在此情况下，新列表应包含 [188, 220]。

- sp497

我会先对它进行排序，之后就很容易了。 - tkausl

如果向量应该是常量，并且不能被排序，则将其复制到第二个向量中，然后对其进行排序。 - Sam Varshavchik

我知道这不完全是你要求的，但它让我想起了C#的LINQ管道 - 这是它的C++版本http://pfultz2.github.io/Linq/ - 还有许多其他版本（请问谷歌）。 - pm100

为什么要考虑使用O(N^2)的暴力破解，当排序通常是O(N.logN)，并且根据您的数据范围，可能存在O(N)的解决方案。谁知道呢？您没有指定。 - paddy

4个回答

8

通用最优算法很少。哪种算法最适合通常取决于正在处理的数据的属性。去重就是一个这样的例子。

v很小并且大部分填充了唯一值，是这样吗？

auto lo = v.begin(), hi = v.end();
std::sort(lo, hi);
while (lo != v.end()) {
    hi = std::mismatch(lo + 1, v.end(), lo).first;
    lo = (std::distance(lo, hi) == 1) ? hi : v.erase(lo, hi);
}

v是否很小且主要由重复内容填充？

auto lo = v.begin(), hi = v.end();
std::sort(lo, hi);
while (lo != v.end()) {
    hi = std::upper_bound(lo + 1, v.end(), *lo);
    lo = (std::distance(lo, hi) == 1) ? hi : v.erase(lo, hi);
}

< p > v 是否是巨大的？

std::unordered_map<int, bool> keyUniqueness{};
keyUniqueness.reserve(v.size());
for (int key : v) {
    bool wasMissing = keyUniqueness.find(key) == keyUniqueness.end();
    keyUniqueness[key] = wasMissing;
}
v.clear();
for (const auto& element : keyUniqueness) {
    if (element.second) { v.push_back(element.first); }
}

And so on.

- Brian Rodriguez

恕我直言，我更喜欢我的版本=P。更简洁易读。对于小数据集或内存占用，我们总是可以回归到“正常”的映射。使用映射可以自动排序并处理重复项。你的版本适用于没有重复项的大型向量，因为如果排序成功，它可能会在原地工作。 - luk32

你能解释一下第三个代码块吗？即：当向量非常巨大时。 - sp497

@SRINI794 超过一百万个元素是“巨无霸”的一个很好的例子。 - Brian Rodriguez

除非你的内存受限，且std::sort可以原地排序，否则总是最好使用它，除了对于没有重复项的大向量。我在cppreference上找不到这样的限制 =/。然而，它确实具有很好的教育价值，并且它存在并被讨论是很好的，我认为它涵盖了一个有效的案例。 - luk32

1

@luk32 你正在查看unordered_map的摊销成本。你应该记住，在O(1)前面可能会有一些巨大的常数，使其比这些方法更慢。算法几乎从来不是黑白分明的优劣。它将取决于正在处理的数据类型。例如：对于小列表，冒泡排序比快速排序更快！ - Brian Rodriguez

显示剩余7条评论

1

由于您使用了 std::vector，我推测您想最大化其所有好处，包括参考局部性。为了做到这一点，我们需要在这里打一些字。我对下面的代码进行了基准测试...

我有一个线性的O(n)算法（实际上是O(nlog(n))），它有点像brian的答案，但我使用OutputIterators而不是原地操作。前提条件是已排序。

template<typename InputIterator, typename OutputIterator>
OutputIterator single_unique_copy(InputIterator first, InputIterator last, OutputIterator result){
    auto previous = first;
    if(previous == last || ++first == last) return result;
    while(true){
        if(*first == *previous)
            while((++first != last) && (*first == *previous));
        else
            *(result++) = *previous;
        if(first == last) break;
        previous = first;
        ++first;
    }
    return ++result;
}

这里是一个示例用法：

int main(){
    std::vector<int> vm = {0, 1, 2, 0, 2, 1, 0, 0, 1, 88, 220, 0, 1, 2, 227, -8};
    std::vector<int> kk;
    std::sort(vm.begin(), vm.end());
    single_unique_copy(vm.begin(), vm.end(), std::back_inserter(kk));
    for(auto x : kk) std::cout << x << ' ';
    return 0;
}

如预期，输出为：

-8, 88, 220, 227

你的使用情况可能与我的不同，因此首先要进行配置文件... :-)

编辑:

使用luk32的算法和我的算法... 使用1300万个元素... 按降序创建，在每个i % 5处重复。
在调试构建下，luk32: 9.34秒，我的: 7.80秒
在-O3下，luk32: 2.71秒，我的: 0.52秒
Mingw5.1 64位，Windows10，1.73Ghz Core i5 4210U，6GB DDR3 1600Mhz RAM
基准测试在这里，http://coliru.stacked-crooked.com/a/187e5e3841439742

对于较小的数字，差异仍然存在，直到它成为非关键代码

- WhiZTiM

1

@luk32的回答绝对是解决这个问题最省时间的方法。然而，如果你的内存不足以承受一个unordered_map，还有其他的方法。

你可以使用std::sort()先对向量进行排序。然后在一次迭代中就可以找到非重复项。总体复杂度为O(nlogn)。

如果问题稍有不同，并且你知道只有一个非重复元素，你可以使用this code（Java代码）。这里的复杂度是O(n)。

- SegFault

我建议不要使用这样的大胆说法。当元素数量巨大时，unordered_map是一个很好的解决方案。但如果数量较小，则有更高效的处理数据的方法。 - Brian Rodriguez

我同意你的观点，unordered_map 绝对是最好的方法。但是我想再提供两种解决方案，以防用户由于某些原因无法使用其他数据结构。这种情况可能会在面试问题中出现。我记得我曾被问到一个面试问题，要求我实现一个可以跟踪其最大值的堆栈。我也只能将值本身推入堆栈中，这让我措手不及。 - SegFault

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- luk32 · Accepted Answer

创建一个无序哈希表unordered_map<DataType, Count> count;
遍历输入向量并增加每个值的计数，类似于count[value]++;
遍历count哈希表，在值等于1时复制键。

时间复杂度为O(n)。使用哈希表，对于小数据集，通常使用标准哈希表可能更有效率，但从技术上讲它是O(n log n)。

这是一种处理离散数据集的好方法。

代码示例：

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v{1,1,2,3,3,4};
    unordered_map<int,int> count;
    for (const auto& e : v) count[e]++;
    vector<int> once;
    for (const auto& e : count) if(e.second == 1) once.push_back(e.first);
    for (const auto& e : once) cout << e << '\n';
    return 0;
}

我已经尝试了一些想法。但是我看不到绕过map的方法。unordered_multiset几乎是一个很好的方式......除非它不允许你遍历键，它有一个检查键计数的方法，但是你需要另一个集合来探测键。在现代C++中，使用auto进行计数很容易。我也查看了algorithm库，但是我没有找到任何transform、copy_if、generate等条件转换元素（映射条目 -> 值，如果计数为1）的方法。