Re: Зачем нужен итератор? - C/C++

Здравствуйте, MasterZiv, Вы писали:

>> был уверен. посмотрел -- облом
>> в оправдание могу сказать, что пользуюсь своими поделками

MZ>Ты так не шути больше. Меня чуть кандратий не хватил.
MZ>Думал -- усё, сбрендил.

>> boost::ptr_vector (уже было озвучено) не подходит?

MZ>Это не STL. Я могу и сам написать ( и сделал так ).
MZ>Вопрос не в этом, а в том, что это должно быть в стандартной
MZ>библиотеке.

дык претензии были к итераторам. по крайней мере в топике так написано.
а итераторы вполне полезная вещь.

MZ>Ну ладно, пора кончать уже с этим топиком.

ок.

Кодт wrote:

> <a
> href=http://www.boost.org/doc/libs/1_43_0/libs/ptr_container/doc/ptr_container.html>boost::ptr_vector</a>
> <http://www.boost.org/doc/libs/1_43_0/libs/ptr_container/doc/ptr_container.html>boost::ptr_vector</a>>?
> И никакого оверхеда.

Ну кстати в Motivation там вся "моя" проблема и расписана.

Posted via RSDN NNTP Server 2.1 beta

Здравствуйте, ND322, Вы писали:

Вопрос, насколько широк круг таких задач на практике?

Много простых алгоритмов и не очень , например std::sort

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

Здравствуйте, MasterZiv, Вы писали:

MZ>Юрий Жмеренецкий wrote:

>> Как будет выглядеть алгоритм перебора всех элементов списка с
>> использованием предложенного интерфейса за линейное время?

MZ>Я не предлагаю ТОТ ЖЕ алгоритм перебора писать, и С ТЕМИ ЖЕ
MZ>функциями. Можно -- давайте те же. Нельзя -- напишим другие,
MZ>с другими функциями доступа к коллекции, в чём проблема ?
MZ>Даже если они не будут выглядеть одинаково снаружи -- не
MZ>проблема, а ещё и лучше -- сразу видно, что контейнеры разные.

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

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, morm, Вы писали:

V>>>А как ты итератор на валидность проверишь?
M>>Тупанул, да

А как быть если возвращаешь, допустим, range, потом erase исходного контейнера. Что делать с end'ом в range??

К>Неподходящее слово "валидность", перегруженное смыслами.

К>Итераторы, — равно как и ссылки, указатели, диапазоны и прочие косвенности, — инвалидируются при некоторых изменениях контейнера.

К>Однако, помимо невалидных, есть ещё и сигнальные значения.
К>У указателей есть одно универсальное сигнальное значение — NULL, а также в роли сигнальных могут выступать указатели за конец массива (end()).
К>Разыменовывать сигнальный указатель или итератор нельзя. Но если это end, то можно применять к нему адресную арифметику.

К>В нашем случае, надо проверять не на валидность, а на сигнальность.
Согласен и ,тем не менее, при изменении end() контейнера ВСЕ range, допустим, полученые через MType::range = m.find(v); — тю-тю...
Мне что-то больше нравится с итератором вариант.

Здравствуйте, morm, Вы писали:

К>>В нашем случае, надо проверять не на валидность, а на сигнальность.
M>Согласен и ,тем не менее, при изменении end() контейнера ВСЕ range, допустим, полученые через MType::range = m.find(v); — тю-тю...
M>Мне что-то больше нравится с итератором вариант.

Следовательно, если мы хотим хранить результат поиска — то должны хранить лишь то, что нам нужно.
Не [it,end), а [it,it]

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

Впрочем, есть хорошие новости!
Для контейнеров с индивидуальными узлами (list, set, map...) значение end() неизменно, поэтому ни итератор, ни диапазон поиска не инвалидируется.

А вот для вектора — уменьшение размера инвалидирует все хвостовые итераторы, включая end(). Тут будет всё плохо.

Здравствуйте, ND322, Вы писали:

