std::map get n max elements

[Philipp Kraus]

Hello,

I've got a std::map<std::string, std::size_t>. How can I extract the
n-th biggest elements. For example:
the map: map["a"] = 5, map["b"] = 5, map["c"] = 7, map["d"] = 10, map["e"] = 10

I would like to get a map only with (n=3)
newmap["e"] = 10
newmap["d"] = 10
newmap["c"] = 7

I need only the key values, also a std::vector with ("e", "d", "c") can
be the result.

Thx

Phil

 

[Noah Roberts]

Hello,

I've got a std::map<std::string, std::size_t>. How can I extract the
n-th biggest elements. For example:
the map: map["a"] = 5, map["b"] = 5, map["c"] = 7, map["d"] = 10,
map["e"] = 10

I would like to get a map only with (n=3)
newmap["e"] = 10
newmap["d"] = 10
newmap["c"] = 7

I need only the key values, also a std::vector with ("e", "d", "c") can
be the result.

Looks like a basic max algorithm to me.

std:air<std::string,std::size_t> is going to be the value type of your
map if you iterate it. Should be fairly straight forward from there.

 

[Philipp Kraus]

Hello,

I've got a std::map<std::string, std::size_t>. How can I extract the
n-th biggest elements. For example:
the map: map["a"] = 5, map["b"] = 5, map["c"] = 7, map["d"] = 10,
map["e"] = 10

I would like to get a map only with (n=3)
newmap["e"] = 10
newmap["d"] = 10
newmap["c"] = 7

I need only the key values, also a std::vector with ("e", "d", "c") can
be the result.

Looks like a basic max algorithm to me.

std:air<std::string,std::size_t> is going to be the value type of
your map if you iterate it. Should be fairly straight forward from
there.

I'm a little bit suprised, because If i get the max of my elements n
times, I'll get only the max. Normally I must sort the map and cut the
n-th max elements (upper or lower bounded elements) or get n times the
max and remove after each run the max element from my map.

But on a std::map I can't sort the data on the value part, so I must
copy the std::map to a multimap, sort and cut. So my question is now:
Can I do it on a std::map without a lot of runs over the map?

Sorry, I'm a little bit confused.

 

[Kai-Uwe Bux]

On 4/27/2011 12:24 PM, Philipp Kraus wrote:
Hello,

I've got a std::map<std::string, std::size_t>. How can I extract the
n-th biggest elements. For example:
the map: map["a"] = 5, map["b"] = 5, map["c"] = 7, map["d"] = 10,
map["e"] = 10

I would like to get a map only with (n=3)
newmap["e"] = 10
newmap["d"] = 10
newmap["c"] = 7

I need only the key values, also a std::vector with ("e", "d", "c") can
be the result.

Looks like a basic max algorithm to me.

std:air<std::string,std::size_t> is going to be the value type of
your map if you iterate it. Should be fairly straight forward from
there.

I'm a little bit suprised, because If i get the max of my elements n
times, I'll get only the max. Normally I must sort the map and cut the
n-th max elements (upper or lower bounded elements) or get n times the
max and remove after each run the max element from my map.

But on a std::map I can't sort the data on the value part, so I must
copy the std::map to a multimap, sort and cut. So my question is now:
Can I do it on a std::map without a lot of runs over the map?

Sorry, I'm a little bit confused.

If n is small (compared to original map size), then you can easily do it
in a single go. Create an array or vector A of size n holding std:air
<std::string,std::size_t> and initialize with minimum possible element
value (0 in this case). A will held n max elements found so far, sorted
by the value. Now iterate through the original map; if the value is equal
or larger than the minimal element in A, insert it in proper position in
A, pushing the least element off from the array. I think you can use
std::lower_bound() for finding the position.

The complexity of this is O(M*log(N)), where M is the size of the initial
map and N is the number of desired maximums.

I think, it is O(M*N). You need log(N) comparisons to find the position for
inserting a new element into the vector of N, but on average you need N/2
move operations (andN in the worst case) to perform the insertion into the
correct slot. It's like insertion sort with binary search.

A solution of O(M*log(N)) complexity can be achieved by using a multiset<>
instead of a vector<> to hold the N biggest elements. Just insert any new
element and whenever the size grows beyong N, pop off the lowest element.

Come to think of it, a priority_queue might be better than a multiset, but
that appears to be an implementation detail.

