45

我需要std::map按值排序，然后按键。该地图包含如下数据：

  1  realistically
  8         really
  4         reason
  3     reasonable
  1     reasonably
  1     reassemble
  1    reassembled
  2      recognize
 92         record
 48        records
  7           recs

我需要按顺序获取值，但更重要的是，在值按顺序排列之后，键需要按字母顺序排列。我怎样才能做到这一点？

4

5 回答 5

68

std::map将对其元素进行排序keys。它不关心values何时排序。

您可以使用std::vector<std::pair<K,V>>然后使用std::sort后跟对其进行排序std::stable_sort：

std::vector<std::pair<K,V>> items;

//fill items

//sort by value using std::sort
std::sort(items.begin(), items.end(), value_comparer);

//sort by key using std::stable_sort
std::stable_sort(items.begin(), items.end(), key_comparer);

第一种应该使用，std::sort因为它是，nlog(n)然后在最坏的情况下使用。std::stable_sortn(log(n))^2

请注意，std::sort选择虽然是出于性能原因，但std::stable_sort需要正确排序，因为您希望保留按值排序。

@gsf 在评论中指出，只有 std::sort当您选择一个首先比较的比较器时才能使用values，如果它们相等，则对keys.

auto cmp = [](std::pair<K,V> const & a, std::pair<K,V> const & b) 
{ 
     return a.second != b.second?  a.second < b.second : a.first < b.first;
};
std::sort(items.begin(), items.end(), cmp);

那应该是有效的。

但是等等，有一个更好的方法：存储std::pair<V,K>而不是std::pair<K,V>然后你根本不需要任何比较器 - 标准比较器std::pair就足够了，因为它首先比较first（这是V）然后second是K：

std::vector<std::pair<V,K>> items;
//...
std::sort(items.begin(), items.end());

那应该很好用。

于 2013-11-07T17:03:38.690 回答
16

您可以使用std::set而不是std::map.

您可以同时存储键和值std::pair，容器的类型将如下所示：

std::set< std::pair<int, std::string> > items;

std::set将按原始键和存储在std::map.

于 2013-11-07T17:34:00.273 回答
2

正如Nawaz 的 回答中所解释的，您无法根据需要自行对地图进行排序，因为std::map仅根据键对其元素进行排序。所以，你需要一个不同的容器，但如果你必须坚持你的地图，那么你仍然可以将其内容（临时）复制到另一个数据结构中。

我认为，最好的解决方案是使用std::set存储翻转的键值对，如ks1322 的 答案中所示。std::set默认情况下已排序，并且对的顺序完全符合您的需要：

3) 如果lhs.first<rhs.first，则返回true。否则，如果rhs.first<lhs.first，则返回false。否则，如果lhs.second<rhs.second，则返回true。否则，返回false。

这样您就不需要额外的排序步骤，并且生成的代码很短：

std::map<std::string, int> m;  // Your original map.
m["realistically"] = 1;
m["really"]        = 8;
m["reason"]        = 4;
m["reasonable"]    = 3;
m["reasonably"]    = 1;
m["reassemble"]    = 1;
m["reassembled"]   = 1;
m["recognize"]     = 2;
m["record"]        = 92;
m["records"]       = 48;
m["recs"]          = 7;

std::set<std::pair<int, std::string>> s;  // The new (temporary) container.

for (auto const &kv : m)
    s.emplace(kv.second, kv.first);  // Flip the pairs.

for (auto const &vk : s)
    std::cout << std::setw(3) << vk.first << std::setw(15) << vk.second << std::endl;

输出：

  1  realistically
  1     reasonably
  1     reassemble
  1    reassembled
  2      recognize
  3     reasonable
  4         reason
  7           recs
  8         really
 48        records
 92         record

Ideone 上的代码

注意：从C++17 开始，您可以使用基于范围的 for 循环和结构化绑定来迭代地图。结果，用于复制地图的代码变得更短且更具可读性：

for (auto const &[k, v] : m)
    s.emplace(v, k);  // Flip the pairs.
于 2019-03-28T15:48:43.767 回答
1

std::map已经使用您定义的谓词对值进行了排序，或者std::less如果您不提供一个谓词。 std::set还将按照定义比较器的顺序存储项目。但是 set 和 map 都不允许您拥有多个键。std::map<int,std::set<string>如果您想单独使用数据结构来完成此操作，我建议您定义一个。您还应该意识到std::lessfor string 将按字典顺序而不是按字母顺序排序。

于 2013-11-07T17:07:22.127 回答
0

编辑：其他两个答案说得很好。我假设您想将它们订购到其他结构中，或者为了打印出来。

“最佳”可能意味着许多不同的东西。你的意思是“最简单”、“最快”、“最高效”、“最少代码”、“最易读”吗？

最明显的方法是循环两次。在第一遍中，对值进行排序：

if(current_value > examined_value)
{
    current_value = examined_value
    (and then swap them, however you like)
}

然后在第二遍时，按字母顺序排列单词，但前提是它们的值匹配。

if(current_value == examined_value)
{
    (alphabetize the two)
}

严格来说，这是一种“冒泡排序”，速度很慢，因为每次进行交换时，都必须重新开始。当您通过整个列表而不进行任何交换时，一个“通过”就完成了。

还有其他排序算法，但原理相同：按值排序，然后按字母顺序排列。

于 2013-11-07T17:09:24.740 回答