Re: STL Container?

From:

=?ISO-8859-15?Q?Marcel_M=FCller?= <news.5.maazl@spamgourmet.com>

Newsgroups:

comp.lang.c++

Date:

Wed, 02 May 2012 17:07:35 +0200

Message-ID:

<4fa14db7$0$6548$9b4e6d93@newsspool4.arcor-online.net>

On 02.05.2012 16:20, Mike Copeland wrote:

Is there an STL container that lends itself to "top-N" or "largest-
N" processing? It seems that a traditional sorted array would do, but
the continual evaluation, deletion/insertion, and resorting process is
cumbersome and expensive. 8<{{

If you bother about the change rate std::set, std::multiset std::map or
std::multimap should do. Either of them has the complexity O(log(n)) on
insertions.

I would like to pass a large number of data records and select the 10
largest (or smallest) items, but it seems there is no STL facility that
makes that process easy. Please advise. TIA

Well, this is another question. If you seek only for the top 10, it is
in general no good advise to sort the entire array. More sophisticated
implementations take the top ten of arbitrary subsets and combine them
by a merge sort operation, always returning no more than ten elements at
each stage. This can be done recursively.
The algorithm has still the same O(n log(n)) complexity than sorting,
but it is only O(log(n)) in memory, which is quite cheap. You need no
binary tree for this purpose. A sorted array will perform well.

Marcel