Проверьте, принадлежит ли итератор списку

Есть ли способ проверить, принадлежит ли данный итератор данному списку в С++?

Ответы

Ответ 1

Очевидный, но недействительный подход

Вы не можете просто перебирать список, сравнивая каждое значение итератора с вашим "кандидатом".

Стандарт С++ 03 смутно относится к действительности ==, примененной к итераторам из разных контейнеров (комментарий Mankarse для ответов Nawaz http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2948.html#446), некоторые компиляторы (например, режим отладки VС++ 2005) предупреждают, если вы это сделаете, но, несмотря на все это, он может действительно надежно работать в зависимости от вашего компилятора/библиотек - проверьте его документацию, если вам все равно, портативность.

Стандарт С++ 11 очень явный, вы не можете сравнивать итераторы с различными контейнерами:

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

Итак, ответы на этот вопрос, которые полагаются на operator==, сейчас сомнительны и недействительны в будущем.

Неоднозначный подход

Что вы можете сделать, так это перебирать список по списку, сравнивая адрес элементов (т.е. &*i) с адресом объекта, к которому относятся другие ваши точки.

  • Комментарий Mankarse предупреждает, что это может не работать как предназначено для объектов, предоставляющих свои собственные operator&. Вы можете обойти это, используя std::addressof, или для С++ 03 повысить версию

  • В комментарии Мартина вам следует предположить, что итератор-кандидат, на котором вы тестируете членство в списке, безопасно разыскивается, то есть не равен итератору end() в контейнере, из которого он пришел. Как указывает Стив, это довольно разумное предварительное условие и никого не должно удивлять.

(Это нормально для всех стандартных контейнеров, поскольку сохраненные элементы никогда не имеют одного и того же адреса, но более общие пользовательские контейнеры могут позволить неравным итераторам обращаться к одному и тому же объекту значений (например, поддерживающие циклы или стиль "мухи" ) оптимизация), и в этом случае этот подход потерпит неудачу. Однако, если вы напишете такой контейнер, вы, вероятно, сможете разработать безопасное сравнение итераторов.)

Реализация:

template <class IteratorA, class IteratorB, class IteratorC>
inline bool range_contains(IteratorA from, const IteratorB& end,
                           const IteratorC& candidate)
{
    while (from != end)
        if (&*from++ == &*candidate)
            return true;
    return false;
}

Примечания:

  • Это использует стандартный библиотечный подход для принятия диапазона позиций итератора для поиска.
  • Типы каждого итератора могут меняться, поскольку есть проблемы с переносимостью, например. контейнеры, где begin() возвращает iterator, но end() возвращает a const_iterator.
  • Итераторы, отличные от from, берутся с помощью ссылки const, поскольку итераторы иногда могут быть нетривиальными объектами (т.е. слишком большими, чтобы вписаться в регистр, относительно дорогостоящий для копирования). from требуется по значению, поскольку он будет увеличиваться в диапазоне.