c++连接多个std：：载体并删除重复

Question

我正在接收来自外部API的一些整数(std::vector)。

API通常需要多次调用，因此我需要将连续API调用中的所有整数累加到本地向量。最后，数组的每个元素都必须是唯一的(不需要排序)。

我的代码如下(使用getNextVector来“模拟”数据和模拟API调用)。

代码可以工作，但是我想要这个操作的最大性能。我的方法对吗？

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

std::vector<int> getNextVector(int i) {
    if ( i == 0 ) {
        std::vector<int> v = { 1,2,3 };
        return v; 
    } else if ( i == 1 ) {
        std::vector<int> v = { 3,4,5 };
        return v; 
    } else if ( i == 2 ) {
        std::vector<int> v = { 5,6,7 };
        return v; 
    } else if ( i == 3 ) {
        std::vector<int> v = { 7,8,9 };
        return v; 
    }
}

int count() { return 4; } //we have four vectors

int main(int argc, char** argv) {

    std::vector<int> dest;
    dest.reserve(20); // we can find this, for simplicity hardcode...

    for( int i = 0; i < count(); i++ ) {
        std::vector<int> src = getNextVector(i);
        dest.insert(
            dest.end(),
            std::make_move_iterator(src.begin()),
            std::make_move_iterator(src.end())
        );
    }

    std::sort(dest.begin(), dest.end());
    dest.erase(unique(dest.begin(), dest.end()), dest.end());
/*
    std::copy(
      dest.begin(),
      dest.end(),
      std::ostream_iterator<int>(std::cout, "\n")
    );
*/
    return 0;
}

Answer 1

我认为你可以把向量的元素存储在一个集合中。如果不需要订货，可以使用unordered_set。只需做以下几点-

std::unordered_set<int> integers;

for (int i = 0; i < count; i++) {
    std::vector<int> src = getNextVector(i);

    for (int j = 0; j < src.size(); j++) {
        integers.insert(src[i]);
    }
}

或者，正如@StoryTeller所建议的那样，您可以使用适当的函数而不是循环。例如-

std::unordered_set<int> integers;

for (int i = 0; i < count; i++) {
    std::vector<int> src = getNextVector(i);
    integers.insert(src.begin(), src.end());
}

Answer 2

我的第一个想法是“使用unordered_set可以快速轻松地完成任务”，后来我意识到它对int没有太大帮助(int的散列仍然是int，所以我在这里看不到性能的提高)。因此，最后，我决定对其进行基准测试，我的结果是：

N = 4 Set implementation 304703 miliseconds
N = 4 Unordered set implementation 404469 miliseconds
N = 4 Vect implementation 91769 miliseconds

N = 20 Set implementation 563320 miliseconds
N = 20 Unordered set implementation 398049 miliseconds
N = 20 Vect implementation 176558 miliseconds

N = 40 Set implementation 569628 miliseconds
N = 40 Unordered set implementation 420496 miliseconds
N = 40 Vect implementation 207368 miliseconds

N = 200 Set implementation 639829 miliseconds
N = 200 Unordered set implementation 456763 miliseconds
N = 200 Vect implementation 245343 miliseconds

N = 2000 Set implementation 728753 miliseconds
N = 2000 Unordered set implementation 499716 miliseconds
N = 2000 Vect implementation 303813 miliseconds

N = 20000 Set implementation 760176 miliseconds
N = 20000 Unordered set implementation 480219 miliseconds
N = 20000 Vect implementation 331941 miliseconds

因此，显然，对于您在这里给我们的示例，您的实现是最快的。当API只返回少量可能的向量组合且迭代次数较少时，就会出现这种情况。我决定通过N>4 (*)的rand()来验证当您有更多不同的值时会发生什么。它就能保持这种状态。无序集是最慢的(散列计算成本)。因此，要回答你的问题:基准你自己的情况-这是最好的方式来确定哪一个是最快的。

(*) rand()的坏随机性不是bug，而是这里的一个特性。

编辑:我的回答没有说没有更快的算法--我已经对STL算法进行了基准测试，乍一看，这些算法的行为似乎与结果提供的不同。但可以肯定的是，有一种方法可以更快地进行独特的连接，也许是一组向量或不同容器的组合，我希望有人能提供一个。

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <chrono>

