Как реализовать итератор в стиле STL и избежать распространенных ошибок?

Я сделал коллекцию, для которой хочу предоставить итератор с произвольным доступом в стиле STL. Я искал пример реализации итератора, но не нашел. Я знаю о необходимости постоянных перегрузок []и *операторов. Какие требования предъявляются к итератору в стиле «STL» и каких других ошибок следует избегать (если таковые имеются)?

Дополнительный контекст: это для библиотеки, и я не хочу вводить какую-либо зависимость от нее, если мне действительно не нужно. Я пишу свою собственную коллекцию, чтобы обеспечить двоичную совместимость между C ++ 03 и C ++ 11 с одним и тем же компилятором (поэтому нет STL, который, вероятно, сломался бы).

http://www.cplusplus.com/reference/std/iterator/ имеет удобную диаграмму, которая детализирует спецификации § 24.2.2 стандарта C ++ 11. По сути, итераторы имеют теги, которые описывают допустимые операции, а теги имеют иерархию. Ниже приведен чисто символический, эти классы на самом деле не существуют как таковые.

iterator {
    iterator(const iterator&);
    ~iterator();
    iterator& operator=(const iterator&);
    iterator& operator++(); //prefix increment
    reference operator*() const;
    friend void swap(iterator& lhs, iterator& rhs); //C++11 I think
};

input_iterator : public virtual iterator {
    iterator operator++(int); //postfix increment
    value_type operator*() const;
    pointer operator->() const;
    friend bool operator==(const iterator&, const iterator&);
    friend bool operator!=(const iterator&, const iterator&); 
};
//once an input iterator has been dereferenced, it is 
//undefined to dereference one before that.

output_iterator : public virtual iterator {
    reference operator*() const;
    iterator operator++(int); //postfix increment
};
//dereferences may only be on the left side of an assignment
//once an output iterator has been dereferenced, it is 
//undefined to dereference one before that.

forward_iterator : input_iterator, output_iterator {
    forward_iterator();
};
//multiple passes allowed

bidirectional_iterator : forward_iterator {
    iterator& operator--(); //prefix decrement
    iterator operator--(int); //postfix decrement
};

random_access_iterator : bidirectional_iterator {
    friend bool operator<(const iterator&, const iterator&);
    friend bool operator>(const iterator&, const iterator&);
    friend bool operator<=(const iterator&, const iterator&);
    friend bool operator>=(const iterator&, const iterator&);

    iterator& operator+=(size_type);
    friend iterator operator+(const iterator&, size_type);
    friend iterator operator+(size_type, const iterator&);
    iterator& operator-=(size_type);  
    friend iterator operator-(const iterator&, size_type);
    friend difference_type operator-(iterator, iterator);

    reference operator[](size_type) const;
};

contiguous_iterator : random_access_iterator { //C++17
}; //elements are stored contiguously in memory.

Вы можете либо специализироваться std::iterator_traits<youriterator>, либо помещать те же typedefs в сам итератор, либо наследовать от std::iterator(у которых есть эти typedefs). Я предпочитаю второй вариант, чтобы избежать изменений в stdпространстве имен, и для удобства чтения, но большинство людей наследуют от std::iterator.

struct std::iterator_traits<youriterator> {        
    typedef ???? difference_type; //almost always ptrdiff_t
    typedef ???? value_type; //almost always T
    typedef ???? reference; //almost always T& or const T&
    typedef ???? pointer; //almost always T* or const T*
    typedef ???? iterator_category;  //usually std::forward_iterator_tag or similar
};

Обратите внимание , что iterator_category должен быть один из std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tag, или std::random_access_iterator_tag, в зависимости от того, какие требования вашего итератор удовлетворяет. В зависимости от вашего итератора, вы можете выбрать специализацию std::next, std::prev, std::advanceи std::distanceкак хорошо, но это редко. В крайне редких случаях вы можете захотеть специализироваться std::beginи std::end.

