ND322 wrote:

> Вопрос простой — любая нормальная библиотека, где есть контейнеры, будет
> иметь для них базовый класс (вероятнее всего, абстрактный). Если в нем
> предусмотреть методы перебора — next, prev, for_each, operator[]..., а
> потом их реализовывать в соответствующих потомках (очередь, список,
> стек...), то разве не будет того же эффекта но проще и дешевле?
Разве не
> логично, что каждый контейнер сам знает, как себя итерировать, но
> использует для этого стандартный интерфейс?

Ты расскажи это создателям STL-я лучше. У них логика особая.

MZ>Ты это кому другому бы рассказывал. Именно "новомодная" эта штука.
MZ>Не было ни итераторов, ни вообще STL-я в С++ классическом.
MZ>Даже шаблонов не было.
этой "новомодной" штучкой мы на проекте живом пользуемся уже лет 7
если тебе попадаются прикладные проекты на С++ без stl могу только посочувствовать.

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

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

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

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

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

В нашем случае, надо проверять не на валидность, а на сигнальность.

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

V>Как минимум для итераторов дребуется отдельный класс, POSITION это не класс, т.е. у него нет методов. С этой позиции MFC проще, т.к. меньше сущностей.

Ну как же меньше сущностей: ввели хэндл элемента, в дополнение к адресу и индексу.

POSITION — непрозрачный указатель на узел контейнера, итератор — полупрозрачный указатель на узел (с перегруженными операциями *, ->, ++ и т.д.)
Итератор позволяет совершать некоторые действия напрямую, а хэндл и индекс — только в связке с самим контейнером.

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

_>>А теперь придумайте такой же "лисопед" для list, set, map... При этом имейте в виду, что кто-то возможно захочет итерацию по коллекции в цикле...
ND>Эээ, а в чем принципиальная сложность? Я бы расширил список "закладных" функций еще next() /*ну, или operator ++, если угодно*/ и prev() /*или operator --*/ и в соотсетствующем контейнере list, map, set... — реализовал бы соответствующие методы. В чем криминал?

... и получил бы опять итератор
Только в профиль и ущербный.

Ибо:
— или контейнер stateful (хранит внутри текущую позицию), и за внешней красотой next(void)/prev(void) мы немедленно лишаемся не то что многопоточности, а даже реентерабельности
— или для итерирования требуется вынести эту текущую позицию наружу: либо в виде итератора (самостоятельного объекта с функциями доступа и навигации), либо в виде хэндла (аргумента этих самых функций Elem& at(POSITION), POSITION next(POSITION))

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

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

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

ononim wrote:

> этой "новомодной" штучкой мы на проекте живом пользуемся уже лет 7

Я на С++ пишу дольше значит.

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

Да нет у меня таких. Просто и до STL-я и шаблонов С++ жил себе
радостно и не тужил особо. Да, плохо, что не было хорошей стандартной
библиотеки, но её и сейчас нет (хорошей).

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

MZ>ND322 wrote:

>> Вопрос простой — любая нормальная библиотека, где есть контейнеры, будет
>> иметь для них базовый класс (вероятнее всего, абстрактный). Если в нем
>> предусмотреть методы перебора — next, prev, for_each, operator[]..., а
>> потом их реализовывать в соответствующих потомках (очередь, список,
>> стек...), то разве не будет того же эффекта но проще и дешевле?
MZ>Разве не
>> логично, что каждый контейнер сам знает, как себя итерировать, но
>> использует для этого стандартный интерфейс?

MZ>Ты расскажи это создателям STL-я лучше. У них логика особая.
Ну, хорошо хоть е один я так думаю. А то я уж решил, что совсем ничего не рублю, раз у меня такие вопросы возникают

MZ>Да нет у меня таких. Просто и до STL-я и шаблонов С++ жил себе
MZ>радостно и не тужил особо. Да, плохо, что не было хорошей стандартной
MZ>библиотеки, но её и сейчас нет (хорошей).
ясно, не перешагнул барьер между "мля, как же все непривычно" и "а блин, как я раньше без этого жил"
ЗЫ А меня от всего МФСшного, включая CList несварение желудка случается. Более отстойной библиотеки чем MFC пожалуй не найти.

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

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

_>>>А теперь придумайте такой же "лисопед" для list, set, map... При этом имейте в виду, что кто-то возможно захочет итерацию по коллекции в цикле...
ND>>Эээ, а в чем принципиальная сложность? Я бы расширил список "закладных" функций еще next() /*ну, или operator ++, если угодно*/ и prev() /*или operator --*/ и в соотсетствующем контейнере list, map, set... — реализовал бы соответствующие методы. В чем криминал?

К>... и получил бы опять итератор
К>Только в профиль и ущербный.

К>Ибо:
К>- или контейнер stateful (хранит внутри текущую позицию), и за внешней красотой next(void)/prev(void) мы немедленно лишаемся не то что многопоточности, а даже реентерабельности
К>- или для итерирования требуется вынести эту текущую позицию наружу: либо в виде итератора (самостоятельного объекта с функциями доступа и навигации), либо в виде хэндла (аргумента этих самых функций Elem& at(POSITION), POSITION next(POSITION))
Ну и что? Действительно, будет тот же итератор, но внутри самого контейнера. Почему реентерабильности лишусь? Насчет многопоточности, да, я и сам об этом выше писал — это плюс внешних итераторов. Мы имеем один контейнер и сколько угодно текущих позиций для него, который можно двигать туда-сюда независимо от самого контейнера. Ну, как бы, это вполне логично для того узкого круга задач, где несколько потоков должны использовать одну коллекцию. Не скажу за CList, а в борландовской реализации можно спокойно брать i-й элемент списка из разных потоков. Правда, я это делал от силы раз или два... Вопрос, насколько широк круг таких задач на практике?

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

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

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

