Which the better way to sort distinct numbers?

Question

In C++ using STL which of the two operations take less CPU time to sort large distinct numbers:

Push the elements into a set
Store the elements in a vector and call sort() function?

Why would you want to use the STL? Come pop along to the 21st century with us! — Lightness Races in Orbit, Feb 28 '13 at 02:27
@Arun Now try for larger inputs, and you'll have your answer, won't you? — Lightness Races in Orbit, Feb 28 '13 at 02:28
@Lightness Races in Orbit Is there a better way than using STL? — Alex, Feb 28 '13 at 02:29
Are you worried about insertion time or just sorting time? Sounds like it's time for your to prototype a bit. — Joel, Feb 28 '13 at 02:30
@Arun: he's referring to the fact that, technically, STL was a library from SGI that slightly adapted to become the current containers/algorithms part of the C++ standard library; so, what you are referring to is not technically the STL, although it is still colloquially called so. It's quite a usual (and useless, if you ask me) exercise in nitpicking in the C++ tag. — Matteo Italia, Feb 28 '13 at 02:31
@Arun It's about the use of the _word_ STL: http://stackoverflow.com/questions/5205491/whats-this-stl-vs-c-standard-library-fight-all-about — jogojapan, Feb 28 '13 at 02:32
Related (but not the same, as removing duplicates is involved): http://stackoverflow.com/a/1041939/777186 — jogojapan, Feb 28 '13 at 02:36
@Arun You should use Standard Library algorithms and containers. — Lightness Races in Orbit, Feb 28 '13 at 02:47
@LightnessRacesinOrbit: so, I suppose that, when you are in a hurry, you have lunch at «the place that sells baked goods filled with dairy and meat-derived products and vegetables, as well as beverages most of which are carbonated» :-) — Matteo Italia, Feb 28 '13 at 03:06
@MatteoItalia That is a most accurate assessment, indeed! (What I _don't_ do is pop along to the local tavern for some hop-skotch and mead.) — Lightness Races in Orbit, Feb 28 '13 at 10:37

score 6 · Accepted Answer · answered Feb 28 '13 at 02:47

If it's a one-off operation, I would use a std::vector followed by a std::sort.

As far as asymptotic complexity is involved, the two solutions should be equivalent: insertion in a set is O(log(n)), and you do that for N elements, so it's O(N log(N)) (proof).

On the other hand, insertion in a vector (provided that you know the size in advance) is O(N), and sorting is O(N log(N)), so globally it's O(N log(N)).

But: a vector requires a one-off allocation (or, if you don't know the final size, it should reach the definitive size in O(log(N)) reallocations on typical implementations); on the other hand, a set, if implemented as an RB tree, requires an allocation for each node, which means that you have to call the allocator N times - and allocator calls, in a POD container, are probably going to be one of the bottlenecks. Also, a tree typically has less cache locality and uses more memory, so all this overhead is probably going to hurt performance.

Also, big-O notation shows the functional time dependency, but hides the multiplicative constants; don't take my word for this, but I'm almost sure that N*set insertion is going to cost more than a single sort at the end due to all the extra bookkeeping to do for each element (a tree insertion often needs some work to restore the RB tree properties).

On the other hand, if you have to keep your data structure sorted (with new data coming by the by) the set is usually the correct solution.

But, as always, when in doubt profile.

Which the better way to sort distinct numbers?

1 Answers1