Ваш контейнер, вероятно, также должен иметь const_iteratorитератор (возможно, изменяемый) для константных данных, аналогичный вашему, iteratorза исключением того, что он должен быть неявно создан из a, iteratorи пользователи не смогут изменять данные. Обычно его внутренний указатель является указателем на непостоянные данные и iteratorнаследуется от него, const_iteratorчтобы минимизировать дублирование кода.

Мой пост в « Написание собственного STL-контейнера» содержит более полный прототип контейнера / итератора.

Документация iterator_facade от Boost.Iterator предоставляет то, что выглядит как хорошее руководство по реализации итераторов для связанного списка. Не могли бы вы использовать это в качестве отправной точки для создания итератора произвольного доступа над вашим контейнером?

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

Томас Беккер написал полезную статью на эту тему здесь .

Был также такой (возможно, более простой) подход, который появился ранее в SO: как правильно реализовать пользовательские итераторы и const_iterators?

Вот пример необработанного итератора указателя.

Вы не должны использовать класс итератора для работы с необработанными указателями!

#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <assert.h>

template<typename T>
class ptr_iterator
    : public std::iterator<std::forward_iterator_tag, T>
{
    typedef ptr_iterator<T>  iterator;
    pointer pos_;
public:
    ptr_iterator() : pos_(nullptr) {}
    ptr_iterator(T* v) : pos_(v) {}
    ~ptr_iterator() {}

    iterator  operator++(int) /* postfix */         { return pos_++; }
    iterator& operator++()    /* prefix */          { ++pos_; return *this; }
    reference operator* () const                    { return *pos_; }
    pointer   operator->() const                    { return pos_; }
    iterator  operator+ (difference_type v)   const { return pos_ + v; }
    bool      operator==(const iterator& rhs) const { return pos_ == rhs.pos_; }
    bool      operator!=(const iterator& rhs) const { return pos_ != rhs.pos_; }
};

template<typename T>
ptr_iterator<T> begin(T *val) { return ptr_iterator<T>(val); }


template<typename T, typename Tsize>
ptr_iterator<T> end(T *val, Tsize size) { return ptr_iterator<T>(val) + size; }

Обходной путь цикла на основе необработанного указателя. Пожалуйста, поправьте меня, если есть лучший способ сделать цикл на основе диапазона из необработанного указателя.

template<typename T>
class ptr_range
{
    T* begin_;
    T* end_;
public:
    ptr_range(T* ptr, size_t length) : begin_(ptr), end_(ptr + length) { assert(begin_ <= end_); }
    T* begin() const { return begin_; }
    T* end() const { return end_; }
};

template<typename T>
ptr_range<T> range(T* ptr, size_t length) { return ptr_range<T>(ptr, length); }

И простой тест

void DoIteratorTest()
{
    const static size_t size = 10;
    uint8_t *data = new uint8_t[size];
    {
        // Only for iterator test
        uint8_t n = '0';
        auto first = begin(data);
        auto last = end(data, size);
        for (auto it = first; it != last; ++it)
        {
            *it = n++;
        }

        // It's prefer to use the following way:
        for (const auto& n : range(data, size))
        {
            std::cout << " char: " << static_cast<char>(n) << std::endl;
        }
    }
    {
        // Only for iterator test
        ptr_iterator<uint8_t> first(data);
        ptr_iterator<uint8_t> last(first + size);
        std::vector<uint8_t> v1(first, last);

        // It's prefer to use the following way:
        std::vector<uint8_t> v2(data, data + size);
    }
    {
        std::list<std::vector<uint8_t>> queue_;
        queue_.emplace_back(begin(data), end(data, size));
        queue_.emplace_back(data, data + size);
    }
}

Прежде всего вы можете посмотреть здесь список различных операций, которые должны поддерживать отдельные типы итераторов.

Затем, когда вы создали свой класс итератора, вам нужно либо специализироваться std::iterator_traitsдля него и предоставить некоторые необходимые typedefs (например, iterator_categoryили value_type), либо альтернативно получить его std::iterator, который определяет необходимые typedefдля вас s и, следовательно, может использоваться по умолчанию std::iterator_traits.