MZ>>Так а не надо одними алгоритмами обрабатывать и контейнеры с произвольным
MZ>>доступом, и с последовательным.

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

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

MZ>>Ты это кому другому бы рассказывал. Именно "новомодная" эта штука.
MZ>>Не было ни итераторов, ни вообще STL-я в С++ классическом.
MZ>>Даже шаблонов не было.
O>этой "новомодной" штучкой мы на проекте живом пользуемся уже лет 7
O>если тебе попадаются прикладные проекты на С++ без stl могу только посочувствовать.
Странно, мне сплошь и рядом попадаются исходники, в которых от STL разве что <stdio> да <string> какие-нибудь.

MZ>>>Не было ни итераторов, ни вообще STL-я в С++ классическом.
MZ>>>Даже шаблонов не было.
O>>этой "новомодной" штучкой мы на проекте живом пользуемся уже лет 7
O>>если тебе попадаются прикладные проекты на С++ без stl могу только посочувствовать.
ND>Странно, мне сплошь и рядом попадаются исходники, в которых от STL разве что <stdio> да <string> какие-нибудь.
Я тоже когдато работал в такой конторе. Контора была полувоенная кстати. Вспоминаю ее как плохой сон.
Кстати что касается контейнеров, то в нашем коде (multi_)set'ов и (multi_)map'ов возможно даже больше чем list'ов и vector'ов. Потому аргументы в данном треде типа вектор и лист ацтой я воще читаю с улыбкой.
Буст тоже используется, но очень в меру.

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

К>>- или контейнер stateful (хранит внутри текущую позицию), и за внешней красотой next(void)/prev(void) мы немедленно лишаемся не то что многопоточности, а даже реентерабельности
К>>- или для итерирования требуется вынести эту текущую позицию наружу: либо в виде итератора (самостоятельного объекта с функциями доступа и навигации), либо в виде хэндла (аргумента этих самых функций Elem& at(POSITION), POSITION next(POSITION))

ND>Ну и что? Действительно, будет тот же итератор, но внутри самого контейнера. Почему реентерабильности лишусь? Насчет многопоточности, да, я и сам об этом выше писал — это плюс внешних итераторов. Мы имеем один контейнер и сколько угодно текущих позиций для него, который можно двигать туда-сюда независимо от самого контейнера. Ну, как бы, это вполне логично для того узкого круга задач, где несколько потоков должны использовать одну коллекцию. Не скажу за CList, а в борландовской реализации можно спокойно брать i-й элемент списка из разных потоков. Правда, я это делал от силы раз или два... Вопрос, насколько широк круг таких задач на практике?

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


А вынесенный наружу хэндл перебора (будь то явный указатель, или обёрнутый итератор, или осмысленный индекс, или непрозрачный ключ) — тут, разумеется, никаких проблем нет.
С той лишь разницей, что указатели и итераторы позволяют обращаться к элементам напрямую, без контейнера (а итераторы — ещё и перемещаться), тогда как индексы и хэндлы идут строго в паре с контейнером.

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

O>ЗЫ А меня от всего МФСшного, включая CList несварение желудка случается. Более отстойной библиотеки чем MFC пожалуй не найти.

Это ты ещё ATL не видел.
Там, блин, для одного и того же есть две сущности: CArray (пришедший из MFC) и CSimpleArray (из WTL?)
И у них разные интерфейсы, вплоть до того, что один использует size_t в качестве размеров и индексов, а другой — int.

CArray, кстати говоря, по умолчанию эксплуатирует неопределённое поведение!!! (Перемещает элементы с помощью memmove).
Кому не нравится — пишите свой трейтс.

К>Это ты ещё ATL не видел.
видел и даже пользуюсь изредка когда ченить комовское по быстрому нуна забодяжить. как то приятнее почему-то, наверно тем что легче и прозрачнее, хотя тяжелое наследие мфц гнетет

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

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

Да. Итератор хранит текущую позицию, тогда как в 'T& operator [] (unsigned n)' для списка будет использован аналог std::advance (а это уже O(n)).

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

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

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

ок. вот пример:

struct test {
   slist_node<test> asc;
   slist_node<test> desc;

   typedef typename list_iterator< slist_node<test>, &test::asc >::type asc_iterator;
   typedef typename list_iterator< slist_node<test>, &test::asc >::type desc_iterator;

   int data;
};

slist< test, test::asc_iterator > asc_list;
slist< test, test::desc_iterator > desc_list;

template< typename Range >
void print ( Range const & r ) {
   for( Range::iterator it = begin( r ); it != end( r ); increment( it ) ) {
      std::cout << it->data << std::endl;
   }
}

как это будет выглядеть без итераторов?

до вот этого твоего поста, я думал что высказывающиеся здесь против STL и итераторов валяют дурака, застряли в 90х и т.п.
теперь во всяком случае понятно откуда может взяться такая точка зрения

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

R>до вот этого твоего поста, я думал что высказывающиеся здесь против STL и итераторов валяют дурака, застряли в 90х и т.п.
R>теперь во всяком случае понятно откуда может взяться такая точка зрения

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