查找映射字符串、矢量中值最多的键<string><>

Question

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

我想返回一组字符串中映射最多值的所有键(如果映射值的数量相同，则为几个键)。我的尝试是:

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;

逻辑上，这是行不通的(我认为)，因为这只会返回一个值最高的键。什么好主意吗?

Answer 1

一种方法是迭代两次:

• 第一个从所有键中获得最大大小的键。
• 第二个获取映射到该大小的键。

看起来应该像这样:

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

Answer 2

除了@a。李的回答是，如果可能的话，你还可以在此过程中优化相当多的东西。

当然，迭代两次映射可能是最便宜的方法&解决问题的简单方法:

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

但是，如果可能的话，我还是建议你这样做:

• 如果您对map类型中的键排序不感兴趣，请使用std::unordered_map，
• 如果您对存储在结果中的键的顺序不感兴趣，则将返回值类型(std::set)替换为std::vector。

对象生命周期特定优化:

• 使用std::string_view的键找到;这将避免额外的字符串副本，假设他们没有优化短字符串优化，
• 返回迭代器数组，而不是它们的键

如果应用，代码看起来像这样:

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

当然，如果您想避免整个问题，您可以在插入时使用自定义比较器对值进行排序，或者找到其数组中元素数量最多的条目，并在其之前插入新条目(当然，您必须使用无序映射或其他容器)。

对未来有用的东西:

• 在哪种情况下我使用特定的STL容器?