Итератор контейнера контейнера


Основываясь на этот вопрос я, хотя я бы стягивают итератор, который перебирает по контейнер контейнеров.

template<typename C>
class IteratorForContainerOfContainer
{
    public:
        using Container             = C;
        using ContainerContainer    = typename Container::value_type;
        using Contained             = typename ContainerContainer::value_type;

        using Level1Iter            = typename Container::iterator;
        using Level2Iter            = typename ContainerContainer::iterator;

        using iterator_category     = std::forward_iterator_tag;
        using value_type            = Contained;
        using difference_type       = std::size_t;
        using pointer               = value_type*;
        using reference             = value_type&;


        IteratorForContainerOfContainer(C& c)
            : outerLoop(std::begin(c))
            , outerEnd(std::end(c))
            , innerLoop(std::begin(*outerLoop))
            , innerEnd(std::end(*outerLoop))
        {
            nextValidPos();
        }
        IteratorForContainerOfContainer()
            : outerLoop()
            , outerEnd()
            , innerLoop()
            , innerEnd()
        {}


        IteratorForContainerOfContainer& operator++()
        {
            ++innerLoop;
            nextValidPos();
            return *this;
        }
        value_type& operator*()
        {
            return *innerLoop;
        }
        bool operator!=(IteratorForContainerOfContainer const& rhs) const
        {
            return outerLoop != rhs.outerLoop || innerLoop != rhs.innerLoop;
        }

        private:
            void nextValidPos()
            {
                while ((innerLoop == innerEnd) && (outerLoop != outerEnd)) {
                    ++outerLoop;
                    if (outerLoop != outerEnd) {
                        innerLoop = std::begin(*outerLoop);
                        innerEnd  = std::end(*outerLoop);
                    }
                }
                if (outerLoop == outerEnd) {
                    outerLoop   = Level1Iter();
                    outerEnd    = Level1Iter();
                    innerLoop   = Level2Iter();
                    innerEnd    = Level2Iter();
                }
            }
            Level1Iter          outerLoop;
            Level1Iter          outerEnd;
            Level2Iter          innerLoop;
            Level2Iter          innerEnd;
};

Так что пример простого использования будет:

int main()
{
    using CC = std::vector<std::vector<int>>;
    using It = IteratorForContainerOfContainer<CC>;

    CC   data = {{1,2,3},{4,5,6},{7,8,9}};

     for(It loop(data);loop != It(); ++loop) {
        std::cout << *loop << " ";
    }
    std::cout << "\n";

}


388
6
задан 1 февраля 2018 в 07:02 Источник Поделиться
Комментарии
2 ответа

Если вы пытаетесь получить IteratorForContainerOfContainer на пустой контейнер, ваш конструктор будет работать в неопределенное поведение, когда он пытается сделать внутренние итераторы, поскольку внешний контейнер пуст, outerLoop будет end итератор, и вы не можете разыменования end итератор.

Вы используете по умолчанию построенного объекта в двойном качестве end итератор. Попробуйте добавить в статический метод, чтобы возвратить один, end(C &c)С необходимыми изменениями nextValidPos.

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

Вы не определяете operator++(int)так, используя it++ не компилируется.

3
ответ дан 2 февраля 2018 в 01:02 Источник Поделиться

Имен (а.к.а. "вы, наверное, не волнует, но..."):


  • ContainerContainer Container. Разве это не наоборот? (ContainerContainer безусловно, контейнер, контейнеров...)

  • Level1Iter, ContainerContainer, OuterEnd. Это 3 разных префиксов для одного и того же... может просто использовать Outer и Inner везде.

  • Использовать Value не Contained. Внутренний контейнер содержал слишком, в конце концов.

Другие:


  • using iterator_category = std::forward_iterator_tag; ах таааак? http://en.cppreference.com/w/cpp/concept/ForwardIterator (не уверен, что это технически даже итератор ввода, поскольку у нее только один инкремент оператор).

  • std::begin(foo) и std::end(foo) -> using std::begin; begin(foo);

  • Я думаю, что вы столкнетесь с проблемами равенства:


    • Значение инициализации (построено по умолчанию) итератор не должен сравниваться равный конец итератора (это "сингулярная").

    • Оператор равенства не должна возвращать true для двух конечный итераторы с разных базовых контейнеров (см. раздел "гарантия многоходовые" страницы связаны cppreference).



Редактировать:

