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的散列仍然诠释，所以我不这里看不到性能的提升）。所以，最后我决定把基准它和我的结果是：

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 

所以，apperently，样品你给了我们这里，你的实现是最快的国家之一。当您的API只返回几个可能的向量组合并且迭代次数很少时，就是这种情况。我决定通过rand() N> 4（*）来验证当你有更多不同的值时会发生什么。它保持这种方式。无序集是最慢的一个（哈希计算成本）。 因此，要回答你的问题：自己衡量你的情况 - 这是确定哪一个是最快的方法的最佳方法。

（*）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或unordered 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());