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 以排序的形式存储整数。
最佳答案
将数据从 vector 复制到 set 会比较慢,因为这将涉及在堆上创建数据结构(通常是红黑树),而排序可以就地完成(有效地使用堆栈作为临时数据存储)。
#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 次内存分配(每个条目一次)。对 vector 进行排序不需要花费任何时间。
关于c++ - 使用集合对 vector 进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17900651/