std::vector<int> getNextVector(int i) {
    if (i == 0) {
        std::vector<int> v = { 1,2,3 };
        return v;
    }
    else if (i == 1) {
        std::vector<int> v = { 3,4,5 };
        return v;
    }
    else if (i == 2) {
        std::vector<int> v = { 5,6,7 };
        return v;
    }
    else if (i == 3) {
        std::vector<int> v = { 7,8,9 };
        return v;
    }
    return {rand() % 10000,rand() % 10000,rand() % 10000 };
}


void set_impl(std::set<int>& dest, int N)
{
    // dest.reserve(20); // we can find this, for simplicity hardcode...

    for (int i = 0; i < N; i++) {
        std::vector<int> src = getNextVector(i);
        dest.insert(
            std::make_move_iterator(src.begin()),
            std::make_move_iterator(src.end())
        );
    }
}

void uset_impl(std::unordered_set<int>& dest, int N)
{
    // dest.reserve(20); // we can find this, for simplicity hardcode...

    for (int i = 0; i < N; i++) {
        std::vector<int> src = getNextVector(i);
        dest.insert(
            std::make_move_iterator(src.begin()),
            std::make_move_iterator(src.end())
        );
    }
}

void vect_impl(std::vector<int>& dest, int N)
{
    for (int i = 0; i < N; i++) {
        std::vector<int> src = getNextVector(i);
        dest.insert(
            dest.end(),
            std::make_move_iterator(src.begin()),
            std::make_move_iterator(src.end())
        );
    }

    std::sort(dest.begin(), dest.end());
    dest.erase(unique(dest.begin(), dest.end()), dest.end());
}

int main(int argc, char** argv) {


    for (int N : { 4, 20, 40, 200, 2000, 20000 })
    {

        const int K = 1000000 / N;

        using clock = std::chrono::high_resolution_clock;

        std::set<int> sdest;
        auto start = clock::now();
        for (int i = 0; i < K; i++)
        {
            sdest.clear();
            set_impl(sdest, N);
        }
        auto set_ms = std::chrono::duration_cast<std::chrono::microseconds>(clock::now() - start).count();


        std::unordered_set<int> usdest;
        start = clock::now();
        for (int i = 0; i < K; i++)
        {
            usdest.clear();
            uset_impl(usdest, N);
        }
        auto uset_ms = std::chrono::duration_cast<std::chrono::microseconds>(clock::now() - start).count();

        std::vector<int> dest;
        dest.reserve(N); // we can find this, for simplicity hardcode...
        start = clock::now();
        for (int i = 0; i < K; i++)
        {
            dest.clear();
            vect_impl(dest, N);
        }
        auto vect_ms = std::chrono::duration_cast<std::chrono::microseconds>(clock::now() - start).count();

        std::cout << "N = " << N << " Set implementation " << set_ms << " miliseconds\n";
        std::cout << "N = " << N << " Unordered set implementation " << uset_ms << " miliseconds\n";
        std::cout << "N = " << N << " Vect implementation " << vect_ms << " miliseconds\n";

    }
    return 0;
}

Answer 3

如果您想要保持从外部API接收的元素的顺序，并且它们没有排序，那么我建议您创建第二个向量，以保持排序。然后对排序向量执行lower_bound，如果返回的迭代器不是值，则在目标向量和排序向量中插入(使用返回的迭代器作为排序向量中的插入位置)。对整数使用set或无序集可能要慢得多(可能是数量级的慢)。如果您不关心顺序，那么使用一个排序向量。

vector<int> sorted;
....
vector<int> src = getNextVector(i);
for( int i : src ) {
  auto itr = std::lower_bound( sorted.begin(), sorted.end(), i );
  if( *itr != i ) {
     sorted.insert(itr, i);
     integers.push_back(i);
  }
}

如果您知道每次调用getNextVector的值都是唯一的，那么您可以执行如下操作(这可能会更快)。

vector<int> sorted;
....
vector<int> src = getNextVector(i);
vector<int> usrc;
for( int i : src ) {
  auto itr = std::lower_bound( sorted.begin(), sorted.end(), i );
  if( *itr != i ) {
     usrc.push_back(i);
     integers.push_back(i);
  }
}
sorted.insert(sorted.end(), usrc.begin(), usrc.end());
std::sort( sorted.begin(), sorted.end() );