ND>Умные книжки много пишут о прелестях итераторов для различных контейнеров данных. Обычно приводятся примеры самостоятельных шаблонных классов, осуществляющих перебор элементов собственно контейнерного класса. Вот снова попалось в литературе, решил спросить мнение гуру. Где используются эти пресловутые классы-итераторы?

Оценить мощь итераторов и внешних алгоритмов на простых примерах не выйдет. Фундаментальное отличие STL от других библиотек состоит в том что STL — это конструктор из которого лего собрать все что портебуется.

Как примеры приведу
http://stxxl.sourceforge.net/ — "STXXL implements containers and algorithms that can process huge volumes of data"
http://tech.unige.ch/omptl/ — "The OMPTL re-implement the algorithm and numeric part of the STL. The range is partitioned, then the computation is executed in parallel."
http://code.google.com/p/thrust/ — "Thrust is a CUDA library of parallel algorithms with an interface resembling the C++ STL."

Для того чтобы эта круть была востребована нужно выйти за рамки тривиальных задач: нужны особые требования к быстродействию, потреблению памяти, масштабируемости на multicpu\multicore машинах, транзакцонности, нужно обрабатывать большие массивы данных, писать свои собственные алгоритмы и контейнеры и т.д. и т.п.

ND>Лично мне на практике всегда хватало его возможностей. Чего я не понимаю в этой жизни?
угу. Уже довольно давно нет одноядерных процессоров, как циклы параллелить будешь?

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, McSeem2, Вы писали:

MS>Итераторы — это бездарная попытка использовать C++ не по назначению. Теоретически это прикольно, но на практике ничего кроме пожизненного рака головы не получается.

Что ты предлагаешь на замену итераторам?

Здравствуйте, rm822, Вы писали:

Для сравнения вот как будет выглядеть этот код с использованием итераторов и некоторых фич из C++0x:

R>


#include <algorithm>
#include <boost/range/mfc.hpp>

using boost::begin;
using boost::end;
using std::for_each;

R>CTypedPtrList<CObList, CPerson*> myList;
R>myList.AddHead(new CPerson());

/*
R>POSITION pos = myList.GetHeadPosition();
R>while(pos != NULL)
R>{
R>   CPerson* thePerson = myList.GetNext(pos);
R>   thePerson->AssertValid();
R>}
*/

  for_each(begin(myList), end(myList), [](CPerson * p) { p->AssertValid(); });

R>CMap<CString, LPCTSTR, CPerson*, CPerson*> myMap;
R>CPerson myPerson;
R>myMap.SetAt(_T("Bill"), &myPerson);

/*
R>POSITION pos = myMap.GetStartPosition();
R>while(pos != NULL)
R>{
R>   CPerson* pPerson;
R>   CString string;
R>   // Get key (string) and value (pPerson)
R>   myMap.GetNextAssoc(pos, string, pPerson);
R>   // Use string and pPerson
R>}
*/

  using Pair = CMap<CString, LPCTSTR, CPerson*, CPerson*>::CPair;
  for_each(begin(myMap), end(myMap), [](Pair & val) {/*use val.key and val.value*/});

Здравствуйте, MasterZiv, Вы писали:

MZ>jazzer wrote:

>> Произвольные скачки по массиву — это действительно естественный способ
>> обращаться к его элементам, что в С++, что в Фортране.
>> Свойство массива как структуры данных такое.

MZ>Вот кстати да. Почему бы не сделать было вместо итераторов
MZ>заклад на 3 функции :
MZ>-- size()
MZ>-- T& operator [] (unsigned n)
MZ>-- const T& operator [] (unsigned n) const

MZ>Ничем не хуже.

Предлагаю взглянуть на boost::iterator_facade requirement, т.е. минимальный набор операций, на основе которых iterator_facade реализует полный интерфейс итератора:
http://www.boost.org/doc/libs/1_42_0/libs/iterator/doc/iterator_facade.html#iterator-facade-requirements

Тот же заклад на три функции.

Здравствуйте, ND322, Вы писали:

ND>Если мне надо пару десятков параметров массива информационного обмена по MIL-1553 запихать в список и потом находить в них нужный, это три-четыре строчки моего пользовательского кода. Микро- если не наносекунды машинного времени. Та же операция через крутую библиотеку с внешним иетратором уложится в 2 строки пользовательского кода. Но взамен, я получу 200 строк кода библиотечного, где будут сотни ненужных проверок, вызовов, подвызовов, создание монстрозных объектов в памяти и т.д. и т.п.

200 строк будут работать быстрее. http://rsdn.ru/forum/cpp/2944787.1.aspx

ND>Вот я и спрашиваю, скажем, Вас, где, в каких практических случаях у вас на практике была необходимость использования этих шаблонных чудо-конктейнеров с внешними итераторами? Можете ли вы, анализируя сейчас те случаи, что-либо сказать об их эффективности?

В <algorithm> много чего есть. Хотя бы std::sort.

CS>

CS>MType::range r = m.find(key);
CS>if(r.empty())
CS>  throw MErr(string("Нет элемента с номером ") + lexical_cast<string>(key));
CS>return r.front().second;
CS>

во что превращается скажем back_inserter?

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Юрий Жмеренецкий, Вы писали:

ЮЖ>В таком решении присутствует нарушение SRP — на контейнер возложено больше обязанностей, чем необходимо, соответственно на ровном месте возникает усложнение контракта контейнера и его реализации. Как следствие — потеря реентерабельности (см. сообщение Кодт'а). Кстати, перечисление в обратном порядке выполняется за O(n^2).

Это мой контейнер, я возложил на него столько обязанностей сколько мне необходимо, это раз

На сколько сложна реализация контейнера лично мне не принципиально, лишь бы он выполнял возложенные на него обязанности, это два

Мне не нужно перечисление в обратном порядке, а если станет нужно и если данная функция будет сильно тормозить весь код, то я без проблем допишу, ведь так? Это три

Я это к чему всё? Не к тому что я придумал универсальный контейнер который покроет все нужны (этот класс не публичный и только для моих целей используется), а к тому что, приложив немного серого вещества можно опровергнуть теорему Юрия Жмеренецкого:
ЮЖ>В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет линейной, поэтому сложность перебора всех элементов с помощью этого интерфейса будет квадратичной.

... << RSDN@Home 1.2.0 alpha rev. 786>>

Здравствуйте, zitz, Вы писали:

ЮЖ>>В таком решении присутствует нарушение SRP — на контейнер возложено больше обязанностей, чем необходимо, соответственно на ровном месте возникает усложнение контракта контейнера и его реализации. Как следствие — потеря реентерабельности (см. сообщение Кодт'а). Кстати, перечисление в обратном порядке выполняется за O(n^2).

Z>Это мой контейнер, я возложил на него столько обязанностей сколько мне необходимо, это раз

Как говорится, wish you happy debug.
Я встречал ситуации, когда кривой дизайн аукался спустя год успешного использования.
И один из таких случаев был, как раз, — склеивание коллекции с итератором.
Там была такая история: некий ком-объект, содержащий список. И выбор — либо реализовывать ещё один ком-класс с итератором, либо сделать по-быстрому, расширить интерфейс коллекции.

Здравствуйте, Кодт, Вы писали:

Z>>Это мой контейнер, я возложил на него столько обязанностей сколько мне необходимо, это раз

К>Как говорится, wish you happy debug.
К>Я встречал ситуации, когда кривой дизайн аукался спустя год успешного использования.
К>И один из таких случаев был, как раз, — склеивание коллекции с итератором.
К>Там была такая история: некий ком-объект, содержащий список. И выбор — либо реализовывать ещё один ком-класс с итератором, либо сделать по-быстрому, расширить интерфейс коллекции.

Спасибо за предупреждение! И за то что делетись опытом!

У меня всё не так критично и печально, т.к. по сути мой класс является обёрткой над std::set с очень урезанным интерфейсом (он собственно для этого и написан — чтобы лишнего ничего не было), ввобдить для него итераторы только для последовательного перебора — я посчитал это лишим и сделал operator[].

class CXXXUIntSet
{
public:
    CXXXUIntSet();
    CXXXUIntSet( const CXXXUIntSet &set );
    virtual ~CXXXUIntSet();

public:
    CXXXUIntSet& operator =( const CXXXUIntSet &set );
    BOOL operator!=( const CXXXUIntSet &set );
    BOOL operator==( const CXXXUIntSet &set );

public:
    BOOL Add( UINT nElem );
    BOOL Remove( UINT nElem );
    BOOL IsPresent( UINT nElem );
    void RemoveAll();

public:
    int GetCount() const;
    int GetSize() const;

public:
    UINT operator[]( int nIndex );
    CXXXUIntSet Intersection( CXXXUIntSet& set );
    CXXXUIntSet Union( CXXXUIntSet& set );
    CXXXUIntSet Difference( CXXXUIntSet& set );
    CXXXUIntSet SymmetricDifference( CXXXUIntSet& set );

private:
    void* m_pData;
    void* m_pNextPosition;
    int m_nNextIndex;
};

З.Ы. У меня основная причина (не относящаяся к данному случаю) happy debug — выход за границы массива/памяти и многопоточность

... << RSDN@Home 1.2.0 alpha rev. 786>>

Здравствуйте, zitz, Вы писали:

Z>У меня всё не так критично и печально, т.к. по сути мой класс является обёрткой над std::set с очень урезанным интерфейсом (он собственно для этого и написан — чтобы лишнего ничего не было), ввобдить для него итераторы только для последовательного перебора — я посчитал это лишим и сделал operator[].
Z>

Z>class CXXXUIntSet
Z>{
Z>public:
Z>    CXXXUIntSet();
Z>    CXXXUIntSet( const CXXXUIntSet &set );
Z>    virtual ~CXXXUIntSet();

Z>public:
Z>    CXXXUIntSet& operator =( const CXXXUIntSet &set );
Z>    BOOL operator!=( const CXXXUIntSet &set );
Z>    BOOL operator==( const CXXXUIntSet &set );

Z>public:
Z>    BOOL Add( UINT nElem );
Z>    BOOL Remove( UINT nElem );
Z>    BOOL IsPresent( UINT nElem );
Z>    void RemoveAll();

Z>public:
Z>    int GetCount() const;
Z>    int GetSize() const;

Z>public:
Z>    UINT operator[]( int nIndex );
Z>    CXXXUIntSet Intersection( CXXXUIntSet& set );
Z>    CXXXUIntSet Union( CXXXUIntSet& set );
Z>    CXXXUIntSet Difference( CXXXUIntSet& set );
Z>    CXXXUIntSet SymmetricDifference( CXXXUIntSet& set );

Z>private:
Z>    void* m_pData;
Z>    void* m_pNextPosition;
Z>    int m_nNextIndex;
Z>};
Z>

А зачем здесь m_pNextPosition и m_nNextIndex ? В интерфейсе же нет GetCurrent() / SeekNext() / etc.
Да, собственно, и std::set не наблюдается.

Z>З.Ы. У меня основная причина (не относящаяся к данному случаю) happy debug — выход за границы массива/памяти и многопоточность

С многопоточностью всё просто: объявить, что контейнер не многопоточный. И пусть владельцы контейнера самостоятельно сериализуют доступ к нему.

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

Даже в твоём интерфейсе: есть функции, вовлекающие два контейнера — Intersection etc... Ясное дело, что на время операции надо заблокировать оба.
Если у каждого свой мьютекс, это предпосылка для дедлоков. (Один поток захватит A,B, а второй попытается B,A).

Как вариант: внутри операции, поочерёдно
1) защитить экземпляр A и создать локальную копию A'
2) защитить экземпляр B и выполнить операцию A' ×= B
3) защитить экземпляр A и сделать присваивание A = A'
Правда, есть риск, что между 1 и 3 кто-то поменяет A. Поэтому такие вещи придётся делать в цикле:
1) защитить A, сделать копию A' и найти сигнатуру S
2) защитить B, вычислить A' ×= B
3) защитить A, найти сигнатуру S', и если S≠S' (данные изменились), перейти к 1; иначе же A=A'
В роли сигнатуры может быть и ещё одна резервная копия, и счётчик изменений.
Тогда можем нарваться на голодание (некий злодей будет много раз модифицировать A точно в моменты 2).
А для однопоточного применения — создание копий сильно избыточно.

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

