Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   std::map get n max elements (http://www.velocityreviews.com/forums/t747441-std-map-get-n-max-elements.html)

 Philipp Kraus 04-27-2011 07:24 PM

std::map get n max elements

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 04-27-2011 07:29 PM

Re: std::map get n max elements

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::pair<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.

--
http://crazycpp.wordpress.com

 Philipp Kraus 04-27-2011 08:29 PM

Re: std::map get n max elements

On 2011-04-27 21:29:04 +0200, Noah Roberts said:

> 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::pair<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 04-27-2011 09:32 PM

Re: std::map get n max elements

Paavo Helde wrote:

> Philipp Kraus <philipp.kraus@flashpixx.de> wrote in news:ip9uam\$704\$1
> @online.de:
>
>> On 2011-04-27 21:29:04 +0200, Noah Roberts said:
>>
>>> 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::pair<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::pair
> <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

Best,

Kai-Uwe Bux

 Noah Roberts 04-27-2011 09:37 PM

Re: std::map get n max elements

On 4/27/2011 1:29 PM, Philipp Kraus wrote:
> On 2011-04-27 21:29:04 +0200, Noah Roberts said:
>
>> 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::pair<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.

--
http://crazycpp.wordpress.com

 Paul Rubin 12-07-2012 07:50 AM

Re: std::map get n max elements

Philipp Kraus <philipp.kraus@flashpixx.de> writes:
> 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@gmail.com 12-10-2012 09:27 AM

Re: std::map get n max elements

On Wednesday, April 27, 2011 8:24:53 PM UTC+1, 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.

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

 All times are GMT. The time now is 10:30 AM.