迭代 std::map 的顺序是否已知(并由标准保证)?
我的意思是 - 我们知道 std::map 的元素是根据键排序的.所以，假设键是整数.如果我使用 for 从 std::map::begin() 迭代到 std::map::end()，标准保证我将因此迭代带有键的元素，按升序排序?
What I mean is - we know that the std::map's elements are sorted according to the keys. So, let's say the keys are integers. If I iterate from std::map::begin() to std::map::end() using a for, does the standard guarantee that I'll iterate consequently through the elements with keys, sorted in ascending order?
示例:
std::map<int, int> map_;
map_[1] = 2;
map_[2] = 3;
map_[3] = 4;
for( std::map<int, int>::iterator iter = map_.begin();
iter != map_.end();
++iter )
{
std::cout << iter->second;
}
这是否保证打印 234 或者它是实现定义的?
Is this guaranteed to print 234 or is it implementation defined?
现实生活中的原因:我有一个带有 int 键的 std::map.在极少数情况下，我想使用大于具体 int 值的键遍历所有元素.是的，听起来 std::vector 是更好的选择，但请注意我的非常罕见的情况".
Real life reason: I have a std::map with int keys. In very rare situations, I'd like to iterate through all elements, with key, greater than a concrete int value. Yep, it sounds like std::vector would be the better choice, but notice my "very rare situations".
EDIT:我知道，std::map 的元素已排序......无需指出(对于这里的大多数答案).我什至在我的问题中写了它.
我在遍历容器时询问了迭代器和顺序.感谢@Kerrek SB 的回答.
EDIT: I know, that the elements of std::map are sorted.. no need to point it out (for most of the answers here). I even wrote it in my question.
I was asking about the iterators and the order when I'm iterating through a container. Thanks @Kerrek SB for the answer.
推荐答案
是的，这是有保证的.此外，*begin() 为您提供由比较运算符确定的最小元素和 *rbegin() 最大元素，以及两个键值 a 和 b 其中表达式 !compare(a,b) &&!compare(b,a) 为真被认为是相等的.默认的比较函数是std::less.
Yes, that's guaranteed. Moreover, *begin() gives you the smallest and *rbegin() the largest element, as determined by the comparison operator, and two key values a and b for which the expression !compare(a,b) && !compare(b,a) is true are considered equal. The default comparison function is std::less<K>.
排序不是幸运的奖励功能，而是数据结构的一个基本方面，因为排序用于确定两个键何时相同(通过上述规则)并执行有效的查找(本质上是一种二分查找，其元素数量具有对数复杂性).
The ordering is not a lucky bonus feature, but rather, it is a fundamental aspect of the data structure, as the ordering is used to determine when two keys are the same (by the above rule) and to perform efficient lookup (essentially a binary search, which has logarithmic complexity in the number of elements).
相关文章