Re: std::map get n max elements
On 27/04/2011 21:32, Leigh Johnston wrote:
On 27/04/2011 21:29, 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?
I can think of two solutions:
1) copy map iterators into a vector and sort that;
2) use Boost.Bimap instead.
Actually I have a third solution which I *think* would be more efficient
than the vector solution:
int main()
{
typedef std::map<std::string, std::size_t> data_t;
data_t data;
data["a"] = 10;
data["b"] = 5;
data["c"] = 10;
data["d"] = 2;
data["e"] = 7;
typedef std::multimap<std::size_t, data_t::const_iterator> top3_t;
top3_t top3;
for (data_t::const_iterator i = data.begin(); i != data.end(); ++i)
{
if (top3.size() < 3 || i->second > top3.begin()->first)
top3.insert(std::make_pair(i->second, i));
if (top3.size() == 4)
top3.erase(top3.begin());
}
std::cout << "top 3" << std::endl;
for (top3_t::const_iterator i = top3.begin(); i != top3.end(); ++i)
std::cout << "[\"" << i->second->first << "\"] = " <<
i->second->second << std::endl;
}
std::cout << "[\"" << i->second->first << "\"] = " <<
i->second->second << std::endl;
}
I just knocked this up in 10 minutes so no guarantees... :)
/Leigh