Здравствуйте, LaptevVV, Вы писали:
J>>Демагогия. J>>Совместимость с Си тут вообще ни при чем. LVV>Еще как причем... Вот нельзя было бы в С арифметические операции с указателями делать, и не стали бы реализовывать "итератор произвольного доступа" — для совместимости с указателем. J>Произвольные скачки по массиву — это действительно естественный способ обращаться к его элементам, что в С++, что в Фортране. J>>Свойство массива как структуры данных такое. LVV>Ага. Только обеспечивается оно индексом, а не итератором.
без разницы, если не касаться вопросов инвалидации.
Индексы точно так же радостно вычитают и складывают.
Ты ж преп, вспомни методы прогонки, численного дифференцирования — они все в терминах итераторов (отношений индексов) формулируются, сплошь i и рядом i+1, i-1 и т.д.
J>>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками. LVV>Это от задачи зависит.
что от задачи зависит? Скорость перемещения итератора произвольного доступа?
Здравствуйте, jazzer, Вы писали:
J>>>Свойство массива как структуры данных такое. LVV>>Ага. Только обеспечивается оно индексом, а не итератором. J>без разницы, если не касаться вопросов инвалидации. J>Индексы точно так же радостно вычитают и складывают. J>Ты ж преп, вспомни методы прогонки, численного дифференцирования — они все в терминах итераторов (отношений индексов) формулируются, сплошь i и рядом i+1, i-1 и т.д.
1. Хорош уже бублик крошить на препода...
2. Не...
Зачем нам две одинаковых сущности на одном месте? Не следует плодить их без надобности.
Итератор — это именно для последовательного доступа предназначен. То, что он в С++ такой произвольный получился — это идеологически неправильно.
Но оправдано наличием указателей для массивов и идеей обратной совместимости. J>>>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками. LVV>>Это от задачи зависит. J>что от задачи зависит? Скорость перемещения итератора произвольного доступа?
Не. Потребность в произвольном итераторе.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, MasterZiv, Вы писали:
MZ>ND322 wrote:
>> готовый библиотечный и мы сами его не пишем, остается проблема ресурсов, >> которые он сжирает за свое существование. По современным меркам — >> мелочь. Но вот я когда-о еще в институте писал всяике полезняшки на
MZ>В 80% случаем, а может и в 90, итератор в реализации -- это лиш MZ>прикрытый фиговым листком указатель. Так что никакой накладухи там MZ>нет.
MZ>Просто итератор, выделенный как абстракция, позволяет делать их MZ>разными, в том числе и тебе самому.
Согласен. Но отдельный класс со своей иерархией, VMT, это все-таки накладуха плюс дополнительный код в котором можно насажать ошибок. Вопрос простой — любая нормальная библиотека, где есть контейнеры, будет иметь для них базовый класс (вероятнее всего, абстрактный). Если в нем предусмотреть методы перебора — next, prev, for_each, operator[]..., а потом их реализовывать в соответствующих потомках (очередь, список, стек...), то разве не будет того же эффекта но проще и дешевле? Разве не логично, что каждый контейнер сам знает, как себя итерировать, но использует для этого стандартный интерфейс?
Здравствуйте, jazzer, Вы писали:
J>Здравствуйте, ND322, Вы писали:
J>>>Но вообще, Boost.Iterator сильно помогает сократить количество кода — достаточно просто пару функций реализовать (типа dereference), а все операторы она сама сделает.
ND>>Ну, вы же понимаете, что "она сама сделает" вовсе не означает сокращения количества кода, как Вы написали. Сократите в одном месте — удлините в другом Если мне надо пару десятков параметров массива информационного обмена по MIL-1553 запихать в список и потом находить в них нужный, это три-четыре строчки моего пользовательского кода. Микро- если не наносекунды машинного времени. Та же операция через крутую библиотеку с внешним иетратором уложится в 2 строки пользовательского кода. Но взамен, я получу 200 строк кода библиотечного, где будут сотни ненужных проверок, вызовов, подвызовов, создание монстрозных объектов в памяти и т.д. и т.п. Не дай бог, придется это дело потом трассировать, если что не так! Вот я и спрашиваю, скажем, Вас, где, в каких практических случаях у вас на практике была необходимость использования этих шаблонных чудо-конктейнеров с внешними итераторами? Можете ли вы, анализируя сейчас те случаи, что-либо сказать об их эффективности?
J>Мне заклинание "MIL-1553" ни о чем не говорит, сорри. J>Тем не менее, вы знакомы с CRTP? J>Там нулевой оверхед, и Boost.Iterator сделана именно через него. J>Так что очень интересно, где вы там нашли монструозные объекты и прочая
J>Насчет практических случаев — да, использовал многажды, никаких нареканий к эффективности, ибо CRTP.
Да, знаком, хотя сам таких финтов ни разу не писал. Действительно, оверхед будет нулевой. Виртуельные методы без VMT А в каких случаях использовали, Если не секрет? Только в Boost или использовали вообще как общий подход в работе с контейнерами?
Здравствуйте, saf_e, Вы писали:
_>Здравствуйте, MasterZiv, Вы писали:
MZ>>jazzer wrote:
>>> Произвольные скачки по массиву — это действительно естественный способ >>> обращаться к его элементам, что в С++, что в Фортране. >>> Свойство массива как структуры данных такое.
MZ>>Вот кстати да. Почему бы не сделать было вместо итераторов MZ>>заклад на 3 функции : MZ>>-- size() MZ>>-- T& operator [] (unsigned n) MZ>>-- const T& operator [] (unsigned n) const
MZ>>Ничем не хуже.
_>А теперь придумайте такой же "лисопед" для list, set, map... При этом имейте в виду, что кто-то возможно захочет итерацию по коллекции в цикле...
Эээ, а в чем принципиальная сложность? Я бы расширил список "закладных" функций еще next() /*ну, или operator ++, если угодно*/ и prev() /*или operator --*/ и в соотсетствующем контейнере list, map, set... — реализовал бы соответствующие методы. В чем криминал?
Здравствуйте, x-code, Вы писали: XC>Основной аргумент в пользу итераторов из предложенных выше — итераторы универсальны, т.е. можно одними и теми же алгоритмами обрабатывать и массивы, и списки, и хз что еще. Однако у меня возникает вопрос практической необходимости такой универсальности. В моих программах, как правило, любая коллелкция — это часть какого-либо класса, и она используется там исключительно для конкретных нужд класса. Методы класса реализуют конкретные алгоритмы, связанные с конкретной предметной областью, и как правило очень сильно заточены под логику этой предметной области. Иными словами, алгоритмы обработки конкретной коллекции совершенно бесполезны и бессмысленны для другой коллекции в другом классе.
Ну, собственно, это и был мой вопрос — если я работаю со списком, значит со списком, если с динамическим массивом (вектором), значит с вектором... Ну, собственно, лично я больше не с чем обычно и не работаю Что мне даст красивый итератор, для создания которого придется отводить отдельную память, тратить быстродействие на кучу его внутренних проверок (валидность, равенства нулю/не нулю и т.д и т.п.), обработчиков исключений и т.д. На практике мне обычно бывает нужно всего пара функций для доступа к данным коллекции. ИМХО, дешево-сердито.
Здравствуйте, ND322, Вы писали:
J>>Насчет практических случаев — да, использовал многажды, никаких нареканий к эффективности, ибо CRTP. ND>Да, знаком, хотя сам таких финтов ни разу не писал. Действительно, оверхед будет нулевой. Виртуельные методы без VMT А в каких случаях использовали, Если не секрет? Только в Boost или использовали вообще как общий подход в работе с контейнерами?
Как общий подход. Для своих контейнеров замечательно все работало (и продолжает замечательно работать).
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, jazzer, Вы писали:
J>>>>Свойство массива как структуры данных такое. LVV>>>Ага. Только обеспечивается оно индексом, а не итератором. J>>без разницы, если не касаться вопросов инвалидации. J>>Индексы точно так же радостно вычитают и складывают. J>>Ты ж преп, вспомни методы прогонки, численного дифференцирования — они все в терминах итераторов (отношений индексов) формулируются, сплошь i и рядом i+1, i-1 и т.д. LVV>1. Хорош уже бублик крошить на препода...
Не покрошишь бублик на препода — потом придет неуч на собеседование LVV>Зачем нам две одинаковых сущности на одном месте? Не следует плодить их без надобности.
зачем for, если есть while (не говоря уже о goto)?
LVV>Итератор — это именно для последовательного доступа предназначен. То, что он в С++ такой произвольный получился — это идеологически неправильно.
Еще раз — это просто оптимизация двунаправленного, не более того. LVV>Но оправдано наличием указателей для массивов и идеей обратной совместимости.
Все наоборот — просто массивы и указатели как раз предоставляют константную сложность, в отличие от общего линейного случая.
J>>>>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками. LVV>>>Это от задачи зависит. J>>что от задачи зависит? Скорость перемещения итератора произвольного доступа? LVV>Не. Потребность в произвольном итераторе.
Пока ты не упрешься в требования скорости, с тебя вполне двунаправленного хватит. Произвольный — просто оптимизация. Юзай std::advance и будет тебе счастье
Здравствуйте, jazzer, Вы писали:
LVV>>1. Хорош уже бублик крошить на препода... J>Не покрошишь бублик на препода — потом придет неуч на собеседование
Не... Наших расхватывают прям с момента защиты... Даже троечников... LVV>>Зачем нам две одинаковых сущности на одном месте? Не следует плодить их без надобности. J>зачем for, если есть while (не говоря уже о goto)?
Ты знаешь, я тоже задаюсь этим вопросом: зачем нужен for? Студиозов приходится отучать его использовать по поводу и без повода.
лучше for_each использовать...
А вот цикл в сравнении с if+goto — это операция более высокого уровня.
В отличие от произвольного итератора и индекса — они одного поля ягоды. LVV>>Итератор — это именно для последовательного доступа предназначен. То, что он в С++ такой произвольный получился — это идеологически неправильно. J>Еще раз — это просто оптимизация двунаправленного, не более того. LVV>>Но оправдано наличием указателей для массивов и идеей обратной совместимости. LVV>>Потребность в произвольном итераторе. J>Пока ты не упрешься в требования скорости, с тебя вполне двунаправленного хватит. Произвольный — просто оптимизация. Юзай std::advance и будет тебе счастье
Это все понятно. Но хочется идеологически выдержанного итератора. Раз последовательнный доступ — так уж последовательный... Токмо за чистоту идеи и голос поднимаю.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re: Зачем нужен итератор?
От:
Аноним
Дата:
26.07.10 21:52
Оценка:
Итераторы используют чуть менее, чем все, кто использует STL.
Проблем с пониманием нет, с производительностью тоже нет.
Это абсолютно стандартная вещь для программирования на C++, а не какая-то "новомодная". Скорее даже наоборот, "старомодная".
Лично я вижу в STL-ных итераторах только один недостаток — их всегда нужно два, что удлиняет запись.
Я за то, чтобы итератор сам проверял свою валидность. Тогда можно будет писать:
typedef map<string, Item> Items;
Item* FindItem(string name)
{
Items::iterator it = items.find(name);
if (!it)
return NULL;
return it->second;
}
void EnumerateItems()
{
for (Items::iterator it = items.begin(); it; ++it)
{
//...
}
}
Здравствуйте, MasterZiv, Вы писали:
MZ>Вот кстати да. Почему бы не сделать было вместо итераторов MZ>заклад на 3 функции : MZ>-- size() MZ>-- T& operator [] (unsigned n) MZ>-- const T& operator [] (unsigned n) const
MZ>Ничем не хуже.
В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет линейной, поэтому сложность перебора всех элементов с помощью этого интерфейса будет квадратичной.
Здравствуйте, Vain, Вы писали:
V>Здравствуйте, morm, Вы писали:
V>>>Так и итераторов будет два, если функцию find обернуть — придётся всегда пару итераторов возвращать, тогда как range уже какбе пара итераторов. M>>чего й то??? V>А как ты итератор на валидность проверишь?
Тупанул, да А как быть если возвращаешь, допустим, range, потом erase исходного контейнера. Что делать с end'ом в range??
Здравствуйте, x-code, Вы писали:
XC>Основной аргумент в пользу итераторов из предложенных выше — итераторы универсальны, т.е. можно одними и теми же алгоритмами обрабатывать и массивы, и списки, и хз что еще. Однако у меня возникает вопрос практической необходимости такой универсальности. В моих программах, как правило, любая коллелкция — это часть какого-либо класса, и она используется там исключительно для конкретных нужд класса. Методы класса реализуют конкретные алгоритмы, связанные с конкретной предметной областью, и как правило очень сильно заточены под логику этой предметной области. Иными словами, алгоритмы обработки конкретной коллекции совершенно бесполезны и бессмысленны для другой коллекции в другом классе.
Вы пользуетесь algorithm? Если да то вопросов не должно возникать, сортировка поиск первого элемента и т.д., все единообразно для большинства контейнеров. Алгоритм написан и отлажен 1 раз, а не в каждом классе своя вариация.
XC>С точки зрения замены типов коллекций. Часто вижу такой аргумент: если вдруг захочется заменить vector на list или наоборот, то все что нужно сделать — просто заменить тип в объявлении объекта-коллекции. XC>Народ, вот это мне как минимум непонятно... Выбор типа для коллекции — фундаментальная вещь, которая должна делаться один раз в самом начале разработки того или иного класса. Мне и в бреду не придет мысль менять list на vector, если я знаю КАК ИМЕННО я работаю с коллекцией, для каких целей я ее вводил в программ и для чего она там используется...
Ну, бывает и хуже, пишешь новый класс, и понимаешь что у тебя есть какое то множество, объявляешь его std::set<myenum>, написал половину класса и понимаешь что для одного из методов тебе важен порядок в какой было все считано, и меняешь set на vector, часть написанного кода остается а добавление меняется, вот это кстати минус, есть универсальный способ доступа к контейнерам, есть удаление, а вот одного и того же insert нету
Менять list на vector вроде не приходилось, а вот set->multiset в связи с развитием задачи было.
Замена list, vector, deque легко может произойти при оптимизации задач, когда будет видно что узкое горлышко именно из-за контейнера, если у вас в задачах нету ограничений по памяти и времени, то вам вряд ли придется столкнуться с этим.
я стараюсь писать
typedef std::vector<int> TSomeEssence;
а внутри
for (TSomeEssence::iterator it ...), такой код мне банально легче читать, сразу видно какая сущность лежит в контейнере.
Здравствуйте, Аноним, Вы писали:
А>Лично я вижу в STL-ных итераторах только один недостаток — их всегда нужно два, что удлиняет запись.
... причём из одного домена (контейнера), что ещё более удлинняет запись. Особенно, когда ссылка на контейнер приходит извне.
В этом плане, интервалы (range) более удобны.
Изредка требуется тройка итераторов: begin <= middle <= end, которую можно выразить двумя интервалами [begin,middle), [middle,end).
Правда, где тройка, там и четвёрка может потребоваться...
А>Я за то, чтобы итератор сам проверял свою валидность. Тогда можно будет писать:
Для этого
— либо итератор должен иметь доступ к end своего домена, или хранить другой признак вылета за диапазон (особенно, когда речь идёт о поддиапазонах)
— либо это однонаправленный итератор, так что все end можно считать эквивалентными, и заменять на специальное значение (например, NULL)
То есть, или оверхед, или неоправданные ограничения.
Было бы проще написать такой find, который возвращает пару (итератор, успешность).
Тот же самый lower_bound мог бы сразу сообщать, указывает итератор на "меньшее" или "равное" значение.
XC>И еще. Для работы с GUI часто требуется привязать какие-то "итераторы" к элементам контролов (методы типа SetItemData()/GetItemData()). POSITION — это гарантированно 4-байтовое значение, которое легко привязывается простым приведением типов. С итераторами такой номер не прокатит, это класс, который разумеется нельзя приводить к DWORD, void*, LPARAM и т.д. XC>На этот вопрос, кстати, мне так толком никто и не ответил.
Юрий Жмеренецкий wrote: > MZ>Ничем не хуже. > > В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет > линейной, поэтому сложность перебора всех элементов с помощью этого > интерфейса будет квадратичной.
Так а не надо одними алгоритмами обрабатывать и контейнеры с произвольным
доступом, и с последовательным. Ну, максимум будет в два раза больше
реализаций алгоритмов. Это проблема для СТАНДАРТНОЙ библиотеки, которая
один раз пишется ?
x-code wrote:
> Кстати, интересный вопрос. Давайте сравним MFC CList с POSITION и > std:list с его итераторами. > Пользуюсь и тем и другим, но как ни странно, больше нравится CList. Даже > сделал с MFC'шных классов кроссплатформенную реализацию.
+1 (тоже кстати сделали такое, внутри -- реализация на STL )
> Итераторы УНИВЕРСАЛЬНЕЕ, но НЕ НАГЛЯДНЕЕ... В том смысле, что запись с
...
> В случае с MFC CList требуется передавать и итератор, и ссылку на саму > коллекцию.
Это всё -- ерунда. Это проблемы идеологические, проблемы непонимания
> Основной аргумент в пользу итераторов из предложенных выше — итераторы > универсальны, т.е. можно одними и теми же алгоритмами обрабатывать и > массивы, и списки, и хз что еще. Однако у меня возникает вопрос > практической необходимости такой универсальности. В моих программах, как > правило, любая коллелкция — это часть какого-либо класса, и она > используется там исключительно для конкретных нужд класса. Методы класса > реализуют конкретные алгоритмы, связанные с конкретной предметной > областью, и как правило очень сильно заточены под логику этой предметной > области. Иными словами, алгоритмы обработки конкретной коллекции > совершенно бесполезны и бессмысленны для другой коллекции в другом классе. > > С точки зрения замены типов коллекций. Часто вижу такой аргумент: если > вдруг захочется заменить vector на list или наоборот, то все что нужно > сделать — просто заменить тип в объявлении объекта-коллекции.
Это кстати почти миф. Не всегда можно один заменять на другой. Меерс описывал.
> Народ, вот это мне как минимум непонятно... Выбор типа для коллекции — > фундаментальная вещь, которая должна делаться один раз в самом начале > разработки того или иного класса. Мне и в бреду не придет мысль менять > list на vector, если я знаю КАК ИМЕННО я работаю с коллекцией, для каких > целей я ее вводил в программ и для чего она там используется...
+1 +2 ... +100
> И еще. Для работы с GUI часто требуется привязать какие-то "итераторы" к > элементам контролов (методы типа SetItemData()/GetItemData()). POSITION > — это гарантированно 4-байтовое значение, которое легко привязывается > простым приведением типов.
А это вообще хаки грязные. Ты не должен думать, что знаешь, что POSITION
— это гарантированно 4-байтовое значение
Главное, в общем, не это всё. А удобство коллекций с практической точки зрения.
STL академичен и неудобен. Раскрывать идею не буду, думаю и так все согласны.
Здравствуйте, MasterZiv, Вы писали:
MZ>Юрий Жмеренецкий wrote: >> MZ>Ничем не хуже. >> >> В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет >> линейной, поэтому сложность перебора всех элементов с помощью этого >> интерфейса будет квадратичной.
MZ>Так а не надо одними алгоритмами обрабатывать и контейнеры с произвольным MZ>доступом, и с последовательным.
Как будет выглядеть алгоритм перебора всех элементов списка с использованием предложенного интерфейса за линейное время?
Вот нельзя было бы в С арифметические операции с указателями делать, и не стали бы реализовывать "итератор произвольного доступа" — для совместимости с указателем. J>Произвольные скачки по массиву — это действительно естественный способ обращаться к его элементам, что в С++, что в Фортране.
Что мне даст красивый итератор, для создания которого придется отводить отдельную память, тратить быстродействие на кучу его внутренних проверок (валидность, равенства нулю/не нулю и т.д и т.п.), обработчиков исключений и т.д. На практике мне обычно бывает нужно всего пара функций для доступа к данным коллекции. ИМХО, дешево-сердито.
Перекуём баги на фичи!
