分揀使用矢量集

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

這裏「V2」將包含相同的元素爲「V1」，但以升序排序order.what將這種進程的時間複雜度。以排序的形式設置商店整數。分揀使用矢量集

來源

2013-07-27 hoder

這取決於您使用的排序算法。 – 2013-07-27 17:35:40

@ H2CO3這裏s會自己排序。 – hoder

請注意，如果'v1'中存在重複值，'s'實際上可能不包含與'v1'中相同的元素。 –

從矢量數據複製到該設置將會比較慢，因爲它會涉及到在堆上創建數據結構（通常是紅黑樹），同時可以在原地進行排序（將堆棧有效地用作臨時數據存儲）。

#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; 
    }

在我的系統（鐺，的libC++和Mac OS 10.8），這個打印：

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

構建一套需要7次內存分配（每一個條目的）。對矢量排序不需要。

來源

2013-07-27 19:04:44

如果在V1不存在重複

std::sort(v1.begin(), v1.end());會快很多

如果V1重複過大，下面會更快

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

來源

2013-07-27 17:53:51 P0W

如果有重複，你仍然想要。如果你想要獨特的元素，使用'std :: sort（）'，但是跟着它使用'std :: unique（）'和'std :: vector :: erase（）'。 –

@DietmarKühl我的答案是基於此圖分析：http：//stackoverflow.com/questions/1041620/most-efficient-way-to-erase-duplicates-and-sort-a-c-vector/1041939#1041939 – P0W

分揀使用矢量集

回答

相關問題