Возвращение «любого итератора ввода» вместо вектора :: итератор или список :: итератор

Question

Предположим, я хочу реализовать на C++ структуру данных для хранения ориентированных графов. Дуги будут храниться в узлах благодаря контейнерам STL. Я бы хотел, чтобы пользователи могли выполнять итерацию по дугам узла, похожим на STL.

Проблема, которую я имею, заключается в том, что я не хочу раскрывать класс Node (который фактически будет абстрактным базовым классом), который я использую в конкретном классе. Поэтому я не хочу, чтобы мои методы возвращают зЬй :: список :: итератор или зЬй :: вектор :: итератор ...

Я попытался это:

class Arc; 

typedef std::iterator<std::random_access_iterator_tag, Arc*> ArcIterator; // Wrong! 

class Node { 
public: 
    ArcIterator incomingArcsBegin() const { 
    return _incomingArcs.begin(); 
    } 
private: 
    std::vector<Arc*> _incomingArcs; 
}; 

Но это не правильно, потому что вектор :: const_iterator не может использоваться для создания ArcIterator. Так какой может быть этот ArcIterator?

Я нашел эту статью около Custom Iterators for the STL, но это не помогло. Я должен быть немного тяжелым сегодня ...;)

Answer 1

Если вы действительно не хотите, чтобы клиент этого класса знал, что он использует под ним вектор, но все же хочет, чтобы они могли каким-то образом перебирать его, вам, скорее всего, понадобится создать класс, который пересылает все его методы в std :: vector :: iterator.

Альтернативой может быть установка шаблона узла на основе типа контейнера, который он должен использовать под ним. Затем клиенты конкретно знают, какой тип контейнера он использует, потому что они сказали им использовать его.

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

Answer 2

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

Если нет, вы можете ознакомиться с использованием boost's iterator facades and adaptors, где вы можете определить свои собственные итераторы или приспособить другие объекты к итераторам.

Answer 3

Попробуйте это:

class Arc; 
class Node { 
private: 
    std::vector<Arc*> incoming_; 
public: 
    typedef std::vector<Arc*>::iterator iterator; 
    iterator incoming_arcs_begin() 
    { return incoming_.begin(); } 
}; 

и использовать Node :: итератор в остальной части кода. Когда/если вы меняете контейнер, вам нужно изменить typedef в одном месте. (Вы можете сделать этот шаг дальше с дополнительным typedef для хранения, в этом случае - вектором.)

Что касается вопроса о const, либо определите const_iterator вектора как ваш итератор, либо определите типы двойного итератора (const и non- const version), как это делает вектор.

Answer 4

Я просмотрел файл заголовка VECTOR.

vector<Arc*>::const_iterator 

является ЬурейеЕ для

allocator<Arc*>::const_pointer 

Может ли это быть вашим ArcIterator? Как:

typedef allocator<Arc*>::const_pointer ArcIterator; 

Answer 5

Чтобы скрыть тот факт, что ваши итераторы основаны на std::vector<Arc*>::iterator вам нужен класс итератора, что делегаты std::vector<Arc*>::iterator. std::iterator не делает.

Если посмотреть на заголовочные файлы в C вашего компилятора ++ стандартной библиотеки, вы можете обнаружить, что std::iterator не очень полезно само по себе, если все, что вам нужно не класс, который определяет определений типов для iterator_category, value_type и т.д.

Как упоминал в своем ответе Дуг Т., библиотека ускорения имеет классы, облегчающие запись итераторов. В частности, boost::indirect_iterator может быть полезна, если вы хотите, чтобы ваши итераторы возвращали Arc, когда были разыменованы вместо Arc*.

Answer 6

Вы можете templatize класс Node и typedef как итератор, так и const_iterator в нем.

Например:

class Arc {}; 

template< 
    template<class T, class U> class Container = std::vector, 
    class Allocator = std::allocator<Arc*> 
> 
class Node 
{ 
    public: 
    typedef typename Container<Arc*, Allocator>::iterator ArcIterator; 
    typedef typename Container<Arc*, Allocator>::Const_iterator constArcIterator; 

    constArcIterator incomingArcsBegin() const { 
     return _incomingArcs.begin(); 
    } 

    ArcIterator incomingArcsBegin() { 
     return _incomingArcs.begin(); 
    } 
    private: 
    Container<Arc*, Allocator> _incomingArcs; 
}; 

Я не пробовал этот код, но он дает вам идею. Однако вы должны заметить, что использование ConstArcIterator просто запретит модификацию указателя на Arc, а не модификацию самой дуги (например, с помощью неконстантных методов).

Answer 7

C++ 0x позволит вам сделать это с помощью automatic type determination.

В новом стандарте, это
for (vector::const_iterator itr = myvec.begin(); itr != myvec.end(); ++itr
можно заменить этим
for (auto itr = myvec.begin(); itr != myvec.end(); ++itr)

К тому же, вы сможете вернуть все, что итератор уместно, и хранить его в auto переменной ,

До тех пор, пока новый стандарт не вступит в силу, вам придется либо templatize вашего класса, либо предоставить абстрактный интерфейс для доступа к элементам вашего списка/вектора. Например, вы можете сделать это, сохранив итератор в переменной-члене, и предоставите функции-члены, например begin() и next(). Это, конечно, означало бы, что только один цикл за один раз может безопасно перебирать ваши элементы.

Answer 8

Посмотрите на Adobe any_iterator: этот класс использует метод, называемый тип erase, с помощью которого тип итератора underyling скрывается за абстрактным интерфейсом. Остерегайтесь: использование any_iterator несет штраф за выполнение во время виртуальной диспетчеризации.

Answer 9

Ну, потому что std::vector гарантированно иметь непрерывную память, она должна быть идеально тонкая, чтобы сделать это:

class Arc; 
typedef Arc* ArcIterator; 

class Node { 
public: 
    ArcIterator incomingArcsBegin() const { 
     return &_incomingArcs[0] 
    } 

    ArcIterator incomingArcsEnd() const { 
     return &_incomingArcs[_incomingArcs.size()] 
    } 
private: 
    std::vector<Arc*> _incomingArcs; 
}; 

В принципе, указатели функции достаточно, как случайные итераторы доступа, что они являются достаточными замены.

Answer 10

Рассмотрите возможность использования Visitor Pattern и инвертирования отношения: вместо запроса структуры графика для контейнера данных вы даете графику функтор и пусть график применит этот функтор к его данным.

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