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

Я обычно предпочитаю constness, но недавно натолкнулся на головоломку с 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
}

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

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

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

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

12.10.2009 22:45:28
«Суть проблемы заключается в том, что итераторы в некотором смысле могут быть просто индикаторами положения» - это не то, чем являются итераторы. Если вы хотите этого, вы должны создать новый контейнер с типом «position» и использовать его вместо итераторов.
Bill 13.10.2009 16:37:17
продолжайте читать: «но так как они также предлагают доступ к самому списку, это не так просто»
Catskul 13.10.2009 19:12:51
... константные итераторы - это всего лишь индикаторы положения.
Catskul 14.10.2009 16:54:37
Проблема в вашем понимании итераторов. Итераторы не являются индикаторами позиции. (И в этой позиции вы найдете ваши данные). Итераторы - это данные , они просто несут информацию, необходимую для перехода к следующему элементу в контейнере.
GManNickG 16.11.2009 19:03:37
Вы просто обнаружили одну из причин, по которой концепция константности логически нарушена. Есть и другие (например, представьте, что вы передаете вектор const неконстантных элементов или неконстантный вектор const элементов).
6502 7.04.2011 06:53:08
8 ОТВЕТОВ
РЕШЕНИЕ

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

10
12.10.2009 23:21:10
Да, вы прекрасно меня поняли.
Catskul 12.10.2009 23:52:48
В противном случае известен как сделать изменчивую и постоянную версию функций, для изменяемого и постоянного доступа.
GManNickG 13.10.2009 01:06:45

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

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

0
12.10.2009 22:54:19
Но это сводит на нет цель const в первую очередь. Я хочу сказать, что функция не будет изменять список побочным эффектом. Это возвращаемое значение, которое может ... Я понимаю, что для создания неконстантного итератора возврата вам нужен неконстантный список, но это то, что я пытаюсь обойти. На самом деле я хотел бы использовать неконстантную версию списка для преобразования const_iterator в обычный итератор после возвращения. Также я не уверен, как помогает использование алгоритма в итераторе. Если вы хотите гарантировать, что функция не изменяется из-за побочного эффекта, как это вам поможет?
Catskul 12.10.2009 23:20:40
«Я хочу сказать, что функция не будет изменять список побочным эффектом. Это возвращаемое значение, которое может ...». Как я уже сказал, возвращаемое значение все еще попадает под функцию. Если возвращаемое значение позволяет его изменить, функция позволяет его изменить.
GManNickG 12.10.2009 23:22:20

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

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

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

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

1
12.10.2009 23:14:02
«Лучше гарантировать это с помощью постусловия» ... ну, это вообще не гарантия. Комментарии могут быть не синхронизированы с кодом. Const призван быть гарантией. Если я использую две версии (с помощью шаблона или иным образом), то я мог бы просто использовать неконстантную версию и игнорировать константную. Find был предназначен только для примера.
Catskul 12.10.2009 23:25:41
std :: find работает точно так, как я описал. И программист, который будет изменять постусловие, не внося надлежащих изменений в документацию, - это тот же программист, который удалит const из вашей функции.
Mark Ruzon 13.10.2009 17:31:36
Вы можете использовать этот аргумент и для других типов безопасности типов, но, тем не менее, используйте другие варианты безопасности типов, чтобы избежать доверия к кодировщику / документации. Вы правы в том, что причина, по которой find предлагает две версии, совпадает с моей проблемой, но если бы это было иначе возможно / просто в использовании / эффективно, то в случае поиска было бы предпочтительнее иметь только версию const.
Catskul 13.10.2009 19:31:57
+1, поскольку постусловие в комментариях - это почти все, что вы можете практически сделать в C ++, но это не идеальное решение. Последний комментарий Catskul является осветительным.
j_random_hacker 17.11.2009 08:49:50
Я воспринял вопрос как просьбу о практическом, а не идеальном решении. С помощью указателей я могу написать const char * p, чтобы сделать объект p указывающим на константу, или я могу написать char * const p, чтобы сделать указатель постоянным, или я могу написать const char * const p, чтобы сделать и указатель, и объект постоянная. Проблема (одна из многих) с C ++ состоит в том, что нет возможности распространить это понятие на итераторы или другие представления данных. Исправление было бы идеально.
Mark Ruzon 20.11.2009 17:40:16

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

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

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

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

1
12.10.2009 23:15:41
см. здесь: stackoverflow.com/questions/1557352/… чтобы понять, что я пытаюсь сказать.
Catskul 13.10.2009 00:52:11
Я понимаю, что вы говорите. Это просто не так, как в C ++. Либо что-то изменчивое, либо его нет. Если что-то не может мутировать что-то, то это не должно как-то дать кому-то, кто просит это, способность мутировать. То, что тело нашей функции не изменяет список, не делает функцию постоянной по отношению к списку. Если функция предоставляет возможность изменять список, функция изменяет список.
GManNickG 13.10.2009 01:01:01
Суть проблемы заключается в том, что итераторы могут представлять собой просто индикаторы положения, а его контейнер является изменчивым или неизменным. Если рассматривать как индикаторы положения, то тот, который указывает на контейнер const или контейнер const, будет эквивалентен. Поскольку они также предлагают доступ к самому списку, он становится более сложным. Я хотел использовать const, чтобы гарантировать, что функция ничего не изменяет, и вернуть индикатор положения. Можно извлечь эту концепцию заранее, но грязно. Использование const для создания такой гарантии - путь C ++.
Catskul 13.10.2009 01:25:36

