sorting vector using sets

Question

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

Here 'v2' will contain the same elements as 'v1' but sorted in ascending order.what will be the time complexity of this sort process. set s stores ints in sorted form .

Note that `s` actually may *not* contain the same elements as in `v1` if there's duplicate values in `v1`. — Some programmer dude, Jul 27 '13 at 17:46
That's my point, sorting generally do *not* remove duplicates. And you still have to copy the values from the set to the new vector, which adds complexity. — Some programmer dude, Jul 27 '13 at 17:49
The complexity is O(n log n). However, it nicely shows that a complexity measure alone isn't enough: using a `std::set` is hideously slow. Don't do it! — Dietmar Kühl, Jul 27 '13 at 18:33

score 1 · Accepted Answer · answered Jul 27 '13 at 19:04

Copying the data from the vector to the set will be slower, because it will involve creating a data structure on the heap (typically a red-black tree), while sorting can be done in-place (effectively using the stack as a temporary data store).

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

On my system (clang, libc++, Mac OS 10.8), this prints:

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

Building the set takes 7 memory allocations (one per entry). Sorting the vector takes none.

score 0 · Answer 2 · answered Jul 27 '13 at 17:53

0

If there are no duplicates in v1

std::sort(v1.begin(), v1.end()); will be much faster

If duplicates in v1 is too large, following will be faster

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

answered Jul 27 '13 at 17:53

P0W

46,614
9
72
119

If there are duplicates you still want to. use `std::sort()` but follow it up with `std::unique()` and `std::vector::erase()` if you want unique elements. – Dietmar Kühl Jul 27 '13 at 18:29
@DietmarKühl My answer was based on this graph analysis:http://stackoverflow.com/questions/1041620/most-efficient-way-to-erase-duplicates-and-sort-a-c-vector/1041939#1041939 – P0W Jul 27 '13 at 20:49

sorting vector using sets

2 Answers2