Вы совершенно правы насчет того, чтобы сравнить конечного итераторов из разных контейнеров, и сравнить их конечный итераторы с значение инициализации итератора.

Соответствующие части стандарта от n4659:


27.2.1 итератора.требования.общие Р7

Итераторы могут иметь особой ценности, которые не связаны с любой последовательности. [...]
Результаты большинства выражений не определены для сингулярных значений;
исключением являются лишь уничтожив итератор, который имеет исключительное значение, назначение неособо
значение итератора, который имеет исключительное значение, и, для итераторов, которые удовлетворяют DefaultConstructible
потребностей, используя значение инициализации итератора в качестве источника копирования или перемещения.

Явно не говорят, что вы не можете добавить равенства между значением инициализации и значение инициализации итератора.

27.2.5 вперед.итераторы Р2


Домен == вперед итераторы-это итераторы над
же базовой последовательности. Однако, значение инициализации итератора может быть
сравнивают и будут сравнивать равное с другими значение инициализации итератора
из того же типа. [ Примечание: значение инициализации итераторы ведут себя так, как если
они ссылаются на конец пустой последовательности. — конец Примечание ]

Нет "и" вот, но опять же, это не говорит, что вы не сможете добавить в сравнение между значением инициализации и конечный итераторы. И не говорите, что вы не можете добавить == сравнивать итераторы разных последовательностей.

Поэтому на передний итератор это нормально.

Но если вы когда-нибудь хотите сделать этот двунаправленный, вам нужно --a == --b then a == b, который не будет верно с этой реализации.


Мне кажется проще хранить указатель на внешний контейнер, и два итератора, в сочетании с предложением @1201ProgramAlarm статических метода end:

#include <cassert>
#include <iterator>

template<typename C>
class IteratorForContainerOfContainer
{
public:
using OuterContainer = C;
using InnerContainer = typename OuterContainer::value_type;
using Value = typename InnerContainer::value_type;

using OuterIter = typename OuterContainer::iterator;
using InnerIter = typename InnerContainer::iterator;

using iterator_category = std::forward_iterator_tag;
using value_type = Value;
using difference_type = std::size_t;
using pointer = value_type*;
using reference = value_type&;

explicit IteratorForContainerOfContainer(OuterContainer& c)
: container(std::addressof(c))
{
begin();
}

IteratorForContainerOfContainer()
: container(nullptr)
, outer()
, inner()
{}

IteratorForContainerOfContainer& operator++()
{
advance();

return *this;
}
value_type& operator*()
{
using std::end;

assert(container);
assert(outer != end(*container));
assert(inner != end(*outer));
assert(inner != InnerIter());

return *inner;
}
bool operator!=(IteratorForContainerOfContainer const& rhs) const
{
return container != rhs.container || outer != rhs.outer || inner != rhs.inner;
}

static IteratorForContainerOfContainer end(OuterContainer& c)
{
using std::end;

auto result = IteratorForContainerOfContainer();
result.container = std::addressof(c);
result.outer = end(c);

return result;
}

private:

void advanceUntilValid()
{
using std::begin;
using std::end;

assert(container);
assert(outer != end(*container)); // advancing past the end is bad!

while (inner == end(*outer))
{
std::advance(outer, 1);

if (outer == end(*container))
{
inner = InnerIter();
return;
}

inner = begin(*outer);
}
}

void begin()
{
using std::begin;
using std::end;

assert(container);

outer = begin(*container);

if (outer == end(*container))
return; // inner will never be valid (should be ok... I think... (singular values compare equal))

inner = begin(*outer);

advanceUntilValid();
}

void advance()
{
using std::begin;
using std::end;

assert(container);
assert(outer != end(*container)); // advancing past the end is bad!
assert(inner != end(*outer)); // should never be, because we always advance to the next valid value...

std::advance(inner, 1);

advanceUntilValid();
}

OuterContainer* container;
OuterIter outer;
InnerIter inner;
};

#include <iostream>
#include <vector>

int main()
{
using CC = std::vector<std::vector<int>>;
using It = IteratorForContainerOfContainer<CC>;

CC data = { { 1, 2, 3 }, { }, { 4, 5, 6 }, { 7, 8, 9 } };

for (It loop(data); loop != It::end(data); ++loop) {
std::cout << *loop << " ";
}

std::cout << "\n";
}

2
ответ дан 5 февраля 2018 в 10:02 Источник Поделиться