Хотя я думаю, что ваш дизайн немного сбивает с толку (поскольку другие указали, что итераторы допускают изменения в контейнере, поэтому я не вижу вашу функцию действительно как 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;
}
2
12.10.2009 23:29:24
Да, это то, что я искал. К сожалению, это так жестоко / не гарантированно будет O (1). В идеальном мире это были бы: MyList :: iterator itor = myNonConstList.nonConstItorFromConst (someConstItor) и O (1)
Catskul 12.10.2009 23:39:05
Просто
GManNickG 13.10.2009 00:01:32

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

В общем случае вы не можете вернуть неконстантный «дескриптор» своим данным из метода 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, если они константные.

6
13.10.2009 13:05:02
Это, безусловно, предусматривает использование функции с контейнерами const, но тогда я теряю гарантию, что неконстантная функция не изменяет список. Что я действительно хотел бы - это использовать константу переданной ссылки, чтобы гарантировать, что список не будет изменен в теле функции. Реальное решение состоит в том, чтобы преобразовать const_iterator, возвращенный в неконстантный, через «advance» согласно одному из других ответов, но, к сожалению, он громоздкий: /
Catskul 12.10.2009 23:48:55
Catskul, если функция собирается возвращать что-то, что позволяет другим изменять список, то функция также нуждается в разрешении для изменения списка. Функция не может предоставить разрешения, которых у нее нет. Вы просто придется признать , что функция разрешается изменять список, даже если он не воспользуется этим правом.
Rob Kennedy 13.10.2009 00:22:20
Пример вы вывесили класса Foo это не правильно. Это не должно компилироваться в стандартном совместимом компиляторе (например, попробуйте Comeau Online). Я предполагаю, что вы говорите о логической X физической константности. Однако это не относится к ссылке в этом примере. Указатель подойдет лучше для иллюстрации проблемы.
Leandro T. C. Melo 13.10.2009 01:20:44
Вы правы - кажется, я помню пример Мейерса, похожий на этот. Я проверю это и отредактирую.
JohnMcG 13.10.2009 03:02:40
Думая об этом еще немного, я думаю, что пример Мейерса был публичным методом, возвращающим ссылку на приватную переменную.
JohnMcG 13.10.2009 03:05:02

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

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;
}
3
13.10.2009 15:30:02
«Я полагаю, что правильность const - это скорее услуга для вызывающей стороны ваших функций, а не для [няньки]…» Но этот аргумент становится рекурсивным, и тогда нет смысла в первую очередь использовать const. Это как бы присесть за детьми; это безопасность типа. Таким образом, например, вы должны иметь возможность разрабатывать функции, которые принимают предикат, и не беспокоиться о том, что предикат может изменить свои аргументы. Здесь возникает конфликт не с const, а с итераторами в том, что иногда они используются как простые индикаторы положения, но они всегда больше, чем это (когда не const).
Catskul 14.10.2009 16:51:57
Ну, может быть, это несколько вводит в заблуждение, но вы должны принять во внимание общую картину. GMan делает отличное замечание: если бы можно было взять контейнер const и вернуть неконстантный итератор, это нарушило бы правильность const для пользователя. По этой причине вы заметите, что в C ++ есть много мест, где вам нужно предоставлять как постоянные, так и изменяемые перегрузки. В таких случаях, кажется, лучше всего реализовать оба варианта в рамках одного и того же кода: вы обнаружите нежелательные модификации при тестировании с параметром const.
UncleBens 14.10.2009 18:08:26
+1, отличный пост. (К сожалению, C ++ не является более ортогональным, так что мы можем забыть о привязке к временным файлам, являющейся особым случаем.) Основа проблемы заключается в том, что constнедостаточно гранулировано для того, что хочет Catskul - это предложение «все или ничего». Но, как вы демонстрируете на своем примере с мутирующими предикатами, трудно представить более гранулярную форму const, которая не допускает всевозможного «удивительного» поведения. IOW трудно представить более гранулированную форму, constкоторая практически полезна.
j_random_hacker 17.11.2009 08:47:38

Вы думаете о своем дизайне неправильно. Не используйте константные аргументы, чтобы указать, что делает функция - используйте их для описания аргумента. В этом случае не имеет значения, что 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);

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

1
13.10.2009 11:18:43
(Прежде всего позвольте мне сказать, что я не хочу удалять константу итора. Я знаю, как это неправильно). «Не используйте константные аргументы, чтобы указать, что делает функция - используйте их для описания аргумента. " Я думал, что, возможно, я должен думать об этом таким образом, но подумал снова, это, кажется, не имеет смысла. Этот аргумент в основном разбивается на «использовать только const для удовлетворения потребности вызывающего в const», но это явно рекурсивно, и когда вы, наконец, доберетесь до вершины, причина использования const состоит в том, чтобы гарантировать, что код не изменит параметр, который точно моя цель.
Catskul 13.10.2009 14:46:24
Вы думаете об этом неправильно. Смотри, const MyList&это самая разрешительная форма - любой может назвать это. MyList&(неконстантный) является более ограничительным - вызывающие абоненты с const MyListне могут вызвать его. В вашем случае вы должны использовать более ограничительную форму (неконстантную).
alex tingle 13.10.2009 16:31:21
В идеальном мире функции, которые не изменяют переданные параметры, на которые ссылаются, будут предлагать только форму const, потому что это является целью const. Это не может быть очевидно, потому что итераторы предлагают возможность изменить список. Поскольку меня заботит только индикатор позиции итератора, я считаю, что неконстантная форма - это обходной путь. Другая работа, которая более уродлива, но ближе к понятию - «Advance»
Catskul 13.10.2009 19:23:09