Отказ от ответственности: я знаю, что некоторым людям это не очень нравится cplusplus.com, но они предоставляют действительно полезную информацию по этому вопросу.

Я был / я в той же лодке, что и вы, по разным причинам (частично образовательным, частично ограниченным). Мне пришлось переписать все контейнеры стандартной библиотеки, и контейнеры должны были соответствовать стандарту. Это означает, что если я поменяю контейнер с версией stl , код будет работать так же. Что также означало, что я должен был переписать итераторы.

Во всяком случае, я посмотрел на EASTL . Помимо изучения тонны контейнеров, которую я никогда не изучал все это время, используя контейнеры stl или мои курсы для студентов. Основная причина в том, что EASTL более читабелен , чем аналог stl (я обнаружил, что это просто из-за отсутствия всех макросов и простого стиля кодирования). Там есть какие-то странные вещи (например, #ifdefs для исключений), но ничего не ошеломляет.

Как уже упоминалось, посмотрите ссылку cplusplus.com на итераторы и контейнеры.

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

Следующее было разработано с использованием Visual Studio 2017 Community Edition в тестовом приложении MFC. Я привожу это в качестве примера, так как эта публикация была одной из нескольких, с которыми я столкнулся, предоставляя некоторую помощь, но все еще не отвечающую моим потребностям.

struct содержащих резидентных данных Памяти выглядели примерно следующий. Для краткости я удалил большинство элементов и также не включил используемые определения препроцессора (используемый SDK предназначен для C, а также C ++ и является старым).

Мне было интересно иметь итераторы для различных WCHARдвумерных массивов, которые содержали текстовые строки для мнемоники.

typedef struct  tagUNINTRAM {
    // stuff deleted ...
    WCHAR   ParaTransMnemo[MAX_TRANSM_NO][PARA_TRANSMNEMO_LEN]; /* prog #20 */
    WCHAR   ParaLeadThru[MAX_LEAD_NO][PARA_LEADTHRU_LEN];   /* prog #21 */
    WCHAR   ParaReportName[MAX_REPO_NO][PARA_REPORTNAME_LEN];   /* prog #22 */
    WCHAR   ParaSpeMnemo[MAX_SPEM_NO][PARA_SPEMNEMO_LEN];   /* prog #23 */
    WCHAR   ParaPCIF[MAX_PCIF_SIZE];            /* prog #39 */
    WCHAR   ParaAdjMnemo[MAX_ADJM_NO][PARA_ADJMNEMO_LEN];   /* prog #46 */
    WCHAR   ParaPrtModi[MAX_PRTMODI_NO][PARA_PRTMODI_LEN];  /* prog #47 */
    WCHAR   ParaMajorDEPT[MAX_MDEPT_NO][PARA_MAJORDEPT_LEN];    /* prog #48 */
    //  ... stuff deleted
} UNINIRAM;

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

Копия резидентных данных памяти сохраняется в объекте, который обрабатывает чтение и запись резидентных данных памяти с / на диск. Этот класс CFileParaсодержит шаблонный прокси-класс ( MnemonicIteratorDimSizeи подкласс, из которого он получен MnemonicIteratorDimSizeBase) и класс итератора MnemonicIterator.

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

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

const static DWORD_PTR dwId_TransactionMnemonic = 1;
const static DWORD_PTR dwId_ReportMnemonic = 2;
const static DWORD_PTR dwId_SpecialMnemonic = 3;
const static DWORD_PTR dwId_LeadThroughMnemonic = 4;

Прокси-класс

Шаблонный прокси-класс и его базовый класс следующие. Мне нужно было разместить несколько различных типов wchar_tтекстовых строковых массивов. Двухмерные массивы имели различное количество мнемоник, в зависимости от типа (цели) мнемоники, и разные типы мнемоник имели различную максимальную длину, варьируясь от пяти текстовых символов до двадцати текстовых символов. Шаблоны для производного прокси-класса естественно соответствовали шаблону, требующему максимального количества символов в каждой мнемонике. После создания прокси-объекта мы используем SetRange()метод для указания фактического мнемонического массива и его диапазона.

// proxy object which represents a particular subsection of the
// memory resident database each of which is an array of wchar_t
// text arrays though the number of array elements may vary.
class MnemonicIteratorDimSizeBase
{
    DWORD_PTR  m_Type;

public:
    MnemonicIteratorDimSizeBase(DWORD_PTR x) { }
    virtual ~MnemonicIteratorDimSizeBase() { }

    virtual wchar_t *begin() = 0;
    virtual wchar_t *end() = 0;
    virtual wchar_t *get(int i) = 0;
    virtual int ItemSize() = 0;
    virtual int ItemCount() = 0;

    virtual DWORD_PTR ItemType() { return m_Type; }
};

template <size_t sDimSize>
class MnemonicIteratorDimSize : public MnemonicIteratorDimSizeBase
{
    wchar_t    (*m_begin)[sDimSize];
    wchar_t    (*m_end)[sDimSize];

public:
    MnemonicIteratorDimSize(DWORD_PTR x) : MnemonicIteratorDimSizeBase(x), m_begin(0), m_end(0) { }
    virtual ~MnemonicIteratorDimSize() { }

    virtual wchar_t *begin() { return m_begin[0]; }
    virtual wchar_t *end() { return m_end[0]; }
    virtual wchar_t *get(int i) { return m_begin[i]; }

    virtual int ItemSize() { return sDimSize; }
    virtual int ItemCount() { return m_end - m_begin; }

    void SetRange(wchar_t (*begin)[sDimSize], wchar_t (*end)[sDimSize]) {
        m_begin = begin; m_end = end;
    }

};

Класс Iterator

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

class MnemonicIterator
{
private:
    MnemonicIteratorDimSizeBase   *m_p;  // we do not own this pointer. we just use it to access current item.
    int      m_index;                    // zero based index of item.
    wchar_t  *m_item;                    // value to be returned.

public:
    MnemonicIterator(MnemonicIteratorDimSizeBase *p) : m_p(p) { }
    ~MnemonicIterator() { }

    // a ranged for needs begin() and end() to determine the range.
    // the range is up to but not including what end() returns.
    MnemonicIterator & begin() { m_item = m_p->get(m_index = 0); return *this; }                 // begining of range of values for ranged for. first item
    MnemonicIterator & end() { m_item = m_p->get(m_index = m_p->ItemCount()); return *this; }    // end of range of values for ranged for. item after last item.
    MnemonicIterator & operator ++ () { m_item = m_p->get(++m_index); return *this; }            // prefix increment, ++p
    MnemonicIterator & operator ++ (int i) { m_item = m_p->get(m_index++); return *this; }       // postfix increment, p++
    bool operator != (MnemonicIterator &p) { return **this != *p; }                              // minimum logical operator is not equal to
    wchar_t * operator *() const { return m_item; }                                              // dereference iterator to get what is pointed to
};

Фабрика прокси-объектов определяет, какой объект должен быть создан на основе мнемонического идентификатора. Прокси-объект создается, и возвращаемый указатель является стандартным типом базового класса, чтобы иметь единый интерфейс независимо от того, к какому из различных мнемонических разделов обращаются. Этот SetRange()метод используется для указания прокси-объекту конкретных элементов массива, которые представляет прокси-сервер, и диапазона элементов массива.

CFilePara::MnemonicIteratorDimSizeBase * CFilePara::MakeIterator(DWORD_PTR x)
{
    CFilePara::MnemonicIteratorDimSizeBase  *mi = nullptr;

    switch (x) {
    case dwId_TransactionMnemonic:
        {
            CFilePara::MnemonicIteratorDimSize<PARA_TRANSMNEMO_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_TRANSMNEMO_LEN>(x);
            mk->SetRange(&m_Para.ParaTransMnemo[0], &m_Para.ParaTransMnemo[MAX_TRANSM_NO]);
            mi = mk;
        }
        break;
    case dwId_ReportMnemonic:
        {
            CFilePara::MnemonicIteratorDimSize<PARA_REPORTNAME_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_REPORTNAME_LEN>(x);
            mk->SetRange(&m_Para.ParaReportName[0], &m_Para.ParaReportName[MAX_REPO_NO]);
            mi = mk;
        }
        break;
    case dwId_SpecialMnemonic:
        {
            CFilePara::MnemonicIteratorDimSize<PARA_SPEMNEMO_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_SPEMNEMO_LEN>(x);
            mk->SetRange(&m_Para.ParaSpeMnemo[0], &m_Para.ParaSpeMnemo[MAX_SPEM_NO]);
            mi = mk;
        }
        break;
    case dwId_LeadThroughMnemonic:
        {
            CFilePara::MnemonicIteratorDimSize<PARA_LEADTHRU_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_LEADTHRU_LEN>(x);
            mk->SetRange(&m_Para.ParaLeadThru[0], &m_Para.ParaLeadThru[MAX_LEAD_NO]);
            mi = mk;
        }
        break;
    }

    return mi;
}

Использование прокси-класса и итератора

Прокси-класс и его итератор используются, как показано в следующем цикле, для заполнения CListCtrlобъекта списком мнемоник. Я использую std::unique_ptrтак, что когда прокси-класс мне больше не нужен и std::unique_ptrвыходит из области видимости, память будет очищена.

Этот исходный код создает прокси-объект для массива, structкоторый соответствует указанному мнемоническому идентификатору. Затем он создает итератор для этого объекта, использует ранжирование forдля заполнения элемента CListCtrlуправления, а затем очищает. Это все необработанные wchar_tтекстовые строки, которые могут точно соответствовать количеству элементов массива, поэтому мы копируем строку во временный буфер, чтобы гарантировать, что текст заканчивается нулем.

    std::unique_ptr<CFilePara::MnemonicIteratorDimSizeBase> pObj(pFile->MakeIterator(m_IteratorType));
    CFilePara::MnemonicIterator pIter(pObj.get());  // provide the raw pointer to the iterator who doesn't own it.

    int i = 0;    // CListCtrl index for zero based position to insert mnemonic.
    for (auto x : pIter)
    {
        WCHAR szText[32] = { 0 };     // Temporary buffer.

        wcsncpy_s(szText, 32, x, pObj->ItemSize());
        m_mnemonicList.InsertItem(i, szText);  i++;
    }

А теперь ключевой итератор для цикла на основе диапазона.

template<typename C>
class keys_it
{
    typename C::const_iterator it_;
public:
    using key_type        = typename C::key_type;
    using pointer         = typename C::key_type*;
    using difference_type = std::ptrdiff_t;

    keys_it(const typename C::const_iterator & it) : it_(it) {}

    keys_it         operator++(int               ) /* postfix */ { return it_++         ; }
    keys_it&        operator++(                  ) /*  prefix */ { ++it_; return *this  ; }
    const key_type& operator* (                  ) const         { return it_->first    ; }
    const key_type& operator->(                  ) const         { return it_->first    ; }
    keys_it         operator+ (difference_type v ) const         { return it_ + v       ; }
    bool            operator==(const keys_it& rhs) const         { return it_ == rhs.it_; }
    bool            operator!=(const keys_it& rhs) const         { return it_ != rhs.it_; }
};

template<typename C>
class keys_impl
{
    const C & c;
public:
    keys_impl(const C & container) : c(container) {}
    const keys_it<C> begin() const { return keys_it<C>(std::begin(c)); }
    const keys_it<C> end  () const { return keys_it<C>(std::end  (c)); }
};

template<typename C>
keys_impl<C> keys(const C & container) { return keys_impl<C>(container); }

Использование:

std::map<std::string,int> my_map;
// fill my_map
for (const std::string & k : keys(my_map))
{
    // do things
}

Это то, что я искал. Но, похоже, никто этого не имел.

Вы получаете мое выравнивание кода OCD в качестве бонуса.

В качестве упражнения напишите свое values(my_map)