c++ - 从 vector 中删除最小的非唯一值

Question

我有一个未排序的 double vector (实际上是在本例中使用的具有 double 成员的对象)。我需要从这个 vector 中删除最小的非唯一值。但是，不保证存在非唯一值。允许对范围进行排序。

一如既往，我开始寻找 std::algorithm 并找到了 std::unique。在我的第一个想法中，我会将其与 std::sort 结合使用，将所有非唯一值移动到 vector 的末尾，然后对非唯一值使用 min_element。但是， std::unique 将在末尾留下非唯一值处于未指定状态。事实上，我失去了所有非 POD 成员。

有没有人建议如何有效地做到这一点？有效地执行此操作很重要，因为代码用于程序的瓶颈(已经有点太慢了)。

Answer 1

好吧，如果您可以对范围进行排序，那么这很容易。按升序排序，然后遍历直到遇到两个相等的相邻元素。完成。

像这样:

T findSmallestNonunique(std::vector<T> v)
{
   std::sort(std::begin(v), std::end(v));
   auto it = std::adjacent_find(std::begin(v), std::end(v));
   if (it == std::end(v))
      throw std::runtime_error("No such element found");
   return *it;
}

这是 a demonstration :

#include <vector>
#include <algorithm>
#include <stdexcept>
#include <iostream>

template <typename Container>
typename Container::value_type findSmallestNonunique(Container c)
{
   std::sort(std::begin(c), std::end(c));
   auto it = std::adjacent_find(std::begin(c), std::end(c));

   if (it == std::end(c))
      throw std::runtime_error("No such element found");

   return *it;
}

int main(int argc, char** argv)
{
    std::vector<int> v;
    for (int i = 1; i < argc; i++)
        v.push_back(std::stoi(argv[i]));

    std::cout << findSmallestNonunique(v) << std::endl;
}

// g++ -std=c++14 -O2 -Wall -pedantic -pthread main.cpp \
// && ./a.out 1 2 2 3 4 5 5 6 7 \
// && ./a.out 5 2 8 3 9 3 0 1 4 \
// && ./a.out 5 8 9 2 0 1 3 4 7
// 
// 2
// 3
// terminate called after throwing an instance of 'std::runtime_error'
//   what():  No such element found

请注意，这里我没有执行就地搜索，但我可以通过引用获取容器来执行搜索。 (这取决于您是否被允许对原始输入进行排序。)

由于排序操作，这可能和O(N×log(N))一样“糟糕”，但它简单易维护，不需要任何分配/复制(除了整个数据集的单个拷贝，如上所述，您可以完全避免)。如果您的输入很大或者您希望在大多数情况下匹配失败，您可能想要使用其他东西。一如既往:简介!