使用std::string作为键的std::map的排序

Question

我有一个 std::map mymap

现在，如果我想向这个 map 中插入值：

std::map <string, string> mymap;
mymap["first"] = "hi";
mymap["third"] = "how r you";
mymap["second"] = "hello";

现在我想遍历这个map并按照sorted(keys)的方式打印出对应的value值:

map<string, string>::iterator itr;
for(itr = mymap.begin(); itr != mymap.end(); itr++)
{
   string newline = itr->second;
   cout << newline << endl;
}

输出应该是：

hi 
hello 
how r you 

我认为默认情况下，map会按照排序键的方式存储，但是我得到的输出顺序与我输入的顺序相同。我需要为此提供自己的排序函数，还是在迭代map之前需要做其他额外的事情？

- Ruchi

---

for循环引用了file_line而不是mymap。我理解这不是实际的代码，因为在填充mymap时没有将first加入引号中。 - hmjd

我不太确定C++的std::map实现，但这样的哈希表通常不会被排序。它们是通过索引器访问的，而不是遍历访问的。 - Gigi

@user983064 std::map是一种按键排序的二叉树。 C++11具有哈希表，例如std::unordered_map。 - juanchopanza

Answer 1

std::map中的元素（默认情况下）按应用于键的operator<排序。

您发布的代码，经过小幅修改，像您期望的那样正常工作：

std::map <string, string> mymap;
mymap["first"]="hi";
mymap["third"]="how r you";
mymap["second"]="hello";

for (std::map<string, string>::iterator i = mymap.begin(); i != mymap.end(); i++)
{
    cout << i->second << "\n";
}

输出:

hi
hello
how r you

- hmjd

---

嗯...那么"fourth"怎么办呢？它应该在"first"之后还是"third"之后？也许他需要自定义比较谓词... - Emilio Garavaglia

@EmilioGaravaglia，是的，他可以使用int作为键。 - hmjd

auto？这个问题没有被标记为 [tag:C++11]。 - juliomalegria

@julio.alegria，这是给你的。 - hmjd

这是关于之前回答的跟进问题，for (std::map<string, string>::iterator i = mymap.begin(); i != mymap.end(); i++) 和 for (std::map<string, string>::iterator i = mymap.begin(); i != mymap.end(); ++i) 有什么区别？其中迭代器在之前而不是之后递增。 - Moses Kirathe

@MosesKirathe 前者在每次迭代的“末尾”将i增加1，而后者在每次迭代的“开头”将i增加1。 - David Lee

Answer 2

map实际上是一棵红黑树，并按照键的顺序进行排序。您正在打印itr->second，这是值而不是键。如果您想按值对键值对进行排序，请使用值作为键，或将所有内容存储在另一个容器中（例如数组），然后进行排序。

- Giovanni Funchal

---

你说的是正确的，所以KEYS是："first" < "second" < "third"，因此我们应该期望与OP所说的相同结果：hi | hello | how r you，但他说：_我得到的输出顺序与我输入的顺序相同_，即：hi | how r you | hello。 - juliomalegria

Answer 3

std::map已经有序。如果您使用unordered_map，那么您现在可能会遇到问题！

std::map中的条目按键或itr->first排序。而itr->second则是指与键相关联的值。

另外，您并不是在迭代map，而是在迭代file_line（我不知道它是什么，但我假设它与mymap不同。这就是您应该迭代的对象）。

- MGZero

Answer 4

该标准定义了以下内容：

迭代器的基本属性是它们按照键的非降序遍历关联容器，其中“非降序”由用于构造它们的比较操作定义。

- Shawnone