Семантика Const-correctness в С++

Для удовольствия и прибыли ™, я пишу класс trie в С++ (используя стандарт С++ 11).

У моего trie<T> есть итератор, trie<T>::iterator. (Все они фактически функционально const_iterator s, потому что вы не можете изменить trie value_type.) Объявление класса итератора выглядит примерно так:

template<typename T>
class trie<T>::iterator : public std::iterator<std::bidirectional_iterator_tag, T> {
    friend class trie<T>;
    struct state {
        state(const trie<T>* const node, const typename std::vector<std::pair<typename T::value_type, std::unique_ptr<trie<T>>>>::const_iterator& node_map_it ) :
            node{node}, node_map_it{node_map_it} {}
// This pointer is to const data:
        const trie<T>* node;
        typename std::vector<std::pair<typename T::value_type, std::unique_ptr<trie<T>>>>::const_iterator node_map_it;
    };
public:
    typedef const T value_type;
    iterator() =default;
    iterator(const trie<T>* node) {
        parents.emplace(node, node->children.cbegin());
            // ...
    }
    // ...
private:
    std::stack<state> parents;
    // ...
};

Обратите внимание, что указатель node объявлен const. Это потому, что (на мой взгляд) итератор не должен изменять node, на который он указывает; это просто итератор.

Теперь, в другом месте моего основного класса trie<T>, у меня есть функция стирания, которая имеет общую подпись STL - для удаления данных требуется iterator (и возвращает iterator к следующему объекту).

template<typename T>
typename trie<T>::iterator trie<T>::erase(const_iterator it)
{
    // ...

    // Cannot modify a const object!
    it.parents.top().node->is_leaf = false;

    // ...
}

Компилятор жалуется, потому что указатель node доступен только для чтения! Функция erase определенно должна изменить trie, на который указывает итератор, хотя итератор не должен.

Итак, у меня есть два вопроса:

Должны быть публичные конструкторы iterator? trie<T> имеет необходимые члены begin() и end(), и, конечно, trie<T>::iterator и trie<T> являются общими друзьями, но я не знаю Не знаю, что такое конвенция. Чтобы сделать их частными, я бы решился на то, что у меня возникло желание удалить const "обещание" из конструктора итератора.
Каковы правильные семантики/соглашения const относительно итератора и его указатель node здесь? Никто из меня никогда не объяснял это, и я не могу найти никаких учебных пособий или статей о паутина. Вероятно, это более важный вопрос, но для этого требуется много планирования и правильной реализации. Я полагаю, это можно было бы обойти, просто используя 1, но это принцип вещи!

Ответ 1

1) Все итераторы должны быть пригодны для копирования. Ваш итератор двунаправлен, поэтому также должен быть конструктивным по умолчанию (http://en.cppreference.com/w/cpp/concept/ForwardIterator), хотя я не знаю, почему. Поэтому конструктор по умолчанию должен быть общедоступным, но вы можете делать то, что вам нравится, с помощью const trie<T>*. Я бы подумал, что это должно быть конфиденциально, поскольку цель этого класса - предоставить пользователю итератор поверх trie, поэтому его публичный интерфейс должен быть только итератором соответствующей категории. Нет необходимости в каких-либо дополнительных общественных конструкторах.

2) erase является неконстантной функцией. Единственными итераторами, к которым вы можете действительно перейти, являются итераторы, которые ссылаются на то же самое, что функция вызывается, что означает (я думаю, хотя я не совсем уверен, что я следил за вашим дизайном) вся иерархия родителей неконстантных объектов. Поэтому я подозреваю, что это один из тех случаев, когда вы можете const_cast<trie<T>*>(it.parents.top().node). Итератору не разрешено использовать его для изменения trie, поэтому вы хотите, чтобы он удерживал указатель на константу. Но когда вы держите указатель на неконтекст trie, а именно this, вам разрешено изменять любую его часть, а итератор просто дает вам возможность начать изменять.

Возможно, существует еще один общий принцип состязания безопасности, который вы можете использовать здесь. Один из возможных случаев в container::erase(const_iterator) - это то, что const container*, которое вы получили от итератора, равно this. В этом случае const_cast, безусловно, является безопасным и законным (а также ненужным, потому что вы можете просто использовать this, но это касается того, является ли оно const-правильным или нет). В вашем контейнере он не равен (обычно) равным this, он указывает на один из нескольких объектов trie, которые вместе составляют иерархический контейнер, частью которого является this. Хорошей новостью является то, что весь контейнер логически const или логически неконстантен вместе, поэтому const_cast является столь же безопасным и законным, как если бы это был один объект. Но немного сложнее доказать правильность, потому что вы должны убедиться, что в вашем дизайне весь иерархический контейнер действительно делает, как я предполагал, разделение неконстантности.

Ответ 2

Не <<20 > методы trie, которые хотят изменить то, что указывает const_iterator (то, на что он указывает, должно быть в экземпляре this trie), должны просто const_cast по мере необходимости. Вы знаете, что это безопасный и определенный бросок, потому что если кому-то удалось вызвать экземпляр trie не const, то этот экземпляр trie сам не const. *

В качестве альтернативы вы можете сделать обратное и удерживать указатель < const <const <<21 > в пределах const_iterator, для чего потребуется конструкция const_cast. Это безопасно по той же причине, выше. Методы const_iterator предоставляют только const доступ, поэтому пользователь не может мутировать часть (-ы) trie, на которую указывает итератор. И если a const_iterator нужно мутировать в методе не const trie, это нормально, потому что trie не должен был const в первую очередь. *

Предпосылка безопасности const_cast здесь заключается в том, что безопасно удерживать и использовать указатель не const для объекта const, пока вы не будете мутировать этот объект. И безопасно отключить указатель const указателя, который указывает на то, что изначально не было объявлено как const.

* Да, вызывающий метод const trie может иметь const_cast ed в undefined; но в этом случае лордон, вызывающий поведение undefined, находится на их голове, а не trie s.

Ответ 3

Должны ли публичные конструкторы iterator?

По крайней мере, конструктор копирования, да. Посмотрите на эту диаграмму, которая описывает характеристики, которые должны иметь каждый тип итератора:

http://www.cplusplus.com/reference/iterator/

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

Каковы правильные семантики/соглашения const относительно итератора и его указателя node здесь?

Если вы хотите иметь erase, то у вас действительно нет const_iterator, у вас есть обычный iterator. Разница между ними заключается в том, что если у вас есть объект const trie, вы можете получить только const_iterator, потому что вам не разрешено каким-либо образом его изменять.

Вы можете заметить это в контейнерах STL. Они имеют тенденцию иметь:

iterator begin();
const_iterator begin() const;

Обычно происходит реализация const_iterator:

class iterator : public const_iterator {...};

который реализует одну или две неконстантные функции. Вероятно, это означает только erase для вас, так как ваш operator* будет оставаться const.