std::map get n max elements

Discussion in 'C++' started by Philipp Kraus, Apr 27, 2011.

  1. 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
    Philipp Kraus, Apr 27, 2011
    #1
    1. Advertising

  2. Philipp Kraus

    Noah Roberts Guest

    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
    Noah Roberts, Apr 27, 2011
    #2
    1. Advertising

  3. 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.
    Philipp Kraus, Apr 27, 2011
    #3
  4. Philipp Kraus

    Kai-Uwe Bux Guest

    Paavo Helde wrote:

    > Philipp Kraus <> 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
    > <M. If N>=M, then you already have the answer ready anyway.


    Best,

    Kai-Uwe Bux
    Kai-Uwe Bux, Apr 27, 2011
    #4
  5. Philipp Kraus

    Noah Roberts Guest

    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
    Noah Roberts, Apr 27, 2011
    #5
  6. Philipp Kraus

    Paul Rubin Guest

    Philipp Kraus <> 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.
    Paul Rubin, Dec 7, 2012
    #6
  7. Philipp Kraus

    Guest

    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;
    }
    , Dec 10, 2012
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter Jansson
    Replies:
    5
    Views:
    6,276
    Ivan Vecerina
    Mar 17, 2005
  2. puzzlecracker
    Replies:
    3
    Views:
    1,752
    Mike Wahler
    May 8, 2006
  3. Replies:
    1
    Views:
    409
    red floyd
    Dec 21, 2008
  4. Thomas J. Gritzan
    Replies:
    6
    Views:
    1,001
    James Kanze
    Dec 22, 2008
  5. James Kanze
    Replies:
    0
    Views:
    1,985
    James Kanze
    Dec 21, 2008
Loading...

Share This Page