сравнивая итераторы из разных контейнеров

Question

Законно ли сравнивать итераторы из разных контейнеров?

std::vector<int> foo;
std::vector<int> bar;

Дает ли выражение foo.begin() == bar.begin() ложное или неопределенное поведение?

(Я пишу собственный итератор и наткнулся на этот вопрос при реализации operator==.)

Answer 1

Если вы считаете стандарт C ++ 11 (n3337):

& секта; 24.2.1 & mdash; [Iterator.requirements.general # 6]

Итератор j называется достижимым из итератора i тогда и только тогда, когда существует конечная последовательность применений выражения ++i, которая составляет i == j. Если j достижимо из i, они относятся к элементам той же последовательности.

& секта; 24.2.5 - [Forward.iterators # 2]

Область == для прямых итераторов - это область итераторов в одной и той же базовой последовательности.

Учитывая, что RandomAccessIterator должен удовлетворять всем требованиям, установленным ForwardIterator, сравнение итераторов из разных контейнеров не определено.

В выпуске LWG # 446 конкретно говорится об этом вопросе, и было предложено добавить следующий текст в стандарт (спасибо @ Lightness Races на орбите за доведение его до внимание):

Результат прямой или косвенной оценки любой функции сравнения или бинарного оператора с двумя значениями итератора в качестве аргументов, которые были получены из двух различных диапазонов r1 и r2 (включая их последние значения) , которые не являются поддиапазоны одного общего диапазона не определены, если явно не указано иное .

Answer 2

Неопределенное поведение, насколько я знаю. В VS 2010 с

/*
* to disable iterator checking that complains that the iterators are incompatible (come from * different containers :-)
*/
#define _HAS_ITERATOR_DEBUGGING 0 

std::vector<int> vec1, vec2;

std::vector<int>::iterator it1 = vec1.begin();
std::vector<int>::iterator it2 = vec2.begin();

if (it1 == it2)
{
std::cout << "they are equal!!!"; 
}

Тест на равенство возвращает в этом случае значение true :-), поскольку контейнеры пусты и оба члена итератора _Ptr равны nullptr.

Кто знает, может быть, ваша реализация работает по-другому, и тест выдаст false: -).

EDIT:

См. Список активных проблем стандартной библиотеки C ++"446. Равенство итераторов между различными контейнерами". Может быть, кто-то может проверить стандарт, чтобы увидеть, было ли изменение принято?

Вероятно, нет, так как он находится в списке активных вопросов, поэтому Чарльз Бейли, который также ответил, что это правильно, это неуказанное поведение.

Так что я думаю, что поведение может отличаться (по крайней мере теоретически) в разных реализациях, и это только одна проблема.

Тот факт, что с включенной отладкой итераторов в реализации STL, которая идет с проверками VS, имеет место для этого точного случая (итераторы, прибывающие из разных контейнеров), по крайней мере для меня еще раз, что следует по возможности избегать таких сравнений.

Answer 3

Вы не можете напрямую сравнивать итераторы из разных контейнеров. Итератор - это объект, который использует внутреннее состояние контейнера для его прохождения; сравнивать внутренности одного контейнера с другим просто не имеет смысла.

Однако, если итераторы, полученные из container.begin(), доступны, может иметь смысл сравнивать итераторы по количеству объектов, пройденных от begin() до текущего значения итератора. Это делается с помощью std::distance:

int a = std::distance(containerA.begin(), iteratorA);
int b = std::distance(containerB.begin(), iteratorB);

if (a <comparison> b)
{ /* ... */ }

Без дополнительного контекста трудно судить, решит ли это вашу проблему или нет. YMMV.

Answer 4

Я считаю, что это неопределенное поведение (C ++ 03).std::vector итераторы являются итераторами с произвольным доступом, и поведение == определено в требованиях для прямых итераторов.

== является отношением эквивалентности

Обратите внимание, чтоэто требование к типу, поэтому оно должно применяться (в данном случае) к любой паре действительных (разыменовываемых или иных) std::vector::iterator s.Я считаю, что это означает, что == должен дать вам ответ true / false и не может вызвать UB.

- Если a и b равны, то либо a, либо bоба - разыменовываемые или иначе - разыменовываемые.

И наоборот, разыменовываемый итератор не может сравниваться равным итератору, который не может быть разыменован.

- Если a и b оба разыменовываются, тогда a == b, если и только если * a и * b - это один и тот же объект.

Обратите внимание на отсутствие требования о a == b для двух итераторов, которые не могут быть разыменованы.Пока == является транзитивным (если a.end() == b.end() и b.end() == c.end(), тогда a.end() == c.end()), рефлексивным (a.end() == a.end()) и симметричным (если a.end() == b.end(), то b.end() == a.end()), не имеет значения, если некоторые, всеили нет end() итераторов для разных контейнеров, сравниваемых равными.

Обратите также внимание, что это в отличие от <.< определяется в терминах b - a, где a и b являются итераторами произвольного доступа.Предварительное условие выполнения b - a заключается в том, что должно быть значение Distance n, такое, что a + n == b, для которого требуется a и b, должны быть итераторами в одном диапазоне.

Answer 5

Нет.Если бы это было законно, это означало бы, что указатели не были бы итераторами.

Answer 6

Я не получаю требования к итераторам ввода от стандартных 100%, но с этого момента (итераторы прямого / двунаправленного / произвольного доступа) нет никаких требований к домену ==, поэтому он должен вернуть false приводит к отношению эквивалентности . Вы не можете делать <или> или вычитать на итераторах из разных контейнеров.

Edit: он не должен возвращать false, он должен привести к отношению эквивалентности, это позволяет .begin() двух пустых контейнеров сравнивать равные (как показано в другом ответе). Если итераторы разыменовываются, a == b => *a == *b должно быть выполнено. Это все еще не неопределенное поведение.

Answer 7

ИСО / МЭК 14882: 2003 (E) 5.10.1

Операторы == (равно) и! = (Не равно) имеют те же семантические ограничения, преобразования и тип результата, что и операторы отношения, за исключением их более низкого приоритета и результата истинности-значения. [..] Указатели на объекты или функции одного типа (после преобразования указателей) можно сравнивать на равенство. Два указателя одного типа сравниваются равными, если и только если они оба равны нулю, оба указывают на одну и ту же функцию или оба представляют один и тот же адрес (3.9.2).

Результаты моделирования на XCode (3.2.3):

#include <iostream>
#include <vector>

int main()
{
    std::vector <int> a,aa;
    std::vector <float> b;

    if( a.begin() == aa.begin() )
        std::cout << "\n a.begin() == aa.begin() \n" ;

    a.push_back(10) ;

    if( a.begin() != aa.begin() )
        std::cout << "\n After push back a.begin() != aa.begin() \n" ;

    // Error if( a.begin() == b.begin() )   

    return 0;
}

Выход:

a.begin () == aa.begin ()
После толчка назад a.begin ()! = Aa.begin ()