Как избежать ловушки const_iterator при передаче ссылки на контейнер const в качестве параметра

Question

Я обычно предпочитаю constness, но недавно натолкнулся на головоломку с константными итераторами, которая потрясает мое отношение к константам раздражает меня о них:

MyList::const_iterator find( const MyList & list, int identifier )
{
    // do some stuff to find identifier
    return retConstItor; // has to be const_iterator because list is const
}

Идея, которую я здесь пытаюсь выразить, конечно же, состоит в том, что переданный список не может быть изменен / не будет изменен, но как только я сделаю ссылку на список const, мне придется использовать 'const_iterator's', который затем мешает мне делает что-нибудь с изменением результата (что имеет смысл).

Является ли решение отказаться от создания переданной ссылки на контейнер const или я упускаю другую возможность?

Это всегда было моей секретной оговоркой о const: даже если вы используете ее правильно, она может создавать проблемы, которых не должно быть, когда нет хорошего / чистого решения, хотя я признаю, что это более конкретно проблема между const и концепция итератора.

Редактировать: Мне очень хорошо известно, почему вы не можете и не должны возвращать неконстантный итератор для константного контейнера. Моя проблема в том, что, хотя я хочу проверить во время компиляции для моего контейнера, который передается по ссылке, я все еще хочу найти способ передать обратно положение чего-либо и использовать его для изменения неконстантной версии списка , Как упомянуто в одном из ответов, возможно извлечь эту концепцию позиции через «продвижение», но грязно / неэффективно.

Answer 1

Если я правильно понимаю, что вы говорите, вы пытаетесь использовать const, чтобы указать вызывающей стороне, что ваша функция не будет изменять коллекцию, но вы хотите, чтобы вызывающий (у которого может быть не * 1002) * ссылка на коллекцию), чтобы иметь возможность изменять коллекцию, используя возвращаемый итератор. Если это так, я не думаю, что есть чистое решение для этого, если только контейнер не предоставляет механизм для превращения const интегратора в не const (я не знаю о контейнере, который делает это). Лучше всего, чтобы ваша функция использовала ссылку не const. Вы также можете иметь 2 перегрузки вашей функции, одну const и одну не const, так что в случае вызывающего абонента, имеющего только ссылку const, они все равно смогут использовать вашу функция.

Answer 2

Это не ловушка; это особенность. (: -)

Как правило, вы не можете вернуть неконстантный «дескриптор» вашим данным из метода const. Например, следующий код недопустим.

class Foo
   {
      public:
         int& getX() const {return x;}
      private:
         int x;
   };

Если бы это было законно, то вы могли бы сделать что-то вроде этого ...

   int main()
   {
      const Foo f;
      f.getX() = 3; // changed value of const object
   }

Разработчики STL следовали этому соглашению с помощью const-итераторов.

---

В вашем случае, то, что const купил бы вам, это возможность вызывать его в коллекциях const. В этом случае вы не хотите, чтобы возвращаемый итератор был изменяемым. Но вы хотите разрешить его изменение, если коллекция неконстантна. Итак, вы можете захотеть два интерфейса:

MyList::const_iterator find( const MyList & list, int identifier )
{
    // do some stuff to find identifier
    return retConstItor; // has to be const_iterator because list is const
}

MyList::iterator find( MyList & list, int identifier )
{
    // do some stuff to find identifier
    return retItor; 
}

Или, вы можете сделать все это с помощью одной функции шаблона

template<typename T>    
T find(T start, T end, int identifier);

Тогда он вернет неконстантный итератор, если входные итераторы неконстантные, и const_iterator, если они константные.

Answer 3

То, что я сделал со стандартными алгоритмами обёртывания, - это метаобъект для определения типа контейнера:

namespace detail
{
    template <class Range>
    struct Iterator
    {
        typedef typename Range::iterator type;
    };

    template <class Range>
    struct Iterator<const Range>
    {
        typedef typename Range::const_iterator type;
    };
}

Это позволяет обеспечить единственную реализацию, например, find:

template <class Range, class Type>
typename detail::Iterator<Range>::type find(Range& range, const Type& value)
{
    return std::find(range.begin(), range.end(), value);
}

Однако это не позволяет называть это временными (я полагаю, я могу жить с этим).

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

Я полагаю, что правильность const - это скорее услуга для вызывающего пользователя ваших функций, а не какая-то мера няни, которая должна гарантировать, что вы правильно понимаете свою простую функцию поиска.

