c++ - 使用集合对向量进行排序

Question

vector <int> v1(6);
//some procedure to fill the vector v1 with ints.
set <int> s(v1);
vector <int> v2(s)

这里“v2”将包含与“v1”相同的元素，但按升序排序。这个排序过程的时间复杂度是多少。set s 以排序形式存储整数。

Answer 1

将数据从向量复制到集合会比较慢，因为这将涉及在堆上创建数据结构（通常是红黑树），而排序可以就地完成（有效地将堆栈用作临时数据店铺）。

#include <iostream>
#include <vector>
#include <set>

size_t gAllocs;
size_t gDeallocs;

void * operator new ( size_t sz )   { ++gAllocs; return std::malloc ( sz ); }
void   operator delete ( void *pt ) { ++gDeallocs; return std::free ( pt ); }

int main () {
    gAllocs = gDeallocs = 0;
    std::vector<int> v { 8, 6, 7, 5, 3, 0, 9 };
    std::cout << "Allocations = " << gAllocs << "; Deallocations = " << gDeallocs << std::endl;
    std::set<int> s(v.begin(), v.end());
    std::cout << "Allocations = " << gAllocs << "; Deallocations = " << gDeallocs << std::endl;
    std::sort ( v.begin(), v.end ());
    std::cout << "Allocations = " << gAllocs << "; Deallocations = " << gDeallocs << std::endl;

    return 0;
    }

在我的系统（clang、libc++、Mac OS 10.8）上，打印：

$ ./a.out 
Allocations = 1; Deallocations = 0
Allocations = 8; Deallocations = 0
Allocations = 8; Deallocations = 0

构建集合需要 7 次内存分配（每个条目一个）。对向量进行排序不需要任何内容​​。

Answer 2

如果 v1 中没有重复项

std::sort(v1.begin(), v1.end());会快得多

如果 v1 中的重复项太大，跟随会更快

std::set<int> s( v1.begin(), v1.end() );
v2.assign( s.begin(), s.end() );