This is better than O(M*log
(M)) which would be needed for sorting the whole initial container, if N
<M. If N>=M, then you already have the answer ready anyway.

Best,

Kai-Uwe Bux

 

[Noah Roberts]

Hello,

I've got a std::map<std::string, std::size_t>. How can I extract the
n-th biggest elements. For example:
the map: map["a"] = 5, map["b"] = 5, map["c"] = 7, map["d"] = 10,
map["e"] = 10

I would like to get a map only with (n=3)
newmap["e"] = 10
newmap["d"] = 10
newmap["c"] = 7

I need only the key values, also a std::vector with ("e", "d", "c") can
be the result.

Looks like a basic max algorithm to me.

std:air<std::string,std::size_t> is going to be the value type of
your map if you iterate it. Should be fairly straight forward from there.

I'm a little bit suprised, because If i get the max of my elements n
times, I'll get only the max. Normally I must sort the map and cut the
n-th max elements (upper or lower bounded elements) or get n times the
max and remove after each run the max element from my map.

But on a std::map I can't sort the data on the value part, so I must
copy the std::map to a multimap, sort and cut. So my question is now:
Can I do it on a std::map without a lot of runs over the map?

Sorry, I'm a little bit confused.

Well, standard max algorithm works something like so:

current_max := first;
for first+1 to end do
if current_elem > current_max then current_max := current_elem;
end for

result := current_max;

With a map, current_element is a pair<key,value>. You seem to be
looking for those keys that have the largest value. You can iterate a
map, looking at each of its pairs, and compare accordingly. The
addition of the top3 thing is just another variation of the theme.

Doing it this way of course is linear but doesn't require sorting.
Would depend on how many times you do it vs. how many times you'd have
to sort to decide whether to use such an algorithm or not.

 

[Paul Rubin]

I would like to get a map only with (n=3)
newmap["e"] = 10
newmap["d"] = 10
newmap["c"] = 7

If the map is large and n is small, you should probably use a priority
queue rather than sorting. Use the function

http://en.cppreference.com/w/cpp/algorithm/make_heap

to make a heap, then call

http://en.cppreference.com/w/cpp/algorithm/pop_heap

n times to get the n biggest elements.

Complexity should be O(N * log M) where M is the size of the
map. That is better than O(M * log M) if M is much larger than N.

 

[guinness.tony]

Hello,

I've got a std::map<std::string, std::size_t>. How can I extract the
n-th biggest elements. For example:
the map: map["a"] = 5, map["b"] = 5, map["c"] = 7, map["d"] = 10, map["e"] = 10

I would like to get a map only with (n=3)
newmap["e"] = 10
newmap["d"] = 10
newmap["c"] = 7

I need only the key values, also a std::vector with ("e", "d", "c") can
be the result.

There's a standard-library algorithm for doing just such a job (the
std::nth_element() function template). Your requirement for selection
based on values (rather than keys) requires an extra level of indirection,
as pointed out by other replies, and my favourite of those suggestions is
to manipulate a set of copies of iterators into the map and then retrieve
the keys of those that meet your criterion.

So here's my solution:

#include <map>
#include <vector>
#include <algorithm>

template<typename map_iter_t>
struct compare_map_iters_by_value
{
bool operator()(map_iter_t const a, map_iter_t const b) const
{
return a->second < b->second;
}
};

template<typename map_t>
std::vector<typename map_t::key_type> const
n_biggest_elements(map_t const& map, std::size_t n)
{
typedef typename map_t::const_iterator map_iter_t;
typedef compare_map_iters_by_value<map_iter_t> compare_t;
typedef std::vector<map_iter_t> map_iters_t;

// make a list of iterators into the map

map_iters_t map_iters;
map_iters.reserve(map.size());

for (map_iter_t p = map.begin(); p != map.end(); ++p)
{
map_iters.push_back(p);
}

// arrange for just the last n items to be the largest-valued ones
// (this should be significantly quicker than std::sort() and friends)

std::nth_element(map_iters.begin(),
map_iters.end() - n,
map_iters.end(),
compare_t());

// extract the keys for those largest n items

std::vector<typename map_t::key_type> results;
results.reserve(n);

for (typename map_iters_t::const_iterator p = map_iters.end(); n > 0; --n)
{
results.push_back((*--p)->first);
}

return results;
}