我有一个数字序列(未排序，没有重复)，目标是对它们进行排序。
方法1:插入到vector中。O(n)，使用排序算法进行排序。O (nlogn)
方法2:插入到集合中。o (nlogn)
哪种方法会更快?
我觉得set会更快，因为每个插入向量都必须分配完成数组元素，复制它，然后删除它，这可能是昂贵的。但我在网上看到，大多数位置向量都是过集的。
谁能告诉我哪一个更快与适当的逻辑?
编辑:如果我们事先不知道元素的个数，哪一个是更快的集合或向量(两者都没有小元素，也没有大元素?)注意:如果没有元素是大的集合似乎是更好的选择，但它对小的也好吗?不知道)
如果你事先知道有许多元素需要，你可以在你的向量中
reserve()空间以避免重新分配，使第一个选择非常有趣(快速插入，单次排序)。如果你需要做一次，去做
std::vector<>。如果其他插入将在稍后的程序中发生，则std::set<>可能更有趣。如果事先不知道预期大小，则可能会对向量进行重新分配，
std::set<>是一个不错的选择(理论平均复杂度更好)。O(n) + O(n * log(n))对于向量vs O(n * log(n))对于集合
如果元素的数量非常小，您仍然可以保留一些空间(例如，如果您期望10个元素，您可能会保留100个元素以确保安全)，并使用
std::vector
无论如何，分析两种解决方案始终是一个很好的实践，实际结果将取决于(除其他事项外)输入的初始排序状态和每个容器的实现质量。
注意:
- 请记住，
std::set有更大的内存占用，如果它对您很重要的话。
这取决于你的用例。
组:
<+快速数据插入O(logn)
+你不需要关心排序
-由于set是作为树来实现的，因此每个元素都有内存开销。
-数据可以分散在内存堆中，因此CPU缓存不能很好地工作。
向量/strong>:
+数据包含在连续的内存块中。所以，你的CPU缓存工作得更好了。
+你的搜索是相同的O(logn)
+你可以为它
reserve内存-你需要在每次更改后进行排序。
所以，如果你有很多元素，并且做"一次插入，多次搜索"，我更喜欢向量。如果要进行许多插入/搜索查询，最好坚持使用set。
在O()方面，我想说向量插入成本是O(nlogn)，但它可以在所有插入之后调用一次。set insert的代价是O(logn)，并且调用每次插入。因此，如果您需要在vector排序后插入，您将为vector支付num_insertions*O(nlogn)，为set支付O(log (n+num_insertions))，这非常便宜。
我想我会使用分析器来研究这个问题。我的代码:
//g++ -std=c++11 -Wall vectorvsset.cpp -g -pg -o vectorvsset
#include <time.h>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
void GenRandom(vector<int32_t> &original)
{
original.clear();
for(size_t i=0; i<10000; i++)
original.push_back(rand());
}
void TestSet(const vector<int32_t> &original)
{
set<int32_t> testset;
testset.insert(original.begin(), original.end());
}
void TestVector(const vector<int32_t> &original)
{
vector<int32_t> testvec;
testvec.insert(testvec.end(), original.begin(), original.end());
sort(testvec.begin(), testvec.end());
}
void TestVectorConvertToSet(const vector<int32_t> &original)
{
vector<int32_t> testvec;
testvec.insert(testvec.end(), original.begin(), original.end());
sort(testvec.begin(), testvec.end());
std::set<int32_t> testsec(testvec.begin(), testvec.end());
}
int main()
{
srand(time(NULL));
cout << "RAND_MAX " << RAND_MAX << endl;
vector<int32_t> original;
for(size_t i=0; i<100; i++)
{
GenRandom(original);
TestSet(original);
TestVector(original);
TestVectorConvertToSet(original);
}
return 0;
}
使用gprof on g++ (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609我的(缩写)结果是:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
0.00 1.42 0.00 100 0.00 3.36 TestVector(std::vector<int, std::allocator<int> > const&)
0.00 1.42 0.00 100 0.00 6.86 TestVectorConvertToSet(std::vector<int, std::allocator<int> > const&)
0.00 1.42 0.00 100 0.00 3.57 TestSet(std::vector<int, std::allocator<int> > const&)
所以使用向量更快，但没有太大区别