1
set<string> myFunc (const map<string, vector<string>>& m)

I want to return all the keys in a set of strings, that map the most values (several keys if number of mapped values is the same). My attempt was:

set<string> ret;
auto max_e = *max_element(m.begin(), m.end(), [] (const pair<string, vector<string>>& m1, const pair<string, vector<string>>& m2) {
    return m1.second.size() < m2.second.size();
  });
ret.insert(max_e.first);
return ret;

Logically, this cannot work (I think) since this would only return one key with the highest value. Any ideas?

smat
  • 11
  • 1
  • 2
    Find the _size_ of the largest element instead of the largest element itself, then you can add all elements with that size – Nick is tired Feb 04 '21 at 13:01

2 Answers2

1

One way of doing it would be iterating twice:

  • 1st one to get the maximum size out of all keys.
  • 2nd one to get the keys that map to that size.

It should look along the lines of:

set <string> myFunc(const map<string, vector<string>>& m) {
    set <string> ret;
    size_t maximumSize = 0;
    for (const auto& e : m) {
        maximumSize = max(maximumSize, e.second.size());
    }
    for (const auto& e : m) {
        if (e.second.size() == maximumSize) {
            ret.insert(e.first);
        }
    }
    return ret;
}
DarthQuack
  • 1,254
  • 3
  • 12
  • 22
  • You could do with only 1 iteration - Whenever you find an element with a bigger key, reset your result set, add the current, then proceed. – BitTickler Feb 04 '21 at 13:13
  • @BitTickler True, although I think resetting the result set multiple times would be a bit expensive as `set.clear()` is [linear in size](http://www.cplusplus.com/reference/set/set/clear/). I'm not sure if OP cares about performance though. – DarthQuack Feb 04 '21 at 13:20
  • I solved it using only one iteration, thank you all! – smat Feb 04 '21 at 13:47
1

In addition to @a.Li's answer, if possible, you can also optimize quite a few things along the way.

Of course, iterating the map twice is probably the least expensive & simple way of solving the issue:

using StringMapType = std::map<std::string, std::vector<std::string>>;
using StringMapVectorType = StringMapType::value_type::second_type;

std::set<StringMapType::key_type> findKeys(const StringMapType &stringMap) {
    StringMapVectorType::size_type maximumSize {};
    for (const auto &[key, values] : stringMap)
        maximumSize = std::max(maximumSize, values.size());
    
    std::set<StringMapType::key_type> results {};
    for (const auto &[key, values] : stringMap)
        if (values.size() == maximumSize)
            results.emplace(key);
    
    return results;
}

However, I would recommend the following, if possible:

  • if you aren't interested in ordering the keys in your map type, use std::unordered_map,
  • replace the return value type (std::set with std::vector, if you aren't interested in the order of the keys stored in the results.

Object lifetime specific optimizations:

  • use std::string_view for the keys you find; this will avoid additional copies of the strings, assuming they aren't optimized out with short string optimization,
  • return an array of iterators, instead of their keys

If applied, the code could look something like this:

    std::vector<StringMapType::const_iterator> findKeys(const StringMapType &stringMap) {
        StringMapVectorType::size_type maximumSize {};
        for (const auto &[key, values] : stringMap)
            maximumSize = std::max(maximumSize, values.size());
        
        std::vector<StringMapType::const_iterator> results {};
        for (auto iterator = stringMap.cbegin(); iterator != 
             stringMap.cend(); ++iterator)
            if (const auto &values = iterator->second;
                values.size() == maximumSize)
                results.emplace_back(iterator);
        
        return results;
    }

Of course, if you'd like to avoid the whole issue, you can instead sort your values at the time of insertion using a custom comparator, or find the the entry with the most amount of elements in its array, and insert the new entry before it (of course, you'd have to use an unordered map, or another container).

Useful things for the future:

Tim
  • 31
  • 2