вектор & lt; int & gt; :: итератор и список & lt; int & gt; :: итератор ключей в std :: map

Question

вектор & lt; int & gt; :: итератор и список & lt; int & gt; :: итератор ключей в std :: map

Почему карта 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> ‘(или нет приемлемого преобразования)

3

c++stdmap

Решение

Другие решения

Вы не можете сравнивать итераторы из std::list<T> для любого Т. Действительно, std::vector<T>::iterator сопоставимо только в том случае, если оба рассматриваемых итератора происходят из одного и того же вектора.

4

Причина, по которой вы не можете сравнить std::list Итераторы в том, что это было бы крайне неэффективно — вам нужно было бы пройти от одного из них, возможно, до конца всего списка, просто чтобы найти другой элемент не за ним. Это было бы O(N) сложность, которую мы не хотим для простых операций, таких как <,

Я не могу предложить замену, так как не знаю, для чего она вам нужна. Потому что адреса std::listэлементы стабильны, вы можете использовать адреса в качестве ключей для map, Но я не понимаю, как это было бы полезно.

0

Источник

Accepted Answer

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.

5