STL Container?

[Mike Copeland]

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<{{
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

 

[Marcel Müller]

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

 

[Marc]

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.

std::nth_element.

 

[Alf P. Steinbach]

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<{{
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

<code>
#include <iostream>
#include <queue> // std:riority_queue
#include <utility> // std::begin, std::end
using namespace std;

class EnumerablePQ
: public priority_queue< int >
{
typedef priority_queue< int > Base;
public:
EnumerablePQ(
int const* const startOfData,
int const* const endOfData
)
: Base( startOfData, endOfData )
{}

int const* begin() const
{ return (c.empty()? nullptr : &c[0]); }


int const* end() const
{ return (c.empty()? nullptr : &c[0] + c.size()); }
};

int main()
{
int const data[] =
{
3, 1, 4, 1, 5, 9, 2, 6, 5, 4,
2, 7, 1, 8, 2, 8, 1, 8, 2, 8
};
EnumerablePQ const epq( begin( data ), end( data ) );

for(
int const* p = epq.begin();
p != epq.end() && p - epq.begin() <= 10;
++p )
{
cout << *p << endl;
}
}
</code>


Cheers & hth.,

- Alf

 

[Warp]

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

std:artial_sort() does exactly that.