問題描述

我的意思是 - 我們知道 std::map 的元素是根據(jù)鍵排序的.所以，假設(shè)鍵是整數(shù).如果我使用 for 從 std::map::begin() 迭代到 std::map::end()，標(biāo)準(zhǔn)保證我將因此迭代帶有鍵的元素，按升序排序?

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 或者它是實現(xiàn)定義的?

Is this guaranteed to print 234 or is it implementation defined?

現(xiàn)實生活中的原因:我有一個帶有 int 鍵的 std::map.在極少數(shù)情況下，我想使用大于具體 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 的元素已排序......無需指出(對于這里的大多數(shù)答案).我什至在我的問題中寫了它.
我在遍歷容器時詢問了迭代器和順序.感謝@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 其中表達(dá)式 !compare(a,b) &&!compare(b,a) 為真被認(rèn)為是相等的.默認(rèn)的比較函數(shù)是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>.

排序不是幸運的獎勵功能，而是數(shù)據(jù)結(jié)構(gòu)的一個基本方面，因為排序用于確定兩個鍵何時相同(通過上述規(guī)則)并執(zhí)行有效的查找(本質(zhì)上是一種二分查找，其元素數(shù)量具有對數(shù)復(fù)雜性).

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).

這篇關(guān)于迭代 std::map 的順序是否已知(并由標(biāo)準(zhǔn)保證)?的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網(wǎng)！