Как реализовать итератор в стиле STL и избежать распространенных ошибок? - PullRequest
277 голосов
/ 08 ноября 2011

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

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

Ответы [ 7 ]

215 голосов
/ 08 ноября 2011

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>, либо помещать те же определения типов в сам итератор, либо наследовать от 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, за исключением того, что они должны быть неявно построены из iterator, и пользователи не смогут изменять данные.Обычно его внутренний указатель является указателем на непостоянные данные и имеет iterator наследование от const_iterator, чтобы минимизировать дублирование кода.

Мой пост на Написание собственного STLКонтейнер имеет более полный прототип контейнера / итератора.

15 голосов
/ 08 ноября 2011

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

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

9 голосов
/ 08 ноября 2011

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

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

7 голосов
/ 29 сентября 2016

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

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

#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);
    }
}
4 голосов
/ 08 ноября 2011

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

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

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

2 голосов
/ 08 ноября 2011

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

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

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

1 голос
/ 12 ноября 2018

Я пытался решить проблему возможности перебирать несколько различных текстовых массивов, каждый из которых хранится в резидентной базе данных, которая является большой 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;
    }

};

Класс итераторов

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

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++;
    }
...