Здравствуйте, Кодт, Вы писали:

Z>>

Z>>class CXXXUIntSet
Z>>{
Z>>    ...

Z>>private:
Z>>    void* m_pData;
Z>>    void* m_pNextPosition;
Z>>    int m_nNextIndex;
Z>>};
Z>>

К>А зачем здесь m_pNextPosition и m_nNextIndex ? В интерфейсе же нет GetCurrent() / SeekNext() / etc.
К>Да, собственно, и std::set не наблюдается.

Это закрытая часть класса, тот кто его использует не должен об этом задумываться

std::set скрыт через void*, чтобы не делать лишние инклюды
Можно было конечно пойти до конца и скрыть вообще всё в void* m_pData, но я пока не настолько фанатичен

Зачем они используются можно глянуть тут:
Re[7]: Зачем нужен итератор?

Z>>З.Ы. У меня основная причина (не относящаяся к данному случаю) happy debug — выход за границы массива/памяти и многопоточность

К>С многопоточностью всё просто: объявить, что контейнер не многопоточный. И пусть владельцы контейнера самостоятельно сериализуют доступ к нему.

Да я не про контейнеры, я вообще в целом. Вот последний пример happy debug — это падение из-за WM_PAINT когда при отрисовке идет обращение к данным которые были уничтожены вторым потоком (причем уничтожены не явно, вызовом какого-нить внешне безобидного метода), тут бывает вообще трудно уловить из-за чего падает и даже где падает. В общем страсти-мордасти

