3

为什么可以定义 vector::iterator 到 int 的映射，但不能定义 list::iterator 到 int 的映射？

#include <vector>
#include <list>
#include <map>
#include <algorithm>
using namespace std;


int main()
{
    int ia[] = {1,2,3,4,5,6,7,8,9,0};

    vector<int> v(begin(ia), end(ia));
    auto it1 = find(begin(v), end(v), 4);
    map< vector<int>::const_iterator, int > m1;
    m1.insert(map<vector<int>::const_iterator, int>::value_type(it1,*it1));

    list<int> l(begin(ia), end(ia));
    auto it2 = find(begin(l), end(l),5);
    map< list<int>::const_iterator, int> m2;
    m2.insert(map<list<int>::const_iterator, int>::value_type(it2,*it2)); //doesn't compile

}

错误 1 ​​错误 C2678：二进制“<”：未找到采用“const std::_List_const_iterator<_Mylist>”类型的左侧操作数的运算符（或没有可接受的转换）

4

3 回答 3

5

std::map要求密钥具有可比较性，可以使用<或提供的比较器。

从概念上讲，随机访问迭代器是可比较的，但双向迭代器不是。std::vector迭代器是随机访问的，std::list迭代器是双向的。

因此，您的列表迭代器不满足std::map键类型的类似要求。如果您提供一个比较器，它可以有效地决定哪个std::list::const_iterator应该在另一个之前，您可以将它传递给地图，这将起作用。粗略的草图：

struct ListIterCmp {
    bool operator() (list<int>::const_iterator a, list<int>::const_iterator b)
    {
        // how?
    }
};
map< list<int>::const_iterator, int, ListIterCmp> m2;
// this should work now...

cppreference文档涵盖了我以前使用旧SGI文档的所有内容，并且仍在更新。看到它们都描述a<b了 RandomAccessIterator，而不是 BidirectionalIterator 概念。

于 2012-10-06T20:11:01.280 回答
4

您不能比较来自std::list<T>任何 T 的迭代器。事实上，std::vector<T>::iterator只有当所讨论的两个迭代器都来自同一个向量时，它才具有可比性。

于 2012-10-06T20:00:20.973 回答
0

您无法比较std::list迭代器的原因是它的效率非常低 - 您可能必须从其中一个走到整个列表的末尾才能发现另一个元素不在它之后。那将是O(N)复杂性，对于像<.

我不能建议更换，因为我不知道你需要它。因为std::list' 元素的地址是稳定的，所以您可以将地址用作 a 的键map。但我看不出这会有什么用。

于 2012-10-06T20:06:32.543 回答