---

Другой вопрос: как бы вы себя чувствовали, если бы я определил следующий предикат, а затем использовал стандартный алгоритм find_if, чтобы увеличить все значения до первого значения> = 3:

bool inc_if_less_than_3(int& a)
{
    return a++ < 3;
}

(GCC не останавливает меня, но я не могу сказать, есть ли какое-то неопределенное поведение, связанное с педантичностью).

1) Контейнер принадлежит пользователю. Поскольку разрешение модификации с помощью предиката никоим образом не наносит вред алгоритму, решать, как они его используют, должен сам вызывающий абонент.

2) Это отвратительно !!! Лучше реализовать find_if, как это, чтобы избежать этого кошмара (лучше всего сделать, так как, очевидно, вы не можете выбрать, является ли итератор постоянным или нет):

template <class Iter, class Pred>
Iter my_find_if(Iter first, Iter last, Pred fun)
{
    while (first != last 
       && !fun( const_cast<const typename std::iterator_traits<Iter>::value_type &>(*first)))
        ++first;
    return first;
}

Answer 4

Хотя я думаю, что ваш дизайн немного сбивает с толку (поскольку другие указали, что итераторы допускают изменения в контейнере, поэтому я не вижу вашу функцию действительно как const), есть способ вывести итератор из const_iterator. Эффективность зависит от вида итераторов.

#include <list>

int main()
{
  typedef std::list<int> IntList;
  typedef IntList::iterator Iter;
  typedef IntList::const_iterator ConstIter;

  IntList theList;
  ConstIter cit = function_returning_const_iter(theList);

  //Make non-const iter point to the same as the const iter.
  Iter it(theList.begin());
  std::advance(it, std::distance<ConstIter>(it, cit));

  return 0;
}

Answer 5

Вы думаете о своем дизайне неправильно. Не используйте константные аргументы для указания того, что делает функция - используйте их для описания аргумента. В этом случае не имеет значения, что find () не меняет список. Важно то, что find () предназначена для использования с изменяемыми списками.

Если вы хотите, чтобы ваша функция find() возвращала неконстантный итератор, то она позволяет вызывающей стороне изменять контейнер. Было бы неправильно для него принимать контейнер const, потому что это предоставило бы вызывающей стороне скрытый способ удаления константы контейнера.

Рассмотрим:

// Your function
MyList::iterator find(const MyList& list, int identifier);

// Caller has a const list.
const MyList list = ...
// but your function lets them modify it.
*( find(list,3) ) = 5;

Итак, ваша функция должна принимать неконстантный аргумент:

MyList::iterator find(MyList& list, int identifier);

Теперь, когда вызывающая сторона попытается использовать вашу функцию для изменения своего списка констант, она получит ошибку компиляции. Это намного лучший результат.

Answer 6

Если вы изменяете данные, направленные итератором, вы меняете список.

Идея, которую я здесь пытаюсь выразить, конечно же, заключается в том, что переданный список не может быть изменен / не будет изменен, но как только я сделаю ссылку на список const, мне придется использовать 'cons_iterator's', который затем мешает мне делать что-нибудь с результатом.

Что такое "Донг что-нибудь"? Изменение данных? Это меняет список, что противоречит вашим первоначальным намерениям. Если список является константным, он (и «он» включает в себя его данные) является константой.

Если бы ваша функция возвращала неконстантный итератор, она создала бы способ изменения списка, следовательно, список не был бы постоянным.

Answer 7

Вместо того, чтобы пытаться гарантировать, что список не будет изменен с помощью ключевого слова const, в этом случае лучше гарантировать его с помощью постусловия. Другими словами, сообщите пользователю через комментарии, что список не будет изменен.

Еще лучше было бы использовать шаблон, который может быть создан для итераторов или const_iterators:

template <typename II> // II models InputIterator
II find(II first, int identifier) {
  // do stuff
  return iterator;
}

Конечно, если вы собираетесь пойти на такие неприятности, вы можете также представить итераторы MyList пользователю и использовать std :: find.

Answer 8

Если вы собираетесь вернуть неконстантный метод доступа к контейнеру, сделайте функцию также неконстантной. Вы допускаете возможность изменения контейнера из-за побочного эффекта.

Это хорошая причина, по которой стандартные алгоритмы используют итераторы, а не контейнеры, поэтому они могут избежать этой проблемы.