... << RSDN@Home 1.2.0 alpha rev. 786>>

Здравствуйте, ND322, Вы писали:

ND>Вот снова попалось в литературе, решил спросить мнение гуру. Где и как на практике используется эта крутизна? В чем преимущество перед обыкновенным CList\TList, который перебирает сои элементы сам без всяких сложных конструкций. Лично мне на практике всегда хватало его возможностей. Чего я не понимаю в этой жизни? Где используются эти пресловутые классы-итераторы?
ND>Заранее спасибо!

Я не гуру, и итераторы не люблю. Но пример приведу.
Просто для того, чтобы было яснее что такое итераторы и зачем они нужны.
Вот представь себе, что нам надо сделать коллекцию, которая хранит последовательность часто повторяющихся элементов.
Ну типа последовательность атрибутов букв текста. Скажем имён шрифтов или стилей.

Понятно, что если мы сделаем просто массив и работать будем просто по индексу, то будет большой перерасход памяти. Так как стиль переключают всего несколько раз на абзац. Кроме того доступ к группам (найти следующую буквы другого стиля) будет трудный.
Можно сделать массив пар из диапазона индексов и имени стиля. Но доступ по индексу будет непростой. Зато доступ к группам будет простой.

Подход с итераторами позволяет хранить просто массив пар {атрибут, сколько повторов}. Написать итератор по буквам поверх итератора такой структуры -- просто. Написать итератор по группам -- вообще ничего писать не надо. Всё просто, быстро, удобно

	От:	MasterZiv
	Дата:	30.07.10 12:10
	Оценка:

	От:	night beast
	Дата:	30.07.10 12:26
	Оценка:

	От:	MasterZiv
	Дата:	30.07.10 12:28
	Оценка:

	От:	minorlogic
	Дата:	30.07.10 13:38
	Оценка:

	От:	minorlogic
	Дата:	30.07.10 13:41
	Оценка:

	От:	morm
	Дата:	31.07.10 11:25
	Оценка:

	От:	rm822
	Дата:	31.07.10 13:54
	Оценка:	3 (1)

	От:	alexeiz
	Дата:	31.07.10 19:24
	Оценка:

	От:	alexeiz
	Дата:	31.07.10 20:42
	Оценка: