迭代器（std::map）在 C++ 中是如何工作的？

Question

我尝试运行以下代码：

std::map < std::string, std::string > m;
m[ "one" ] = "0";
m[ "two" ] = "1";
m[ "three" ] = "2";
m[ "four" ] = "3";

auto it = m.begin();
std::cout << it->first << "\n";

输出为："four"。但是为什么要从末尾开始呢？我被期待 "one"!

Answer 1

原因是 std::map is a sorted container. It sorts its elements, which are key-value pairs, according to the key, which is std::string 在您的特定情况下。

然后，字符串按字典顺序相互比较。由于字符串 four 是所有字符串中最小的一个，所以对 ("four", "3") 成为第一对。所以 begin() returns 指向这一对的迭代器。

Answer 2

我不确定，但我认为 std::map 对关键元素进行排序以便快速搜索。（我相信它使用二进制搜索）。如果您不想更改顺序，则必须使用 std::vector 或 std::list 或 std::deque 之类的东西。

迭代器（std::map）在 C++ 中是如何工作的？

How does exactly iterator (of std::map) works in C++?

c++

dictionary

iterator

std