c++ - 如何在 C++ 中比较两个映射迭代器？

Question

#include <iostream>
#include<vector>
#include<map>
using namespace std;
int main() {
   vector<int> v1{1,2,3,4,5};
    auto it1 = v1.begin();
    auto it2 = v1.end();
    if(it1<it2){
        cout<<"TRUE"<<endl;             // Output: TRUE
    }

    map<int,int> m;
    m.insert(make_pair(1,2));
    m.insert(make_pair(5,7));
    auto it3 = m.begin();
    auto it4 = m.end();
    if(it3<it4){
        cout<<"TRUE"<<endl;           
    }   
    /*
    error: no match for 'operator<' (operand types are 'std::_Rb_tree_iterator<std::pair<const int, int> >' and 'std::_Rb_tree_iterator<std::pair<const int, int> >')
   18 |     if(it3<it4){
      |        ~~~^~~~
    */

}

Line (it1

Answer 1

Line (it1<it2) works fine when using vector but (it3<it4)

vector 迭代器是随机访问迭代器。可以比较随机访问迭代器的顺序。

but (it3<it4) does not work when using map?

Map 迭代器不是随机访问迭代器。它们无法进行顺序比较。

但是，如果您知道映射的比较器，则可以间接通过两个迭代器，并将键与比较器进行比较。您必须首先检查结束迭代器，因为您无法从中获取 key (但您知道它在所有其他迭代器之后)。这仅适用于有序映射，例如 std::map。它不适用于 HashMap ，例如 std::unordered_map。它也不会找出两个迭代器与多映射中相同元素的相对顺序。

一般来说，给定一对前向迭代器和结束迭代器，您可以通过从一个迭代器开始进行线性搜索来找到这对迭代器，直到找到第二个迭代器或容器的末尾。如果在 other 迭代器之前找到 end，则 other 在前；如果您确实找到了另一个迭代器，那么它就在后面。这当然具有线性最坏情况的复杂性。