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

31.07.10 12:14: Перенесено модератором из 'C/C++. Прикладные вопросы' — Кодт
Re: Зачем нужен итератор?
От: Vamp Россия  
Дата: 23.07.10 16:25
Оценка:
ND>Заранее спасибо!
Основная польза — итераторы позволяют строить алогритмы, независимые от контейнера. Передаешь в алогоритм пару итераторов — и алогритм выполняет с итераторами, а не с контейнером, таким образом, становится контейнеро-независимым.
Да здравствует мыло душистое и веревка пушистая.
Re: Зачем нужен итератор?
От: potapov.d  
Дата: 23.07.10 16:43
Оценка: 7 (2) :)
Здравствуйте, ND322, Вы писали:

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

ND>Заранее спасибо!

Вы отстали от жизни, согласно последним инновационным предложениям от классиков итератор не_нужен.
Re[2]: Зачем нужен итератор?
От: morm Россия  
Дата: 23.07.10 17:47
Оценка:
Здравствуйте, potapov.d, Вы писали:

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


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

ND>>Заранее спасибо!

PD>Вы отстали от жизни, согласно последним инновационным предложениям от классиков итератор не_нужен.


Андрей как всегда радикален Пока, однако, они используются. MType::iterator itr = find_if(v.begin(),v.end(),boost::bind(&foo, boost::lambda::_1));

Или например в map без итераторов сложно выкрутиться в таком случае:

class A
{
  MType m;
  public:
    typedef map<int, float> MType;
    float GetVal(int key) const
    {
       MType::const_iterator itr = m.find(key);
       if(itr == m.end())
         throw MErr(string("Нет элемента с номером ") + lexical_cast<string>(key));
       return itr->second;
    }
}
Re[3]: Зачем нужен итератор?
От: c-smile Канада http://terrainformatica.com
Дата: 23.07.10 17:56
Оценка:
Здравствуйте, morm, Вы писали:

M>Или например в map без итераторов сложно выкрутиться в таком случае:


M>
M>class A
M>{
M>  MType m;
M>  public:
M>    typedef map<int, float> MType;
M>    float GetVal(int key) const
M>    {
M>       MType::const_iterator itr = m.find(key);
M>       if(itr == m.end())
M>         throw MErr(string("Нет элемента с номером ") + lexical_cast<string>(key));
M>       return itr->second;
M>    }
M>}

M>


map<int, float> есть коллекция pair<int, float>. Если есть коллекция есть значит есть range.

MType::range r = m.find(key);
if(r.empty())
  throw MErr(string("Нет элемента с номером ") + lexical_cast<string>(key));
return r.front().second;
Re: Зачем нужен итератор?
От: minorlogic Украина  
Дата: 23.07.10 21:23
Оценка:
Здравствуйте, ND322, Вы писали:

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

ND>Заранее спасибо!

Итератор это абстракция позволяющая представить МНОЖЕСТВО однотипных объектов. Абстракция позволяющая работать как с указателями в памяти так и с очень сложными коллекциями(графы например).

Т.е. это унифицированный интерфейс доступа к элементам множетсва. Не больше ни меньше.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re: Зачем нужен итератор?
От: ononim  
Дата: 23.07.10 21:44
Оценка:
> В чем преимущество перед обыкновенным CList\TList, который перебирает сои элементы сам без всяких сложных конструкций.
Итераторы используются для итерирования произвольных контейнеров.
Итерация при помощи индексов (типа в CList) эффективно работает лишь для тех контейнеров, у которых доступ к произвольному элементу по индексу возможен за константное время. Но имеется туева хуча других типов контейнеров, где индексы ни к селу ни к городу, тот же связный список, не говоря уж о деревьях. Так вот, чтобы не вводить для каждого типа контейнера свой способ итерации и чтобы можно было использовать обобщенные алгоритмы (к примеру, поиск совпадающего элемента последовательным перебором) для различных типов контейнеров были придуманы итераторы. Сорри за небольшой каламбуризм.
И кстати никакой сложности на самом деле нету — просто немного непривычно. И вообще доступ по индексу на самом деле сложнее — ведь тут присутствует дополнительное понятия "индекс" которое может быть совершенно неинтересно с т.з. алгоритма который осуществляет доступ к контейнеру.

> Где используются эти пресловутые классы-итераторы?

Очень даже используется.
Как много веселых ребят, и все делают велосипед...
Re[4]: Зачем нужен итератор?
От: morm Россия  
Дата: 24.07.10 07:29
Оценка:
Здравствуйте, c-smile, Вы писали:

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


M>>Или например в map без итераторов сложно выкрутиться в таком случае:


M>>
M>>class A
M>>{
M>>  MType m;
M>>  public:
M>>    typedef map<int, float> MType;
M>>    float GetVal(int key) const
M>>    {
M>>       MType::const_iterator itr = m.find(key);
M>>       if(itr == m.end())
M>>         throw MErr(string("Нет элемента с номером ") + lexical_cast<string>(key));
M>>       return itr->second;
M>>    }
M>>}

M>>


CS>map<int, float> есть коллекция pair<int, float>. Если есть коллекция есть значит есть range.


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>


Это понятно, я написал как сейчас. Но range таскает за собой лишний функционал в этом примере.
Слишком толсто
От: rm822 Россия  
Дата: 24.07.10 08:04
Оценка: +1 :)
сабж
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[2]: Зачем нужен итератор?
От: ND322  
Дата: 24.07.10 17:02
Оценка:
Здравствуйте, ononim, Вы писали:

>> В чем преимущество перед обыкновенным CList\TList, который перебирает сои элементы сам без всяких сложных конструкций.

O>Итераторы используются для итерирования произвольных контейнеров.
O>Итерация при помощи индексов (типа в CList) эффективно работает лишь для тех контейнеров, у которых доступ к произвольному элементу по индексу возможен за константное время. Но имеется туева хуча других типов контейнеров, где индексы ни к селу ни к городу, тот же связный список, не говоря уж о деревьях. Так вот, чтобы не вводить для каждого типа контейнера свой способ итерации и чтобы можно было использовать обобщенные алгоритмы (к примеру, поиск совпадающего элемента последовательным перебором) для различных типов контейнеров были придуманы итераторы. Сорри за небольшой каламбуризм.
O>И кстати никакой сложности на самом деле нету — просто немного непривычно. И вообще доступ по индексу на самом деле сложнее — ведь тут присутствует дополнительное понятия "индекс" которое может быть совершенно неинтересно с т.з. алгоритма который осуществляет доступ к контейнеру.

>> Где используются эти пресловутые классы-итераторы?

O>Очень даже используется.

Я понимаю, ЧТО такое итератор, я понимаю (но не использую пока на практике), что такое графы, очереди, двусвязные списки и т.д. и .п. Я не очень понимаю, в каких конкретно областях эти самые итераторы используются на практике? Вот я и спросил, в нажедже, что опытные люди просто приведут пример из жизни. Лично я вижу единственное реальное преимущество — мы можем для одной структуры (списка, дерева, ассоциативного массива и т.д.) иметь несколько текущих позиций и перебирать объекты в этих контейнерных структурах независимо — ну, например, имеем один стек, но вершин у него несколько и живут они независимо Правда, у меня за всю практическую деятельность, ни в одной реальной программе пока такой необходимости не возникало. Если бы возникло,я бы наверное тупо ввел две переменные-указателя на соответствующие текущие значения, да и перебирал бы себе дальше — дешево-сердито
Re[3]: Зачем нужен итератор?
От: ononim  
Дата: 24.07.10 18:09
Оценка:
ND>Я понимаю, ЧТО такое итератор, я понимаю (но не использую пока на практике), что такое графы, очереди, двусвязные списки и т.д. и .п. Я не очень понимаю, в каких конкретно областях эти самые итераторы используются на практике? Вот я и спросил, в нажедже, что опытные люди просто приведут пример из жизни.
Да пажалста. Я системщик. Обертки-итераторы вокруг FindFirstFile/FindNextFile, перечисление процессов, модулей, потоков etc — все это есть и применяется в нашем текущем проекте.

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

Итератор это обобщенное понятие, придуманное для того чтобы обобщить методы последовательного доступа к элементам различных контейнеров и ничего более.
Что во первых позволяет не за??ирать голову программиста особенностями потрохов различных контейнеров, во вторых позволяет использовать один и тот же обобщенный (читай — шаблонный) С++ код для работы с различными контейнерами. То бишь читай здесь — http://www.cppreference.com/wiki/stl/algorithm/start и обрати внимание что приведенным там алгоритмам пофиг элементы какого контейнера им скармливают.
Как много веселых ребят, и все делают велосипед...
Re[5]: Зачем нужен итератор?
От: Vain Россия google.ru
Дата: 24.07.10 19:10
Оценка:
Здравствуйте, morm, Вы писали:

CS>>map<int, float> есть коллекция pair<int, float>. Если есть коллекция есть значит есть range.

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>>

M>Это понятно, я написал как сейчас. Но range таскает за собой лишний функционал в этом примере.
Так и итераторов будет два, если функцию find обернуть — придётся всегда пару итераторов возвращать, тогда как range уже какбе пара итераторов.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re: Слишком толсто
От: Vain Россия google.ru
Дата: 24.07.10 19:17
Оценка:
Здравствуйте, rm822, Вы писали:

R>сабж

Вопросы новичков в STL воспринимаются уже как троллизм? однако.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[2]: Слишком толсто
От: rm822 Россия  
Дата: 24.07.10 21:14
Оценка: -1
V>Вопросы новичков в STL воспринимаются уже как троллизм? однако.
Он нам предлагает сравнить STL c MFC-обрубками, которые тоже построены на итераторах, тока называются они там POSITION.

скопипастил код из MSDN, ну и где простота vs stl и отсутствие итераторов?
CTypedPtrList<CObList, CPerson*> myList;

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

CMap<CString, LPCTSTR, CPerson*, CPerson*> myMap;
CPerson myPerson;

myMap.SetAt(_T("Bill"), &myPerson);
POSITION pos = myMap.GetStartPosition();
while(pos != NULL)
{
   CPerson* pPerson;
   CString string;
   // Get key (string) and value (pPerson)
   myMap.GetNextAssoc(pos, string, pPerson);
   // Use string and pPerson
}
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: Слишком толсто
От: Vain Россия google.ru
Дата: 25.07.10 01:05
Оценка: 1 (1) -1 :)))
Здравствуйте, rm822, Вы писали:

V>>Вопросы новичков в STL воспринимаются уже как троллизм? однако.

R>Он нам предлагает сравнить STL c MFC-обрубками, которые тоже построены на итераторах, тока называются они там POSITION.
Как минимум для итераторов дребуется отдельный класс, POSITION это не класс, т.е. у него нет методов. С этой позиции MFC проще, т.к. меньше сущностей.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re: Зачем нужен итератор?
От: Vain Россия google.ru
Дата: 25.07.10 01:20
Оценка:
Здравствуйте, ND322, Вы писали:

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

Итераторы, это результат попытки унифицировать доступ к элементу, а также унифицировать способ обхода (итерации по контейнеру) контейнера. Таким образом один и тот же способ будет необходим и достаточен, чтобы обойти конейнеры любых типов. Для этого тостаточно, чтобы контейнер объявлял определённый набор методов (begin/end) и эти методы работали с промежуточным объектом — итератором. Тогда способ доступа к элементу и итерации по контейнеру всегда будет одинаковыми.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re: Зачем нужен итератор?
От: McSeem2 США http://www.antigrain.com
Дата: 25.07.10 04:24
Оценка: 1 (1) +1 -3 :)))
Здравствуйте, ND322, Вы писали:

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



Итераторы — это бездарная попытка использовать C++ не по назначению. Теоретически это прикольно, но на практике ничего кроме пожизненного рака головы не получается. Посмотрите на буст — это же просто помойка. Развитие C++ должно закончиться так же как Си и Фортрана. Любые попытки его развивать делают только хуже. В этом плане язык Си — более православный. Он стандартизирован, легок в имплементации и все хорошо. C++ — это монстр и кадавр, обеспокоенный желудочно.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re: Зачем нужен итератор?
От: LaptevVV Россия  
Дата: 25.07.10 06:01
Оценка:
Здравствуйте, ND322, Вы писали:

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

ND>Заранее спасибо!
Определение:
Итератор — это объект, обеспечивающий последовательный доступ к элементам контейнера.
Вот и все.
В этом качестве он и нужен. Обозвать можно по-разному. ъ
Но все равно некая сущность, обеспечивающая последовательный доступ к элементам контейнера, нужна. ИМХО — это плюс.
В С++ его сделали произвольным — по аналогии с указателем.
ИМХО — это минус.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[2]: Зачем нужен итератор?
От: McSeem2 США http://www.antigrain.com
Дата: 25.07.10 06:52
Оценка:
Здравствуйте, LaptevVV, Вы писали:

LVV>Итератор — это объект, обеспечивающий последовательный доступ к элементам контейнера.

LVV>Вот и все.

А тогда что такое "итератор произвольного доступа"? А такой есть и даже свойство такое есть. Это оксиморон.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[3]: Зачем нужен итератор?
От: LaptevVV Россия  
Дата: 25.07.10 07:40
Оценка:
Здравствуйте, McSeem2, Вы писали:
LVV>>Итератор — это объект, обеспечивающий последовательный доступ к элементам контейнера.
LVV>>Вот и все.
MS>А тогда что такое "итератор произвольного доступа"? А такой есть и даже свойство такое есть. Это оксиморон.
Я таких иностранных слов не знаю...
Но В С++ многое сделано в угоду пресловутой обратной совместимости с С — это самая большая ошибка Страуструпа.
Вот и итераторы сделаны по аналогии с указателем — "естественным итератором" для массивов.
ИМХО — это дебилизм — обеспечение обратной совместимости. "Хотели — как лучше, а получилось — как всегда"(с)
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[2]: Зачем нужен итератор?
От: Went  
Дата: 25.07.10 12:44
Оценка:
Здравствуйте, McSeem2, Вы писали:

MS>Итераторы — это бездарная попытка использовать C++ не по назначению. Теоретически это прикольно, но на практике ничего кроме пожизненного рака головы не получается. Посмотрите на буст — это же просто помойка. Развитие C++ должно закончиться так же как Си и Фортрана. Любые попытки его развивать делают только хуже. В этом плане язык Си — более православный. Он стандартизирован, легок в имплементации и все хорошо. C++ — это монстр и кадавр, обеспокоенный желудочно.


Pokimon, залогиньтесь.
Re[4]: Зачем нужен итератор?
От: jazzer Россия Skype: enerjazzer
Дата: 25.07.10 13:28
Оценка:
Здравствуйте, LaptevVV, Вы писали:

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

LVV>>>Итератор — это объект, обеспечивающий последовательный доступ к элементам контейнера.
LVV>>>Вот и все.
MS>>А тогда что такое "итератор произвольного доступа"? А такой есть и даже свойство такое есть. Это оксиморон.
LVV>Я таких иностранных слов не знаю...
Стыдись, ты ж преп!

LVV>Но В С++ многое сделано в угоду пресловутой обратной совместимости с С — это самая большая ошибка Страуструпа.

LVV>Вот и итераторы сделаны по аналогии с указателем — "естественным итератором" для массивов.
LVV>ИМХО — это дебилизм — обеспечение обратной совместимости. "Хотели — как лучше, а получилось — как всегда"(с)

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

А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками.
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[5]: Зачем нужен итератор?
От: McSeem2 США http://www.antigrain.com
Дата: 25.07.10 14:06
Оценка:
Здравствуйте, jazzer, Вы писали:

J>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками.


Коллега на работе написал итератор. Есть некая сильно упакованная структура данных, представляющая набор сегментов полигона с кривыми. Все, что требуется — последовательное чтение, типа "дай мне следующий сегмент". Сегменты бывают разные — типа отрезок, квадратическкая курва или кубическая курва. Казалось бы — итератор для этого — то, что доктор прописал. Но получилось настолько все кучеряво и длинно, что разобраться в этом теперь нетривиально. Получилась ненужная усложнистика на ровном месте. На самом деле все гораздо хуже — есть набор этих полигонов, для них используется итератор более высокого уровня. А сверху еще есть layers, для них — еще более отдельный итератор. В результате приключился взрыв на макаронной фабрике в виде недоступного пониманию спагетти-кода. Всех программистов в радиусе офиса засыпало макаронами. Такие дела.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[6]: Зачем нужен итератор?
От: jazzer Россия Skype: enerjazzer
Дата: 25.07.10 14:23
Оценка: :)
Здравствуйте, McSeem2, Вы писали:

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


J>>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками.


MS>Коллега на работе написал итератор. Есть некая сильно упакованная структура данных, представляющая набор сегментов полигона с кривыми. Все, что требуется — последовательное чтение, типа "дай мне следующий сегмент". Сегменты бывают разные — типа отрезок, квадратическкая курва или кубическая курва. Казалось бы — итератор для этого — то, что доктор прописал. Но получилось настолько все кучеряво и длинно, что разобраться в этом теперь нетривиально. Получилась ненужная усложнистика на ровном месте. На самом деле все гораздо хуже — есть набор этих полигонов, для них используется итератор более высокого уровня. А сверху еще есть layers, для них — еще более отдельный итератор. В результате приключился взрыв на макаронной фабрике в виде недоступного пониманию спагетти-кода. Всех программистов в радиусе офиса засыпало макаронами. Такие дела.


Если честно, я мало что понял

Но вообще, Boost.Iterator сильно помогает сократить количество кода — достаточно просто пару функций реализовать (типа dereference), а все операторы она сама сделает.
Но если сами эти две функции получаются сильно кучерявыми — тады ой

Но вообще, конечно, имеет смысл в самих контейнерах дополнительно предусматривать всякие методы типа for_each (так же, как сейчас предоставляется sort) — они зачастую могут быть сделаны на порядок проще аналогичного кода на итераторах.
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[4]: Зачем нужен итератор?
От: ND322  
Дата: 25.07.10 18:00
Оценка: :)
Здравствуйте, ononim, Вы писали:

ND>>Я понимаю, ЧТО такое итератор, я понимаю (но не использую пока на практике), что такое графы, очереди, двусвязные списки и т.д. и .п. Я не очень понимаю, в каких конкретно областях эти самые итераторы используются на практике? Вот я и спросил, в нажедже, что опытные люди просто приведут пример из жизни.

O>Да пажалста. Я системщик. Обертки-итераторы вокруг FindFirstFile/FindNextFile, перечисление процессов, модулей, потоков etc — все это есть и применяется в нашем текущем проекте.

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

O>Итератор это обобщенное понятие, придуманное для того чтобы обобщить методы последовательного доступа к элементам различных контейнеров и ничего более.
O>Что во первых позволяет не за??ирать голову программиста особенностями потрохов различных контейнеров, во вторых позволяет использовать один и тот же обобщенный (читай — шаблонный) С++ код для работы с различными контейнерами. То бишь читай здесь — http://www.cppreference.com/wiki/stl/algorithm/start и обрати внимание что приведенным там алгоритмам пофиг элементы какого контейнера им скармливают.

Понятно.
FindFirst/FindNext использовал неоднократно (тоже системщик), хотя итератор пока к ним прикрутить как-то желания не возникало. Подумаю.
Лично я ничего против итераторов не имею — мне лишь интересно, насколько широко народ их реально использует (ну, то есть, процентное соотношение объема текста умной книжки по СРР, посвященного итераторам к проценту реального их использования в жизни).

Касаемо выгоды шаблонного С++ кода для работы с различными контейнерами — ну, ИМХО, я опять же сужу по практике. При условии, что итератор готовый библиотечный и мы сами его не пишем, остается проблема ресурсов, которые он сжирает за свое существование. По современным меркам — мелочь. Но вот я когда-о еще в институте писал всяике полезняшки на MSVC. Потом по работе пришлось что-то делать на Delphi. Когда было нужно, залезал в свой старый код, брал готовые отлаженные куски (ну там, со строками работа, с файловыми операциями и т.д.), менял {} на begin-end и экономил на этом кучу времени. А написал бы я красиво с шаблонами, итераторами и прочими оптимайзами — переносимость код бы точно потерял как в ту, так и в другую сторону. Но, повторюсь, наверняка есть и свои плюсы внешних классов-итераторов!
Re[4]: Слишком толсто
От: ND322  
Дата: 25.07.10 18:08
Оценка:
Здравствуйте, Vain, Вы писали:

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


V>>>Вопросы новичков в STL воспринимаются уже как троллизм? однако.

R>>Он нам предлагает сравнить STL c MFC-обрубками, которые тоже построены на итераторах, тока называются они там POSITION.
V>Как минимум для итераторов дребуется отдельный класс, POSITION это не класс, т.е. у него нет методов. С этой позиции MFC проще, т.к. меньше сущностей.
Точно, в MFC POSITION — просто переменная, а не класс. А если вы возьмете Борландовский TList, то там еще проще.
Re[7]: Зачем нужен итератор?
От: ND322  
Дата: 25.07.10 18:19
Оценка:
Здравствуйте, jazzer, Вы писали:

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


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


J>>>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками.


MS>>Коллега на работе написал итератор. Есть некая сильно упакованная структура данных, представляющая набор сегментов полигона с кривыми. Все, что требуется — последовательное чтение, типа "дай мне следующий сегмент". Сегменты бывают разные — типа отрезок, квадратическкая курва или кубическая курва. Казалось бы — итератор для этого — то, что доктор прописал. Но получилось настолько все кучеряво и длинно, что разобраться в этом теперь нетривиально. Получилась ненужная усложнистика на ровном месте. На самом деле все гораздо хуже — есть набор этих полигонов, для них используется итератор более высокого уровня. А сверху еще есть layers, для них — еще более отдельный итератор. В результате приключился взрыв на макаронной фабрике в виде недоступного пониманию спагетти-кода. Всех программистов в радиусе офиса засыпало макаронами. Такие дела.


J>Если честно, я мало что понял


J>Но вообще, Boost.Iterator сильно помогает сократить количество кода — достаточно просто пару функций реализовать (типа dereference), а все операторы она сама сделает.

J>Но если сами эти две функции получаются сильно кучерявыми — тады ой


J>Но вообще, конечно, имеет смысл в самих контейнерах дополнительно предусматривать всякие методы типа for_each (так же, как сейчас предоставляется sort) — они зачастую могут быть сделаны на порядок проще аналогичного кода на итераторах.


Ну, вы же понимаете, что "она сама сделает" вовсе не означает сокращения количества кода, как Вы написали. Сократите в одном месте — удлините в другом Если мне надо пару десятков параметров массива информационного обмена по MIL-1553 запихать в список и потом находить в них нужный, это три-четыре строчки моего пользовательского кода. Микро- если не наносекунды машинного времени. Та же операция через крутую библиотеку с внешним иетратором уложится в 2 строки пользовательского кода. Но взамен, я получу 200 строк кода библиотечного, где будут сотни ненужных проверок, вызовов, подвызовов, создание монстрозных объектов в памяти и т.д. и т.п. Не дай бог, придется это дело потом трассировать, если что не так! Вот я и спрашиваю, скажем, Вас, где, в каких практических случаях у вас на практике была необходимость использования этих шаблонных чудо-конктейнеров с внешними итераторами? Можете ли вы, анализируя сейчас те случаи, что-либо сказать об их эффективности?
Re[8]: Зачем нужен итератор?
От: jazzer Россия Skype: enerjazzer
Дата: 25.07.10 18:33
Оценка: :)
Здравствуйте, ND322, Вы писали:

J>>Но вообще, Boost.Iterator сильно помогает сократить количество кода — достаточно просто пару функций реализовать (типа dereference), а все операторы она сама сделает.


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


Мне заклинание "MIL-1553" ни о чем не говорит, сорри.
Тем не менее, вы знакомы с CRTP?
Там нулевой оверхед, и Boost.Iterator сделана именно через него.
Так что очень интересно, где вы там нашли монструозные объекты и прочая

Насчет практических случаев — да, использовал многажды, никаких нареканий к эффективности, ибо CRTP.
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[6]: Зачем нужен итератор?
От: morm Россия  
Дата: 25.07.10 18:45
Оценка: :)
Здравствуйте, Vain, Вы писали:

V>Так и итераторов будет два, если функцию find обернуть — придётся всегда пару итераторов возвращать, тогда как range уже какбе пара итераторов.


чего й то???
Re[7]: Зачем нужен итератор?
От: Vain Россия google.ru
Дата: 25.07.10 19:13
Оценка:
Здравствуйте, morm, Вы писали:

V>>Так и итераторов будет два, если функцию find обернуть — придётся всегда пару итераторов возвращать, тогда как range уже какбе пара итераторов.

M>чего й то???
А как ты итератор на валидность проверишь?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[5]: Слишком толсто
От: Vain Россия google.ru
Дата: 25.07.10 19:14
Оценка:
Здравствуйте, ND322, Вы писали:

V>>>>Вопросы новичков в STL воспринимаются уже как троллизм? однако.

R>>>Он нам предлагает сравнить STL c MFC-обрубками, которые тоже построены на итераторах, тока называются они там POSITION.
V>>Как минимум для итераторов дребуется отдельный класс, POSITION это не класс, т.е. у него нет методов. С этой позиции MFC проще, т.к. меньше сущностей.
ND>Точно, в MFC POSITION — просто переменная, а не класс.
typedef
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[9]: Зачем нужен итератор?
От: night beast СССР  
Дата: 26.07.10 04:28
Оценка:
Здравствуйте, jazzer, Вы писали:

J>Мне заклинание "MIL-1553" ни о чем не говорит, сорри.

J>Тем не менее, вы знакомы с CRTP?
J>Там нулевой оверхед, и Boost.Iterator сделана именно через него.
J>Так что очень интересно, где вы там нашли монструозные объекты и прочая

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

J>Насчет практических случаев — да, использовал многажды, никаких нареканий к эффективности, ибо CRTP.


это да
Re: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 26.07.10 06:50
Оценка: +1 -3
ND322 wrote:

> Умные книжки много пишут о прелестях итераторов для различных

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

По факту итераторы -- говно.

Но когда говорят о их прелестях, то имеют в виду, что они позволяют
алготирмам, которые обрабатывают данные, абстрагироваться от
структуры тех данных, которые они обрабатывают. В этом их "прелесть"
с точки зрения дизайнеров STL.
Posted via RSDN NNTP Server 2.1 beta
Re[5]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 26.07.10 07:40
Оценка:
ND322 wrote:

> готовый библиотечный и мы сами его не пишем, остается проблема ресурсов,

> которые он сжирает за свое существование. По современным меркам —
> мелочь. Но вот я когда-о еще в институте писал всяике полезняшки на

В 80% случаем, а может и в 90, итератор в реализации -- это лиш
прикрытый фиговым листком указатель. Так что никакой накладухи там
нет.

Просто итератор, выделенный как абстракция, позволяет делать их
разными, в том числе и тебе самому.
Posted via RSDN NNTP Server 2.1 beta
Re[5]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 26.07.10 07:45
Оценка:
jazzer wrote:

> Произвольные скачки по массиву — это действительно естественный способ

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

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

Ничем не хуже.
Posted via RSDN NNTP Server 2.1 beta
Re: Зачем нужен итератор?
От: x-code  
Дата: 26.07.10 07:46
Оценка: +1
Здравствуйте, ND322, Вы писали:

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


Кстати, интересный вопрос. Давайте сравним MFC CList с POSITION и std:list с его итераторами.
Пользуюсь и тем и другим, но как ни странно, больше нравится CList. Даже сделал с MFC'шных классов кроссплатформенную реализацию.

Итератор — это отдельная сущность, близкая к указателям, но обладающая своими методами. Итераторы, в отличие от указателей, могут быть устроены весьма нетривиально.
POSITION — это всего лишь 4-байтовое значение, с которым НИЧЕГО НЕЛЬЗЯ СДЕЛАТЬ, не имея собственно объекта-коллекции. POSITION идеологически ближе к индексу массива.
Лично мне немного понятнее, когда я вижу в коде 'arr[i]', чем когда '*ptr'; хотя с точки зрения производительности указатели будут быстрее.
Итераторы УНИВЕРСАЛЬНЕЕ, но НЕ НАГЛЯДНЕЕ... В том смысле, что запись с участием объекта-коллекции лишний раз подчеркивает, ЧТО ИМЕННО мы делаем в этой строчке. Не просто берем из памяти какое-то значение, а берем конкретно i-тое значение из массива с конкретным именем.

Итератор можно передать куда-нибудь в функцию сам по себе, без контейнера, и делать с ним там что угодно. Впрочем, не совсем что угодно... для собственно ИТЕРАЦИИ нужен еще один итератор — на конец коллекции.
В случае с MFC CList требуется передавать и итератор, и ссылку на саму коллекцию.

Итераторы синтаксически подобны указателям, т.е. используются переопределенные операторы ++, --, *. MFC использует методы GetAt(), GetNext(), GetPrev(). Вариант с итераторами, опять-таки, универсальнее... Теоретически, можно заменить итератор на обычный указатель, и все должно работать.
Но мне в принципе не нравится переопределение операторов. Я вижу 'p++', и как я угадаю, будет ли это простая команда inc, или вызов целого метода? Т.е. вариант с методами GetAt() и т.д. лично мне нравится больше — именно тем, что там все записывается ЯВНО.

Основной аргумент в пользу итераторов из предложенных выше — итераторы универсальны, т.е. можно одними и теми же алгоритмами обрабатывать и массивы, и списки, и хз что еще. Однако у меня возникает вопрос практической необходимости такой универсальности. В моих программах, как правило, любая коллелкция — это часть какого-либо класса, и она используется там исключительно для конкретных нужд класса. Методы класса реализуют конкретные алгоритмы, связанные с конкретной предметной областью, и как правило очень сильно заточены под логику этой предметной области. Иными словами, алгоритмы обработки конкретной коллекции совершенно бесполезны и бессмысленны для другой коллекции в другом классе.

С точки зрения замены типов коллекций. Часто вижу такой аргумент: если вдруг захочется заменить vector на list или наоборот, то все что нужно сделать — просто заменить тип в объявлении объекта-коллекции.
Народ, вот это мне как минимум непонятно... Выбор типа для коллекции — фундаментальная вещь, которая должна делаться один раз в самом начале разработки того или иного класса. Мне и в бреду не придет мысль менять list на vector, если я знаю КАК ИМЕННО я работаю с коллекцией, для каких целей я ее вводил в программ и для чего она там используется...

И еще. Для работы с GUI часто требуется привязать какие-то "итераторы" к элементам контролов (методы типа SetItemData()/GetItemData()). POSITION — это гарантированно 4-байтовое значение, которое легко привязывается простым приведением типов. С итераторами такой номер не прокатит, это класс, который разумеется нельзя приводить к DWORD, void*, LPARAM и т.д.
На этот вопрос, кстати, мне так толком никто и не ответил.

Вероятно, истина как всегда где-то рядом, может быть посередине
Re[8]: Зачем нужен итератор?
От: ononim  
Дата: 26.07.10 10:29
Оценка: 1 (1) +1 -1
V>>>Так и итераторов будет два, если функцию find обернуть — придётся всегда пару итераторов возвращать, тогда как range уже какбе пара итераторов.
M>>чего й то???
V>А как ты итератор на валидность проверишь?
Проверять в программе надо только входные данные, ибо они не под вашим контролем. Итератор должен _быть_ валиден, ибо код который вы пишете под вашим контролем. Или нет?
Как много веселых ребят, и все делают велосипед...
Re[2]: Зачем нужен итератор?
От: ononim  
Дата: 26.07.10 10:31
Оценка:
XC>Лично мне немного понятнее, когда я вижу в коде 'arr[i]', чем когда '*ptr'; хотя с точки зрения производительности указатели будут быстрее.
XC>Итераторы УНИВЕРСАЛЬНЕЕ, но НЕ НАГЛЯДНЕЕ... В том смысле, что запись с участием объекта-коллекции лишний раз подчеркивает, ЧТО ИМЕННО мы делаем в этой строчке. Не просто берем из памяти какое-то значение, а берем конкретно i-тое значение из массива с конкретным именем.
А вот и нифиге. Мне индексы совершенно не наглядны. Я даже если пишу for(...) по массиву заданному голым указателем — использую арифметику указателей, а не индексы. Так что это просто дело привычки — для человека который годами в паскале/бейсике писал for i .... индекс будет конечно нагляднее, а вот для человека "со стороны" — совсем даже не факт.
Как много веселых ребят, и все делают велосипед...
Re[6]: Зачем нужен итератор?
От: saf_e  
Дата: 26.07.10 10:40
Оценка:
Здравствуйте, 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... При этом имейте в виду, что кто-то возможно захочет итерацию по коллекции в цикле...
Re[5]: Зачем нужен итератор?
От: LaptevVV Россия  
Дата: 26.07.10 12:11
Оценка:
Здравствуйте, jazzer, Вы писали:

MS>>>А тогда что такое "итератор произвольного доступа"? А такой есть и даже свойство такое есть. Это оксиморон.

LVV>>Я таких иностранных слов не знаю...
J>Стыдись, ты ж преп!

LVV>>Но В С++ многое сделано в угоду пресловутой обратной совместимости с С — это самая большая ошибка Страуструпа.
LVV>>Вот и итераторы сделаны по аналогии с указателем — "естественным итератором" для массивов.
LVV>>ИМХО — это дебилизм — обеспечение обратной совместимости. "Хотели — как лучше, а получилось — как всегда"(с)

J>Демагогия.

J>Совместимость с Си тут вообще ни при чем.
Еще как причем... Вот нельзя было бы в С арифметические операции с указателями делать, и не стали бы реализовывать "итератор произвольного доступа" — для совместимости с указателем. J>Произвольные скачки по массиву — это действительно естественный способ обращаться к его элементам, что в С++, что в Фортране.
J>Свойство массива как структуры данных такое.
Ага. Только обеспечивается оно индексом, а не итератором.
J>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками.
Это от задачи зависит.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[6]: Зачем нужен итератор?
От: jazzer Россия Skype: enerjazzer
Дата: 26.07.10 14:39
Оценка:
Здравствуйте, LaptevVV, Вы писали:

J>>Демагогия.

J>>Совместимость с Си тут вообще ни при чем.
LVV>Еще как причем... Вот нельзя было бы в С арифметические операции с указателями делать, и не стали бы реализовывать "итератор произвольного доступа" — для совместимости с указателем. J>Произвольные скачки по массиву — это действительно естественный способ обращаться к его элементам, что в С++, что в Фортране.
J>>Свойство массива как структуры данных такое.
LVV>Ага. Только обеспечивается оно индексом, а не итератором.
без разницы, если не касаться вопросов инвалидации.
Индексы точно так же радостно вычитают и складывают.
Ты ж преп, вспомни методы прогонки, численного дифференцирования — они все в терминах итераторов (отношений индексов) формулируются, сплошь i и рядом i+1, i-1 и т.д.

J>>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками.

LVV>Это от задачи зависит.
что от задачи зависит? Скорость перемещения итератора произвольного доступа?
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[7]: Зачем нужен итератор?
От: LaptevVV Россия  
Дата: 26.07.10 16:40
Оценка:
Здравствуйте, jazzer, Вы писали:

J>>>Свойство массива как структуры данных такое.

LVV>>Ага. Только обеспечивается оно индексом, а не итератором.
J>без разницы, если не касаться вопросов инвалидации.
J>Индексы точно так же радостно вычитают и складывают.
J>Ты ж преп, вспомни методы прогонки, численного дифференцирования — они все в терминах итераторов (отношений индексов) формулируются, сплошь i и рядом i+1, i-1 и т.д.
1. Хорош уже бублик крошить на препода...
2. Не...
Зачем нам две одинаковых сущности на одном месте? Не следует плодить их без надобности.
Итератор — это именно для последовательного доступа предназначен. То, что он в С++ такой произвольный получился — это идеологически неправильно.
Но оправдано наличием указателей для массивов и идеей обратной совместимости.
J>>>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками.
LVV>>Это от задачи зависит.
J>что от задачи зависит? Скорость перемещения итератора произвольного доступа?
Не. Потребность в произвольном итераторе.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[6]: Зачем нужен итератор?
От: ND322  
Дата: 26.07.10 16:42
Оценка: -1
Здравствуйте, MasterZiv, Вы писали:

MZ>ND322 wrote:


>> готовый библиотечный и мы сами его не пишем, остается проблема ресурсов,

>> которые он сжирает за свое существование. По современным меркам —
>> мелочь. Но вот я когда-о еще в институте писал всяике полезняшки на

MZ>В 80% случаем, а может и в 90, итератор в реализации -- это лиш

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

MZ>Просто итератор, выделенный как абстракция, позволяет делать их

MZ>разными, в том числе и тебе самому.
Согласен. Но отдельный класс со своей иерархией, VMT, это все-таки накладуха плюс дополнительный код в котором можно насажать ошибок. Вопрос простой — любая нормальная библиотека, где есть контейнеры, будет иметь для них базовый класс (вероятнее всего, абстрактный). Если в нем предусмотреть методы перебора — next, prev, for_each, operator[]..., а потом их реализовывать в соответствующих потомках (очередь, список, стек...), то разве не будет того же эффекта но проще и дешевле? Разве не логично, что каждый контейнер сам знает, как себя итерировать, но использует для этого стандартный интерфейс?
Re[9]: Зачем нужен итератор?
От: ND322  
Дата: 26.07.10 17:01
Оценка:
Здравствуйте, 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 или использовали вообще как общий подход в работе с контейнерами?
Re[7]: Зачем нужен итератор?
От: ND322  
Дата: 26.07.10 17:05
Оценка:
Здравствуйте, 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... — реализовал бы соответствующие методы. В чем криминал?
Re[2]: Зачем нужен итератор?
От: ND322  
Дата: 26.07.10 17:13
Оценка: -1
Здравствуйте, x-code, Вы писали:
XC>Основной аргумент в пользу итераторов из предложенных выше — итераторы универсальны, т.е. можно одними и теми же алгоритмами обрабатывать и массивы, и списки, и хз что еще. Однако у меня возникает вопрос практической необходимости такой универсальности. В моих программах, как правило, любая коллелкция — это часть какого-либо класса, и она используется там исключительно для конкретных нужд класса. Методы класса реализуют конкретные алгоритмы, связанные с конкретной предметной областью, и как правило очень сильно заточены под логику этой предметной области. Иными словами, алгоритмы обработки конкретной коллекции совершенно бесполезны и бессмысленны для другой коллекции в другом классе.

Ну, собственно, это и был мой вопрос — если я работаю со списком, значит со списком, если с динамическим массивом (вектором), значит с вектором... Ну, собственно, лично я больше не с чем обычно и не работаю Что мне даст красивый итератор, для создания которого придется отводить отдельную память, тратить быстродействие на кучу его внутренних проверок (валидность, равенства нулю/не нулю и т.д и т.п.), обработчиков исключений и т.д. На практике мне обычно бывает нужно всего пара функций для доступа к данным коллекции. ИМХО, дешево-сердито.
Re[10]: Зачем нужен итератор?
От: jazzer Россия Skype: enerjazzer
Дата: 26.07.10 17:41
Оценка:
Здравствуйте, ND322, Вы писали:

J>>Насчет практических случаев — да, использовал многажды, никаких нареканий к эффективности, ибо CRTP.

ND>Да, знаком, хотя сам таких финтов ни разу не писал. Действительно, оверхед будет нулевой. Виртуельные методы без VMT А в каких случаях использовали, Если не секрет? Только в Boost или использовали вообще как общий подход в работе с контейнерами?

Как общий подход. Для своих контейнеров замечательно все работало (и продолжает замечательно работать).
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[8]: Зачем нужен итератор?
От: jazzer Россия Skype: enerjazzer
Дата: 26.07.10 17:45
Оценка:
Здравствуйте, 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 (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[3]: Зачем нужен итератор?
От: minorlogic Украина  
Дата: 26.07.10 18:02
Оценка: +3
Почитайте уже что нить про итераторы , а то с такой "knowlege base" дискутировать , тоскливо ...
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[9]: Зачем нужен итератор?
От: LaptevVV Россия  
Дата: 26.07.10 19:15
Оценка:
Здравствуйте, 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)
    {
        //...
    }
}
Re[6]: Зачем нужен итератор?
От: Юрий Жмеренецкий ICQ 380412032
Дата: 27.07.10 03:18
Оценка:
Здравствуйте, MasterZiv, Вы писали:

MZ>Вот кстати да. Почему бы не сделать было вместо итераторов

MZ>заклад на 3 функции :
MZ>-- size()
MZ>-- T& operator [] (unsigned n)
MZ>-- const T& operator [] (unsigned n) const

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


В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет линейной, поэтому сложность перебора всех элементов с помощью этого интерфейса будет квадратичной.
Re[8]: Зачем нужен итератор?
От: morm Россия  
Дата: 27.07.10 08:14
Оценка:
Здравствуйте, Vain, Вы писали:

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


V>>>Так и итераторов будет два, если функцию find обернуть — придётся всегда пару итераторов возвращать, тогда как range уже какбе пара итераторов.

M>>чего й то???
V>А как ты итератор на валидность проверишь?

Тупанул, да А как быть если возвращаешь, допустим, range, потом erase исходного контейнера. Что делать с end'ом в range??
Re[2]: Зачем нужен итератор?
От: Igore Россия  
Дата: 27.07.10 08:27
Оценка: +1 :)
Здравствуйте, 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 ...), такой код мне банально легче читать, сразу видно какая сущность лежит в контейнере.
Re[2]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 27.07.10 09:12
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Лично я вижу в STL-ных итераторах только один недостаток — их всегда нужно два, что удлиняет запись.


... причём из одного домена (контейнера), что ещё более удлинняет запись. Особенно, когда ссылка на контейнер приходит извне.
В этом плане, интервалы (range) более удобны.

Изредка требуется тройка итераторов: begin <= middle <= end, которую можно выразить двумя интервалами [begin,middle), [middle,end).
Правда, где тройка, там и четвёрка может потребоваться...

А>Я за то, чтобы итератор сам проверял свою валидность. Тогда можно будет писать:


Для этого
— либо итератор должен иметь доступ к end своего домена, или хранить другой признак вылета за диапазон (особенно, когда речь идёт о поддиапазонах)
— либо это однонаправленный итератор, так что все end можно считать эквивалентными, и заменять на специальное значение (например, NULL)

То есть, или оверхед, или неоправданные ограничения.

Было бы проще написать такой find, который возвращает пару (итератор, успешность).
Тот же самый lower_bound мог бы сразу сообщать, указывает итератор на "меньшее" или "равное" значение.
Перекуём баги на фичи!
Re[2]: Зачем нужен итератор?
От: Andrew S Россия http://alchemy-lab.com
Дата: 27.07.10 19:52
Оценка:
XC>И еще. Для работы с GUI часто требуется привязать какие-то "итераторы" к элементам контролов (методы типа SetItemData()/GetItemData()). POSITION — это гарантированно 4-байтовое значение, которое легко привязывается простым приведением типов. С итераторами такой номер не прокатит, это класс, который разумеется нельзя приводить к DWORD, void*, LPARAM и т.д.
XC>На этот вопрос, кстати, мне так толком никто и не ответил.

Используйте контейнеры из буст.мультииндекс. Там для списков есть возможность получить из указателя на элемент итератор.
http://www.boost.org/doc/libs/1_43_0/libs/multi_index/doc/tutorial/indices.html#iterator_to

Почему этого нет в STL — ответа на этот вопрос у меня нет. А штука нужная, иногда — очень.
http://www.rusyaz.ru/pr — стараемся писАть по-русски
Re[7]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 28.07.10 08:32
Оценка: -1
Юрий Жмеренецкий wrote:
> MZ>Ничем не хуже.
>
> В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет
> линейной, поэтому сложность перебора всех элементов с помощью этого
> интерфейса будет квадратичной.

Так а не надо одними алгоритмами обрабатывать и контейнеры с произвольным
доступом, и с последовательным. Ну, максимум будет в два раза больше
реализаций алгоритмов. Это проблема для СТАНДАРТНОЙ библиотеки, которая
один раз пишется ?
Posted via RSDN NNTP Server 2.1 beta
Re[2]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 28.07.10 08:43
Оценка: +1 -3
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 академичен и неудобен. Раскрывать идею не буду, думаю и так все согласны.
Posted via RSDN NNTP Server 2.1 beta
Re[2]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 28.07.10 08:48
Оценка: -1
Аноним 985 wrote:

> Это абсолютно стандартная вещь для программирования на C++, а не

> какая-то "новомодная". Скорее даже наоборот, "старомодная".

Ты это кому другому бы рассказывал. Именно "новомодная" эта штука.
Не было ни итераторов, ни вообще STL-я в С++ классическом.
Даже шаблонов не было.
Posted via RSDN NNTP Server 2.1 beta
Re[8]: Зачем нужен итератор?
От: Юрий Жмеренецкий ICQ 380412032
Дата: 28.07.10 08:51
Оценка:
Здравствуйте, MasterZiv, Вы писали:

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

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

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

MZ>доступом, и с последовательным.

Как будет выглядеть алгоритм перебора всех элементов списка с использованием предложенного интерфейса за линейное время?
Re[7]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 28.07.10 08:51
Оценка:
ND322 wrote:

> Вопрос простой — любая нормальная библиотека, где есть контейнеры, будет

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

Ты расскажи это создателям STL-я лучше. У них логика особая.
Posted via RSDN NNTP Server 2.1 beta
Re[3]: Зачем нужен итератор?
От: ononim  
Дата: 28.07.10 10:03
Оценка:
MZ>Ты это кому другому бы рассказывал. Именно "новомодная" эта штука.
MZ>Не было ни итераторов, ни вообще STL-я в С++ классическом.
MZ>Даже шаблонов не было.
этой "новомодной" штучкой мы на проекте живом пользуемся уже лет 7
если тебе попадаются прикладные проекты на С++ без stl могу только посочувствовать.
Как много веселых ребят, и все делают велосипед...
Re[9]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 28.07.10 11:20
Оценка:
Здравствуйте, morm, Вы писали:

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

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

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

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

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

В нашем случае, надо проверять не на валидность, а на сигнальность.
Перекуём баги на фичи!
Re[4]: Слишком толсто
От: Кодт Россия  
Дата: 28.07.10 11:29
Оценка: 1 (1)
Здравствуйте, Vain, Вы писали:

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


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

POSITION — непрозрачный указатель на узел контейнера, итератор — полупрозрачный указатель на узел (с перегруженными операциями *, ->, ++ и т.д.)
Итератор позволяет совершать некоторые действия напрямую, а хэндл и индекс — только в связке с самим контейнером.
Перекуём баги на фичи!
Re[8]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 28.07.10 11:54
Оценка:
Здравствуйте, ND322, Вы писали:

_>>А теперь придумайте такой же "лисопед" для list, set, map... При этом имейте в виду, что кто-то возможно захочет итерацию по коллекции в цикле...

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

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

Ибо:
— или контейнер stateful (хранит внутри текущую позицию), и за внешней красотой next(void)/prev(void) мы немедленно лишаемся не то что многопоточности, а даже реентерабельности
— или для итерирования требуется вынести эту текущую позицию наружу: либо в виде итератора (самостоятельного объекта с функциями доступа и навигации), либо в виде хэндла (аргумента этих самых функций Elem& at(POSITION), POSITION next(POSITION))
Перекуём баги на фичи!
Re[9]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 28.07.10 15:49
Оценка:
Юрий Жмеренецкий wrote:

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

> использованием предложенного интерфейса за линейное время?

Я не предлагаю ТОТ ЖЕ алгоритм перебора писать, и С ТЕМИ ЖЕ
функциями. Можно -- давайте те же. Нельзя -- напишим другие,
с другими функциями доступа к коллекции, в чём проблема ?
Даже если они не будут выглядеть одинаково снаружи -- не
проблема, а ещё и лучше -- сразу видно, что контейнеры разные.
Posted via RSDN NNTP Server 2.1 beta
Re[4]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 28.07.10 15:52
Оценка:
ononim wrote:

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


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

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

> посочувствовать.

Да нет у меня таких. Просто и до STL-я и шаблонов С++ жил себе
радостно и не тужил особо. Да, плохо, что не было хорошей стандартной
библиотеки, но её и сейчас нет (хорошей).
Posted via RSDN NNTP Server 2.1 beta
Re[8]: Зачем нужен итератор?
От: ND322  
Дата: 28.07.10 17:07
Оценка:
Здравствуйте, MasterZiv, Вы писали:

MZ>ND322 wrote:


>> Вопрос простой — любая нормальная библиотека, где есть контейнеры, будет

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

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

Ну, хорошо хоть е один я так думаю. А то я уж решил, что совсем ничего не рублю, раз у меня такие вопросы возникают
Re[5]: Зачем нужен итератор?
От: ononim  
Дата: 28.07.10 17:12
Оценка: +2 -1 :)
MZ>Да нет у меня таких. Просто и до STL-я и шаблонов С++ жил себе
MZ>радостно и не тужил особо. Да, плохо, что не было хорошей стандартной
MZ>библиотеки, но её и сейчас нет (хорошей).
ясно, не перешагнул барьер между "мля, как же все непривычно" и "а блин, как я раньше без этого жил"
ЗЫ А меня от всего МФСшного, включая CList несварение желудка случается. Более отстойной библиотеки чем MFC пожалуй не найти.
Как много веселых ребят, и все делают велосипед...
Re[9]: Зачем нужен итератор?
От: ND322  
Дата: 28.07.10 17:15
Оценка: -1
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, 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-й элемент списка из разных потоков. Правда, я это делал от силы раз или два... Вопрос, насколько широк круг таких задач на практике?
Re[9]: Зачем нужен итератор?
От: ND322  
Дата: 28.07.10 17:17
Оценка:
Здравствуйте, Юрий Жмеренецкий, Вы писали:

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


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

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

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

MZ>>доступом, и с последовательным.

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

Не понял, а если те же функции сидят в итераторе в виде самостоятельного класса, у них время перебора будет линейным?
Re[4]: Зачем нужен итератор?
От: ND322  
Дата: 28.07.10 17:36
Оценка: +1
Здравствуйте, ononim, Вы писали:

MZ>>Ты это кому другому бы рассказывал. Именно "новомодная" эта штука.

MZ>>Не было ни итераторов, ни вообще STL-я в С++ классическом.
MZ>>Даже шаблонов не было.
O>этой "новомодной" штучкой мы на проекте живом пользуемся уже лет 7
O>если тебе попадаются прикладные проекты на С++ без stl могу только посочувствовать.
Странно, мне сплошь и рядом попадаются исходники, в которых от STL разве что <stdio> да <string> какие-нибудь.
Re[5]: Зачем нужен итератор?
От: ononim  
Дата: 28.07.10 18:07
Оценка:
MZ>>>Не было ни итераторов, ни вообще STL-я в С++ классическом.
MZ>>>Даже шаблонов не было.
O>>этой "новомодной" штучкой мы на проекте живом пользуемся уже лет 7
O>>если тебе попадаются прикладные проекты на С++ без stl могу только посочувствовать.
ND>Странно, мне сплошь и рядом попадаются исходники, в которых от STL разве что <stdio> да <string> какие-нибудь.
Я тоже когдато работал в такой конторе. Контора была полувоенная кстати. Вспоминаю ее как плохой сон.
Кстати что касается контейнеров, то в нашем коде (multi_)set'ов и (multi_)map'ов возможно даже больше чем list'ов и vector'ов. Потому аргументы в данном треде типа вектор и лист ацтой я воще читаю с улыбкой.
Буст тоже используется, но очень в меру.
Как много веселых ребят, и все делают велосипед...
Re[10]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 28.07.10 19:44
Оценка:
Здравствуйте, ND322, Вы писали:

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

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

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


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


А вынесенный наружу хэндл перебора (будь то явный указатель, или обёрнутый итератор, или осмысленный индекс, или непрозрачный ключ) — тут, разумеется, никаких проблем нет.
С той лишь разницей, что указатели и итераторы позволяют обращаться к элементам напрямую, без контейнера (а итераторы — ещё и перемещаться), тогда как индексы и хэндлы идут строго в паре с контейнером.
Перекуём баги на фичи!
Re[6]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 28.07.10 19:51
Оценка:
Здравствуйте, ononim, Вы писали:

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


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

CArray, кстати говоря, по умолчанию эксплуатирует неопределённое поведение!!! (Перемещает элементы с помощью memmove).
Кому не нравится — пишите свой трейтс.
Перекуём баги на фичи!
Re[7]: Зачем нужен итератор?
От: ononim  
Дата: 28.07.10 20:45
Оценка:
К>Это ты ещё ATL не видел.
видел и даже пользуюсь изредка когда ченить комовское по быстрому нуна забодяжить. как то приятнее почему-то, наверно тем что легче и прозрачнее, хотя тяжелое наследие мфц гнетет
Как много веселых ребят, и все делают велосипед...
Re[10]: Зачем нужен итератор?
От: Юрий Жмеренецкий ICQ 380412032
Дата: 28.07.10 22:39
Оценка:
Здравствуйте, ND322, Вы писали:

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

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

Да. Итератор хранит текущую позицию, тогда как в 'T& operator [] (unsigned n)' для списка будет использован аналог std::advance (а это уже O(n)).
Re[10]: Зачем нужен итератор?
От: night beast СССР  
Дата: 29.07.10 06:30
Оценка:
Здравствуйте, 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;
   }
}


как это будет выглядеть без итераторов?
Мда...
От: rm822 Россия  
Дата: 29.07.10 07:50
Оценка: :)
до вот этого твоего поста, я думал что высказывающиеся здесь против STL и итераторов валяют дурака, застряли в 90х и т.п.
теперь во всяком случае понятно откуда может взяться такая точка зрения
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re: Мда...
От: night beast СССР  
Дата: 29.07.10 08:00
Оценка:
Здравствуйте, rm822, Вы писали:

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

R>теперь во всяком случае понятно откуда может взяться такая точка зрения

пример надуманный, просто было интересно, как предлагается обходить коллекции с различными алгоритмами итерирования.
Re[6]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 29.07.10 08:37
Оценка: +1 -1
ononim wrote:

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

> Более отстойной библиотеки чем MFC пожалуй не найти.

Меня тоже от CList передёргивает, но попробуй на STD напиши коллекцию-
хранилище полиморфных объектов, которое бы само удаляло объекты
при удалении их из хранилища. (shared-ptr не предлагать — +4 байта на
каждый хранимый объект не катит). А на MFC-шных -- в момент пишется.

STL не различает ситуацию удаления элемента из коллекции и ситуацию
перенесения объекта из одного буфера коллекции в другой (новый).
Потому что академичный, блин.
Posted via RSDN NNTP Server 2.1 beta
Re[7]: Зачем нужен итератор?
От: ononim  
Дата: 29.07.10 10:04
Оценка: -1
MZ>Меня тоже от CList передёргивает, но попробуй на STD напиши коллекцию-
MZ>хранилище полиморфных объектов, которое бы само удаляло объекты
MZ>при удалении их из хранилища. (shared-ptr не предлагать — +4 байта на
MZ>каждый хранимый объект не катит). А на MFC-шных -- в момент пишется.

сходу — как-то так:
template <class T> class ZuPtr
{
    mutable T *_t;
public:
    ZuPtr(T *t):_t(t) {}
    ZuPtr(const ZuPtr &z):_t(z._t) {z._t = 0;}
    ZuPtr &operator =(const ZuPtr &z){_t = z._t; z._t = 0; return *this;}
    ~ZuPtr() {delete _t;}
    T* operator ->(){return _t;}
};

struct Foo
{
    Foo(){printf("[0x%x] Foo\n", this);}
    ~Foo(){printf("[0x%x]~Foo\n", this);}
};

typedef ZuPtr<Foo> FooPtr;

typedef std::vector<FooPtr> FooV; 
typedef std::list<FooPtr> FooL;


но вообще последнний раз когда мне требовалась такая задача мне нужен был map
и памяти было жалко, потому я сделал все на boost::intrusive_ptr
Как много веселых ребят, и все делают велосипед...
Re[8]: Зачем нужен итератор?
От: night beast СССР  
Дата: 29.07.10 10:12
Оценка:
Здравствуйте, ononim, Вы писали:

O>сходу — как-то так:

O>template <class T> class ZuPtr
O>{
O>    mutable T *_t;
O>public:
O>    ZuPtr(T *t):_t(t) {}
O>    ZuPtr(const ZuPtr &z):_t(z._t) {z._t = 0;}
O>    ZuPtr &operator =(const ZuPtr &z){_t = z._t; z._t = 0; return *this;}
O>    ~ZuPtr() {delete _t;}
O>    T* operator ->(){return _t;}
O>};

O>struct Foo
O>{
O>    Foo(){printf("[0x%x] Foo\n", this);}
O>    ~Foo(){printf("[0x%x]~Foo\n", this);}
O>};

O>typedef ZuPtr<Foo> FooPtr;

O>typedef std::vector<FooPtr> FooV; 
O>typedef std::list<FooPtr> FooL;


в std алгоритмах бывает используются временные переменные, так что твое решение не катит.
формально, задачу решает наследование от std::vector<FooPtr> и нужного определение деструктора.
Re[7]: Зачем нужен итератор?
От: zitz  
Дата: 29.07.10 14:01
Оценка: :)
Здравствуйте, Юрий Жмеренецкий, Вы писали:

MZ>>Вот кстати да. Почему бы не сделать было вместо итераторов

MZ>>заклад на 3 функции :
MZ>>-- size()
MZ>>-- T& operator [] (unsigned n)
MZ>>-- const T& operator [] (unsigned n) const

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


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


Я делал себе такую штуку для множества, достаточно ввести m_nNextIndex и последовательный перебор всех значений (а у меня в основном такой) будет иметь обычную сложность.
Эх, люблю я цикл for( int i=0; i<set.GetCount(); i++) set[i];
UINT CXXXUIntSet::operator []( int nIndex )
{
    ASSERT( nIndex < GetSize() );
    std::set<UINT>* pSet1 = (std::set<UINT>*)m_pData;

    UINT retData = 0;

    if ( m_nNextIndex < 0 )
    {
        *(std::set<UINT>::iterator*)m_pNextPosition = pSet1->begin();
        m_nNextIndex = 0;
    }

    if ( nIndex == m_nNextIndex )
    {
        retData = **(std::set<UINT>::iterator*)m_pNextPosition;
        (*(std::set<UINT>::iterator*)m_pNextPosition)++;
        *(std::set<UINT>::iterator*)m_pNextPosition != pSet1->end() ? m_nNextIndex++ : m_nNextIndex = -1;
    }
    else
    {
        *(std::set<UINT>::iterator*)m_pNextPosition = pSet1->begin();
        m_nNextIndex = 0;
        while ( nIndex >= m_nNextIndex )
        {
            retData = **(std::set<UINT>::iterator*)m_pNextPosition;
            (*(std::set<UINT>::iterator*)m_pNextPosition)++;
            m_nNextIndex++;
        }
    }

    return retData;
}
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[9]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 29.07.10 14:53
Оценка:
night beast wrote:

> O> ZuPtr(T *t):_t(t) {}

> O> ZuPtr(const ZuPtr &z):_t(z._t) {z._t = 0;}
> O> ZuPtr &operator =(const ZuPtr &z){_t = z._t; z._t = 0; return *this;}
> O> ~ZuPtr() {delete _t;}
> O> T* operator ->(){return _t;}

> в std алгоритмах бывает используются временные переменные, так что твое

> решение не катит.

А чем они мешают ... что-то не соображу.
Но могу сказать точно: первое расширение содержимого vesctor-а
вызовит деструкторы в старом "хранилище" и указатели в новом хранилище
уже будут невалидные -- все объекты будут удалены.

> формально, задачу решает наследование от std::vector<FooPtr> и нужного

> определение деструктора.

Этого, блин, МАЛО. Нужно ещё заставить различаться ситуацию удаления
элементов НАСОВСЕМ от переноса их в новое хранилище.
Я ничего кроме написания собственного аллокатора с состоянием не
придумал. Решение непереносимо и ужасно.
Posted via RSDN NNTP Server 2.1 beta
Re[7]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 29.07.10 17:23
Оценка:
Здравствуйте, MasterZiv, Вы писали:

MZ>Меня тоже от CList передёргивает, но попробуй на STD напиши коллекцию-

MZ>хранилище полиморфных объектов, которое бы само удаляло объекты
MZ>при удалении их из хранилища. (shared-ptr не предлагать — +4 байта на
MZ>каждый хранимый объект не катит). А на MFC-шных -- в момент пишется.

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

MZ>STL не различает ситуацию удаления элемента из коллекции и ситуацию

MZ>перенесения объекта из одного буфера коллекции в другой (новый).
MZ>Потому что академичный, блин.

Скорее, потому что в стандарте 98 нет move constructor.
А MFC-шные фокусы с memmove — имеют ограниченную применимость.

Но, если очень хочется, можно сделать руками.
vector<T> u, v;
....
// переносим задний элемент из u в v

// копированием (дорого)
v.push_back(u.back());
u.pop_back();

// обменом
v.push_back(T());
swap(u.back(), v.back();
u.pop_back();
Перекуём баги на фичи!
Re[8]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 29.07.10 17:47
Оценка:
Кодт wrote:

> Скорее, потому что в стандарте 98 нет move constructor.


Так почему было либо не добавить его туда
либо не использовать просто функцию ?

> А MFC-шные фокусы с memmove — имеют ограниченную применимость.


Ни разу ещё на это не напарывался.
Впрочем, я в своём коде давно отказался от использования MFC-шных
коллекций.

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


Я не про это. Я про перенос ЭЛЕМЕНТОВ коллекций из одного
хранилища в другое. При переносе вызываются конструктор
в новом месте (копирования) и деструктор в старом месте.
В случае удаления -- просто деструктор. Ну и как
определить, что элемент из коллекции удаляют насовсем ?
Posted via RSDN NNTP Server 2.1 beta
Re[8]: Зачем нужен итератор?
От: Centaur Россия  
Дата: 29.07.10 18:09
Оценка: +1
Поздравляю, ononim, Вы изобрели std::auto_ptr<T>:

O>    ZuPtr(const ZuPtr &z):_t(z._t) {z._t = 0;}
O>    ZuPtr &operator =(const ZuPtr &z){_t = z._t; z._t = 0; return *this;}


Только без защиты от использования с стандартными контейнерами, которые требуют от элементов, чтобы они были CopyConstructible и CopyAssignable, с обязательной эквивалентностью копий.
Re[9]: Зачем нужен итератор?
От: ononim  
Дата: 29.07.10 18:20
Оценка:
C>Поздравляю, ononim, Вы изобрели std::auto_ptr<T>:
я знаю
Как много веселых ребят, и все делают велосипед...
Re[9]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 29.07.10 18:44
Оценка: 3 (1)
Здравствуйте, MasterZiv, Вы писали:

>> Скорее, потому что в стандарте 98 нет move constructor.


MZ>Так почему было либо не добавить его туда либо не использовать просто функцию ?


Добавить КУДА? в интерфейс произвольного объекта (рядом с ctor, cctor, dtor) или в интерфейс контейнера?

>> А MFC-шные фокусы с memmove — имеют ограниченную применимость.


MZ>Ни разу ещё на это не напарывался.

MZ>Впрочем, я в своём коде давно отказался от использования MFC-шных коллекций.

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


MZ>Я не про это. Я про перенос ЭЛЕМЕНТОВ коллекций из одного хранилища в другое.

MZ>При переносе вызываются конструктор в новом месте (копирования) и деструктор в старом месте.
MZ>В случае удаления -- просто деструктор.
MZ>Ну и как определить, что элемент из коллекции удаляют насовсем ?

А его в обоих случаях удаляют насовсем.
Просто, вместо глубокого копирования и глубокого разрушения можно применить трюк с созданием пустого объекта и обменом содержимым.
Для POD-типов и некоторых других вместо обмена можно применить memmove, что, собственно, CArray и делает.

Или ты имеешь в виду именно списки?
Так у std::list есть функция splice, как раз для того, чтобы переносить цепочку узлов из одного контейнера в другой, без конструирования-разрушения.
Перекуём баги на фичи!
Re[10]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 29.07.10 20:09
Оценка:
Кодт wrote:

> Добавить КУДА? в интерфейс произвольного объекта (рядом с ctor, cctor,

> dtor) или в интерфейс контейнера?

Да в стандарт. STL добавили, а

> А его в обоих случаях удаляют насовсем.


Здрасте, приехали.

> Просто, вместо глубокого копирования и глубокого разрушения можно

> применить трюк с созданием пустого объекта и обменом содержимым.
> Для POD-типов и некоторых других вместо обмена можно применить memmove,
> что, собственно, CArray и делает.
>
> Или ты имеешь в виду именно списки?
> Так у std::list есть функция splice, как раз для того, чтобы переносить
> цепочку узлов из одного контейнера в другой, без конструирования-разрушения.

Нет, именно вектора.

Я не понимаю, как можно не понимать глубокой разницы между ПЕРЕМЕЩЕНИЕМ
элемента коллекции из одного хранилища в другое (что вообще-то внутреннее
дело коллекции и нас вообще касаться не должно) и УДАЛЕНИЕМ элемента или
добавлением элемента в коллекцию. Разные же вещи. В STL -- одно и то же.
В MFC-шных коллекциях различается чётко и ясно.
Posted via RSDN NNTP Server 2.1 beta
Re[10]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 29.07.10 20:11
Оценка:
ononim wrote:

> C>Поздравляю, ononim, Вы изобрели std::auto_ptr<T>:

> я знаю

Интересно, а что std::auto_ptr<T> в стандартных контейнерах
хранить нельзя, не знал ?
Posted via RSDN NNTP Server 2.1 beta
Re[11]: Зачем нужен итератор?
От: ononim  
Дата: 29.07.10 20:56
Оценка:
>> C>Поздравляю, ononim, Вы изобрели std::auto_ptr<T>:
>> я знаю
MZ>Интересно, а что std::auto_ptr<T> в стандартных контейнерах
MZ>хранить нельзя, не знал ?
знал
но в некоторых реализациях STL можно
но так делать нельзя, я знаю
Как много веселых ребят, и все делают велосипед...
Re[11]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 29.07.10 21:17
Оценка:
Здравствуйте, MasterZiv, Вы писали:

>> Добавить КУДА? в интерфейс произвольного объекта (рядом с ctor, cctor,

>> dtor) или в интерфейс контейнера?

MZ>Да в стандарт. STL добавили, а


Ещё раз, куда в стандарт. Добавить move constructor, или метод vector::move_element_to_another_vector ?

>> А его в обоих случаях удаляют насовсем.


MZ>Здрасте, приехали.


И снова здравствуйте!
Объект располагается где-то в памяти. Когда мы освобождаем эту память (возвращаем её в кучу, либо оставляем пустой для грядущих добавлений), куда девается объект? Уничтожается.

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

А вот уничтожение, сопряжённое с копированием, можно реализовывать по-разному.
Либо через конструктор копирования и деструктор, либо через дефолтный конструктор, обмен и деструктор.
Деструктор будет в любом случае.

>> Или ты имеешь в виду именно списки?


MZ>Нет, именно вектора.


MZ>Я не понимаю, как можно не понимать глубокой разницы между ПЕРЕМЕЩЕНИЕМ

MZ>элемента коллекции из одного хранилища в другое (что вообще-то внутреннее
MZ>дело коллекции и нас вообще касаться не должно) и УДАЛЕНИЕМ элемента или
MZ>добавлением элемента в коллекцию. Разные же вещи. В STL -- одно и то же.
MZ>В MFC-шных коллекциях различается чётко и ясно.

Ну хорошо, в MFC/ATL есть у контейнеров метод RelocateElements.
И часто ты им пользуешься?

Вообще-то, он предназначен для внутренних нужд — через него реализованы функции вставки и удаления.
Переопределяя его (а лучше — не его, а трейтс-параметр шаблона CArray) ты можешь добиваться наилучшей и наиправильной работы этих функций. (Ибо, по дефолту там UB на memmove).

В STL перемещение элементов вектора спрятано внутрь и прибито гвоздями. Как именно — забота версии STL.

У Dinkumware (в поставке для VC) — там присваивания. Можно сделать через swap. Можно через копирования.
Для некоторых типов данных эффективнее swap, для других присваивание, для третьих копирование. (Ибо, по дефолту swap делается через копирование и два присваивания).


Вообще, идеология STL такова, что обычные контейнеры необязательно эффективны, но зато универсальны.
Когда возникает желание побороться за производительность, — пиши свой контейнер. Хочешь — делай его STL-like, не хочешь — не делай.
Присобачить STL-like интерфейс к CArray — раз плюнуть.
А с помощью буста можно и трейтсы с правильной реализацией RelocateElements на все случаи жизни (ну, хотя бы проверяя тип на POD и на известное семейство memmove-безопасных).
Перекуём баги на фичи!
Re[8]: Зачем нужен итератор?
От: Юрий Жмеренецкий ICQ 380412032
Дата: 29.07.10 23:23
Оценка:
Здравствуйте, zitz, Вы писали:

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


Z>Я делал себе такую штуку для множества, достаточно ввести m_nNextIndex и последовательный перебор всех значений (а у меня в основном такой) будет иметь обычную сложность.

Z>Эх, люблю я цикл for( int i=0; i<set.GetCount(); i++) set[i];

  Скрытый текст
Z>
Z>UINT CXXXUIntSet::operator []( int nIndex )
Z>{
Z>    ASSERT( nIndex < GetSize() );
Z>    std::set<UINT>* pSet1 = (std::set<UINT>*)m_pData;

Z>    UINT retData = 0;

Z>    if ( m_nNextIndex < 0 )
Z>    {
Z>        *(std::set<UINT>::iterator*)m_pNextPosition = pSet1->begin();
Z>        m_nNextIndex = 0;
Z>    }

Z>    if ( nIndex == m_nNextIndex )
Z>    {
Z>        retData = **(std::set<UINT>::iterator*)m_pNextPosition;
Z>        (*(std::set<UINT>::iterator*)m_pNextPosition)++;
Z>        *(std::set<UINT>::iterator*)m_pNextPosition != pSet1->end() ? m_nNextIndex++ : m_nNextIndex = -1;
Z>    }
Z>    else
Z>    {
Z>        *(std::set<UINT>::iterator*)m_pNextPosition = pSet1->begin();
Z>        m_nNextIndex = 0;
Z>        while ( nIndex >= m_nNextIndex )
Z>        {
Z>            retData = **(std::set<UINT>::iterator*)m_pNextPosition;
Z>            (*(std::set<UINT>::iterator*)m_pNextPosition)++;
Z>            m_nNextIndex++;
Z>        }
Z>    }

Z>    return retData;
Z>}
Z>

В таком решении присутствует нарушение SRP — на контейнер возложено больше обязанностей, чем необходимо, соответственно на ровном месте возникает усложнение контракта контейнера и его реализации. Как следствие — потеря реентерабельности (см. сообщение Кодт'а). Кстати, перечисление в обратном порядке выполняется за O(n^2).
Re[10]: Зачем нужен итератор?
От: night beast СССР  
Дата: 30.07.10 04:28
Оценка:
Здравствуйте, MasterZiv, Вы писали:

MZ>night beast wrote:


>> O> ZuPtr(T *t):_t(t) {}

>> O> ZuPtr(const ZuPtr &z):_t(z._t) {z._t = 0;}
>> O> ZuPtr &operator =(const ZuPtr &z){_t = z._t; z._t = 0; return *this;}
>> O> ~ZuPtr() {delete _t;}
>> O> T* operator ->(){return _t;}

>> в std алгоритмах бывает используются временные переменные, так что твое

>> решение не катит.

MZ>А чем они мешают ... что-то не соображу.


по той-же причине, почему не рекомендуют хранить auto_ptr в стандартных контейнерах:
vector<FooPtr> v;
v.push_back( new Foo () );
{
   FooPtr tmp = v[0]; // захватываем память
} // здесь мы освобождаем память 
v[0]; // здесь имеем v[0] == 0;


MZ>Но могу сказать точно: первое расширение содержимого vesctor-а

MZ>вызовит деструкторы в старом "хранилище" и указатели в новом хранилище
MZ>уже будут невалидные -- все объекты будут удалены.

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

>> формально, задачу решает наследование от std::vector<FooPtr> и нужного

>> определение деструктора.

MZ>Этого, блин, МАЛО. Нужно ещё заставить различаться ситуацию удаления

MZ>элементов НАСОВСЕМ от переноса их в новое хранилище.
MZ>Я ничего кроме написания собственного аллокатора с состоянием не
MZ>придумал. Решение непереносимо и ужасно.

деструктор это и есть удаление элементов насовсем.
можно более конкретно описать задачу?
Re[11]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 30.07.10 09:02
Оценка:
night beast wrote:

> или я не понял задачу, или одно из двух;

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

Ты уверен ?

> деструктор это и есть удаление элементов насовсем.

> можно более конкретно описать задачу?

Да я уже описал. Хранить в коллекции (ну давай для конкретики вектор)
полиморфные объекты, унаследованные от класса, скажем, CMyFavoriteObject,
по ссылке, без дополнительных накладных расходов по памяти и так,
чтобы коллекция была бы ответственна за удаление этих объектов
(т.е. клиент удалил из коллекции элемент -- он удалился вообще,
т.е. delete).
Posted via RSDN NNTP Server 2.1 beta
Re[12]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 30.07.10 09:33
Оценка: +1 -1
Кодт wrote:

> Объект располагается где-то в памяти. Когда мы освобождаем эту память

> (возвращаем её в кучу, либо оставляем пустой для грядущих добавлений),
> куда девается объект? Уничтожается.

Ты по-моему совсем меня не понимаешь. Я совсем о другом.

> Ну хорошо, в MFC/ATL есть у контейнеров метод RelocateElements.

> И часто ты им пользуешься?

Вообще не использую. Но там есть замечательный
глобальный метод типа

void AFXAPI DestructElements( MyClass **pElements, int nCount );

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

> Вообще, идеология STL такова, что обычные контейнеры необязательно

> эффективны, но зато универсальны.
> Когда возникает желание побороться за производительность, — пиши свой
> контейнер. Хочешь — делай его STL-like, не хочешь — не делай.

Дело не в производительности, а именно в универсальности. Перемещение
элемента в другое хранилище -- отдельная операция, она НЕ СВЯЗАНА
с удалением объекта вообще никак. Так вот именно она должна
была специфицирована в стандарте и как-то реализована. Но ребята
решили притвориться академиками и не париться. Конструктор-деструктор.
Типа другого пути нет.
Posted via RSDN NNTP Server 2.1 beta
Re[12]: Зачем нужен итератор?
От: night beast СССР  
Дата: 30.07.10 09:40
Оценка:
Здравствуйте, MasterZiv, Вы писали:

>> или я не понял задачу, или одно из двух;

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

MZ>Ты уверен ?


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

>> деструктор это и есть удаление элементов насовсем.

>> можно более конкретно описать задачу?

MZ>Да я уже описал. Хранить в коллекции (ну давай для конкретики вектор)

MZ>полиморфные объекты, унаследованные от класса, скажем, CMyFavoriteObject,
MZ>по ссылке, без дополнительных накладных расходов по памяти и так,
MZ>чтобы коллекция была бы ответственна за удаление этих объектов
MZ>(т.е. клиент удалил из коллекции элемент -- он удалился вообще,
MZ>т.е. delete).

boost::ptr_vector (уже было озвучено) не подходит?
Re[13]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 30.07.10 09:54
Оценка:
Здравствуйте, MasterZiv, Вы писали:

MZ>Дело не в производительности, а именно в универсальности. Перемещение

MZ>элемента в другое хранилище -- отдельная операция, она НЕ СВЯЗАНА
MZ>с удалением объекта вообще никак. Так вот именно она должна
MZ>была специфицирована в стандарте и как-то реализована. Но ребята
MZ>решили притвориться академиками и не париться. Конструктор-деструктор.
MZ>Типа другого пути нет.

Ты, видимо, упорно путаешь CArray и его производные — CPtrArray, CObArray.
Их элементы — указатели. Понимаешь, указатели, а не указуемые значения.

Если тебе хочется, чтобы контейнер выполнял глубокое копирование и глубокое удаление (указателей вместе с указуемыми) — пожалуйста, boost::ptr_vector.
Или vector<shared_ptr>, если не хочешь иметь разные траблы с монопольным владением.
Перекуём баги на фичи!
Re[13]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 30.07.10 12:10
Оценка:
night beast wrote:

> MZ>Ты уверен ?

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

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

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


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

Ну ладно, пора кончать уже с этим топиком.
Posted via RSDN NNTP Server 2.1 beta
Re[14]: Зачем нужен итератор?
От: night beast СССР  
Дата: 30.07.10 12:26
Оценка:
Здравствуйте, MasterZiv, Вы писали:

>> был уверен. посмотрел -- облом

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

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

MZ>Думал -- усё, сбрендил.



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


MZ>Это не STL. Я могу и сам написать ( и сделал так ).

MZ>Вопрос не в этом, а в том, что это должно быть в стандартной
MZ>библиотеке.

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

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


ок.
Re[8]: Зачем нужен итератор?
От: MasterZiv СССР  
Дата: 30.07.10 12:28
Оценка:
Кодт wrote:

> <a

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

Ну кстати в Motivation там вся "моя" проблема и расписана.
Posted via RSDN NNTP Server 2.1 beta
Re[10]: Зачем нужен итератор?
От: minorlogic Украина  
Дата: 30.07.10 13:38
Оценка:
Здравствуйте, ND322, Вы писали:

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

Много простых алгоритмов и не очень , например std::sort
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[10]: Зачем нужен итератор?
От: minorlogic Украина  
Дата: 30.07.10 13:41
Оценка:
Здравствуйте, MasterZiv, Вы писали:

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


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

>> использованием предложенного интерфейса за линейное время?

MZ>Я не предлагаю ТОТ ЖЕ алгоритм перебора писать, и С ТЕМИ ЖЕ

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

Тогда это ухудшение , потому что теряется универсальность. ПОпробуйте рассуждать в терминах , преимущества недостатки различных подходов. вместо "мне обычно хватает доступа по индекусу".
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[10]: Зачем нужен итератор?
От: morm Россия  
Дата: 31.07.10 11:25
Оценка:
Здравствуйте, Кодт, Вы писали:

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


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

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

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


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


К>Однако, помимо невалидных, есть ещё и сигнальные значения.

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

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

Согласен и ,тем не менее, при изменении end() контейнера ВСЕ range, допустим, полученые через MType::range = m.find(v); — тю-тю...
Мне что-то больше нравится с итератором вариант.
Re[11]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 31.07.10 11:55
Оценка:
Здравствуйте, morm, Вы писали:

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

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

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

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

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

А вот для вектора — уменьшение размера инвалидирует все хвостовые итераторы, включая end(). Тут будет всё плохо.
Перекуём баги на фичи!
Re: Зачем нужен итератор?
От: rm822 Россия  
Дата: 31.07.10 13:54
Оценка: 3 (1)
Здравствуйте, 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>>
Re[2]: Зачем нужен итератор?
От: alexeiz  
Дата: 31.07.10 19:24
Оценка:
Здравствуйте, McSeem2, Вы писали:

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


Что ты предлагаешь на замену итераторам?
Re[3]: Слишком толсто
От: alexeiz  
Дата: 31.07.10 20:42
Оценка:
Здравствуйте, 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*/});
Re[6]: Зачем нужен итератор?
От: alexeiz  
Дата: 31.07.10 20:47
Оценка: 5 (1)
Здравствуйте, 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

Тот же заклад на три функции.
Re[8]: Зачем нужен итератор?
От: Roman Odaisky Украина  
Дата: 01.08.10 11:53
Оценка:
Здравствуйте, ND322, Вы писали:

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


200 строк будут работать быстрее. http://rsdn.ru/forum/cpp/2944787.1.aspx
Автор: Roman Odaisky
Дата: 09.05.08


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


В <algorithm> много чего есть. Хотя бы std::sort.
До последнего не верил в пирамиду Лебедева.
а что с output итераторами?
От: rm822 Россия  
Дата: 01.08.10 14:14
Оценка:
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>>
Re[9]: Зачем нужен итератор?
От: zitz  
Дата: 02.08.10 06:33
Оценка: -1 :)
Здравствуйте, Юрий Жмеренецкий, Вы писали:

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


Это мой контейнер, я возложил на него столько обязанностей сколько мне необходимо, это раз
На сколько сложна реализация контейнера лично мне не принципиально, лишь бы он выполнял возложенные на него обязанности, это два
Мне не нужно перечисление в обратном порядке, а если станет нужно и если данная функция будет сильно тормозить весь код, то я без проблем допишу, ведь так? Это три
Я это к чему всё? Не к тому что я придумал универсальный контейнер который покроет все нужны (этот класс не публичный и только для моих целей используется), а к тому что, приложив немного серого вещества можно опровергнуть теорему Юрия Жмеренецкого:
ЮЖ>В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет линейной, поэтому сложность перебора всех элементов с помощью этого интерфейса будет квадратичной.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[10]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 02.08.10 10:20
Оценка: 2 (1)
Здравствуйте, zitz, Вы писали:

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


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


Как говорится, wish you happy debug.
Я встречал ситуации, когда кривой дизайн аукался спустя год успешного использования.
И один из таких случаев был, как раз, — склеивание коллекции с итератором.
Там была такая история: некий ком-объект, содержащий список. И выбор — либо реализовывать ещё один ком-класс с итератором, либо сделать по-быстрому, расширить интерфейс коллекции.
Перекуём баги на фичи!
Re[11]: Зачем нужен итератор?
От: zitz  
Дата: 02.08.10 11:14
Оценка:
Здравствуйте, Кодт, Вы писали:

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>>
Re[12]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 02.08.10 11:51
Оценка:
Здравствуйте, 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).
А для однопоточного применения — создание копий сильно избыточно.

Эрго, арбитражем таких взаимодействий должен заниматься тот, кто в арбитраже компетентен. То есть, владелец обоих контейнеров.
Перекуём баги на фичи!
Re[13]: Зачем нужен итератор?
От: zitz  
Дата: 02.08.10 12:35
Оценка:
Здравствуйте, Кодт, Вы писали:

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]: Зачем нужен итератор?
Автор: zitz
Дата: 29.07.10


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


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


Да я не про контейнеры, я вообще в целом. Вот последний пример happy debug — это падение из-за WM_PAINT когда при отрисовке идет обращение к данным которые были уничтожены вторым потоком (причем уничтожены не явно, вызовом какого-нить внешне безобидного метода), тут бывает вообще трудно уловить из-за чего падает и даже где падает. В общем страсти-мордасти
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re: Зачем нужен итератор?
От: Erop Россия  
Дата: 02.08.10 12:44
Оценка: +1
Здравствуйте, ND322, Вы писали:

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

ND>Заранее спасибо!

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

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

Подход с итераторами позволяет хранить просто массив пар {атрибут, сколько повторов}. Написать итератор по буквам поверх итератора такой структуры -- просто. Написать итератор по группам -- вообще ничего писать не надо. Всё просто, быстро, удобно
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[7]: Зачем нужен итератор?
От: Erop Россия  
Дата: 02.08.10 12:52
Оценка:
Здравствуйте, ND322, Вы писали:


ND>Вопрос простой — любая нормальная библиотека, где есть контейнеры, будет иметь для них базовый класс (вероятнее всего, абстрактный).


есть просто куча нормальных библ, ни разу ни ООП при этом
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[3]: Зачем нужен итератор?
От: Erop Россия  
Дата: 02.08.10 12:56
Оценка:
Здравствуйте, Igore, Вы писали:

I>Ну, бывает и хуже, пишешь новый класс, и понимаешь что у тебя есть какое то множество, объявляешь его std::set<myenum>, написал половину класса и понимаешь что для одного из методов тебе важен порядок в какой было все считано, и меняешь set на vector, часть написанного кода остается а добавление меняется, вот это кстати минус, есть универсальный способ доступа к контейнерам, есть удаление, а вот одного и того же insert нету


Это действительно бывает и действительно намного хуже. Чтобы так не было программы стоит проектировать, однако
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[6]: Зачем нужен итератор?
От: Erop Россия  
Дата: 02.08.10 13:01
Оценка:
Здравствуйте, ononim, Вы писали:

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


Не-не-не! Пределов совершенству нет!!!
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[11]: Зачем нужен итератор?
От: Erop Россия  
Дата: 02.08.10 13:20
Оценка: +1
Здравствуйте, minorlogic, Вы писали:

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


Ну так давно же известно, что универсальные решения в каждом конкретном случае хуже, зато они универсальные...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[11]: Зачем нужен итератор?
От: Erop Россия  
Дата: 02.08.10 13:30
Оценка:
Здравствуйте, morm, Вы писали:


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

M>Мне что-то больше нравится с итератором вариант.

Что-то тут не так. Если тухнет end, то тухнут и все остальные итераторы вроде как...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[12]: Зачем нужен итератор?
От: minorlogic Украина  
Дата: 02.08.10 13:39
Оценка: :)
Здравствуйте, Erop, Вы писали:

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


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


E>Ну так давно же известно, что универсальные решения в каждом конкретном случае хуже, зато они универсальные...


Восхитительный техничекий аргумент. Особенно перфоманс бенчмарки.
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[13]: Зачем нужен итератор?
От: Erop Россия  
Дата: 02.08.10 13:45
Оценка:
Здравствуйте, minorlogic, Вы писали:

E>>Ну так давно же известно, что универсальные решения в каждом конкретном случае хуже, зато они универсальные...

M>Восхитительный техничекий аргумент. Особенно перфоманс бенчмарки.
Ты оспариваешь тезис, что универсальность обычно небесплатна?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[14]: Зачем нужен итератор?
От: minorlogic Украина  
Дата: 02.08.10 14:05
Оценка:
Здравствуйте, Erop, Вы писали:

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


E>>>Ну так давно же известно, что универсальные решения в каждом конкретном случае хуже, зато они универсальные...

M>>Восхитительный техничекий аргумент. Особенно перфоманс бенчмарки.
E>Ты оспариваешь тезис, что универсальность обычно небесплатна?

Нет , я по теме, я про итераторы.
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[12]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 02.08.10 16:18
Оценка:
Здравствуйте, Erop, Вы писали:

E>Что-то тут не так. Если тухнет end, то тухнут и все остальные итераторы вроде как...

vector<int> v(10);
vector<int>::iterator first = v.begin(), middle = begin+v.size()/2, end = v.end(), last = end-1;
v.pop_back();

begin и middle валидны, end протух, last... как минимум, стал нечитаемым (v.end()==last), формально — протух.
Перекуём баги на фичи!
Re[13]: Зачем нужен итератор?
От: Erop Россия  
Дата: 02.08.10 16:23
Оценка:
Здравствуйте, Кодт, Вы писали:

К>begin и middle валидны, end протух, last... как минимум, стал нечитаемым (v.end()==last), формально — протух.

Гарантии нет. Вдруг был всего один элемент в векторе?
Кроме того, я не помню, есть ли гарантии для вектора в котором, скажем, 10 элементов.
Если помнишь, процитируй, что ли, как они формулируются. Чисто для полноты картины.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[14]: Зачем нужен итератор?
От: Кодт Россия  
Дата: 02.08.10 19:13
Оценка: 10 (1)
Здравствуйте, Erop, Вы писали:

К>>begin и middle валидны, end протух, last... как минимум, стал нечитаемым (v.end()==last), формально — протух.

E>Гарантии нет. Вдруг был всего один элемент в векторе?
E>Кроме того, я не помню, есть ли гарантии для вектора в котором, скажем, 10 элементов.
E>Если помнишь, процитируй, что ли, как они формулируются. Чисто для полноты картины.

23.2.4.2 vector capacity [lib.vector.capacity]
5 Notes: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the
sequence. It is guaranteed that no reallocation takes place during insertions that happen after a call to
reserve() until the time when an insertion would make the size of the vector greater than the size
specified in the most recent call to reserve().

23.2.4.3 vector modifiers [lib.vector.modifiers]
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
3 Effects: Invalidates all the iterators and references after the point of the erase.

То есть, стандарт умалчивает, происходит ли переразмещение при удалениях.
Но можно предположить, что — нет, не происходит. Иначе бы последняя фраза звучала так: заведомо инвалидирует хвост, но и в голове тоже поберегись!
Перекуём баги на фичи!
Re[9]: Зачем нужен итератор?
От: Vain Россия google.ru
Дата: 03.08.10 01:17
Оценка:
Здравствуйте, ononim, Вы писали:

V>>>>Так и итераторов будет два, если функцию find обернуть — придётся всегда пару итераторов возвращать, тогда как range уже какбе пара итераторов.

M>>>чего й то???
V>>А как ты итератор на валидность проверишь?
O>Проверять в программе надо только входные данные, ибо они не под вашим контролем. Итератор должен _быть_ валиден, ибо код который вы пишете под вашим контролем. Или нет?
Не обязательно, если итератор будет потом использоваться, то его надо проверить на валидность посредством сравнения с концом.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[11]: Зачем нужен итератор?
От: Vain Россия google.ru
Дата: 03.08.10 01:19
Оценка:
Здравствуйте, morm, Вы писали:

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

M>>>Тупанул, да А как быть если возвращаешь, допустим, range, потом erase исходного контейнера. Что делать с end'ом в range??
К>>Неподходящее слово "валидность", перегруженное смыслами.
К>>Итераторы, — равно как и ссылки, указатели, диапазоны и прочие косвенности, — инвалидируются при некоторых изменениях контейнера.
К>>Однако, помимо невалидных, есть ещё и сигнальные значения.
К>>У указателей есть одно универсальное сигнальное значение — NULL, а также в роли сигнальных могут выступать указатели за конец массива (end()).
К>>Разыменовывать сигнальный указатель или итератор нельзя. Но если это end, то можно применять к нему адресную арифметику.
К>>В нашем случае, надо проверять не на валидность, а на сигнальность.
M>Согласен и ,тем не менее, при изменении end() контейнера ВСЕ range, допустим, полученые через MType::range = m.find(v); — тю-тю...
M>Мне что-то больше нравится с итератором вариант.
Это зависит в общем случае от контейнера, массив — возможно, лист — не обязательно.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[10]: Зачем нужен итератор?
От: rg45 СССР  
Дата: 03.08.10 07:21
Оценка: +1
Здравствуйте, Vain, Вы писали:

V>Не обязательно, если итератор будет потом использоваться, то его надо проверить на валидность посредством сравнения с концом.


Вообще-то, валидность/невалидность итератора никак не связана с равенством/неравенством концу контейнера. Итератор, полученный с помощью end(), изначально валиден, и может стать невалидным впоследствии, в результате переаллокации, например. Невалидность итератора означает, что над ним нельзя выполнять никакие операции, в т.ч. сравнения, в т.ч. с концом. И проверить валидность итератора в общем случае нельзя, программа должна отслеживать валидность итераторов исходя из собственной логики.
--
Не можешь достичь желаемого — пожелай достигнутого.
Re[11]: Зачем нужен итератор?
От: Vain Россия google.ru
Дата: 03.08.10 08:50
Оценка:
Здравствуйте, rg45, Вы писали:

V>>Не обязательно, если итератор будет потом использоваться, то его надо проверить на валидность посредством сравнения с концом.

R>Вообще-то, валидность/невалидность итератора никак не связана с равенством/неравенством концу контейнера. Итератор, полученный с помощью end(), изначально валиден, и может стать невалидным впоследствии, в результате переаллокации, например. Невалидность итератора означает, что над ним нельзя выполнять никакие операции, в т.ч. сравнения, в т.ч. с концом. И проверить валидность итератора в общем случае нельзя, программа должна отслеживать валидность итераторов исходя из собственной логики.
Ну если радеть за чистоту понятий то да
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[11]: Зачем нужен итератор?
От: Vain Россия google.ru
Дата: 03.08.10 08:53
Оценка:
Здравствуйте, rg45, Вы писали:

V>>Не обязательно, если итератор будет потом использоваться, то его надо проверить на валидность посредством сравнения с концом.

R>Вообще-то, валидность/невалидность итератора никак не связана с равенством/неравенством концу контейнера. Итератор, полученный с помощью end(), изначально валиден, и может стать невалидным впоследствии, в результате переаллокации, например. Невалидность итератора означает, что над ним нельзя выполнять никакие операции, в т.ч. сравнения, в т.ч. с концом. И проверить валидность итератора в общем случае нельзя, программа должна отслеживать валидность итераторов исходя из собственной логики.
Я имел ввиду под валидностью — валидность на разименовывание.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[10]: Зачем нужен итератор?
От: K13 http://akvis.com
Дата: 04.08.10 12:51
Оценка:
J>>Насчет практических случаев — да, использовал многажды, никаких нареканий к эффективности, ибо CRTP.
ND>Да, знаком, хотя сам таких финтов ни разу не писал. Действительно, оверхед будет нулевой. Виртуельные методы без VMT А в каких случаях использовали, Если не секрет? Только в Boost или использовали вообще как общий подход в работе с контейнерами?

вообще-то классы итераторов не обязаны иметь общего предка. поэтому vmt — не из этой оперы.

что касается CRTP — штука мощная и полезная.

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

Да, разбухает код — вместо вызова call_func() с указателем на функцию у нас для каждого варианта обработки получается отдельный скомпилированный цикл. Но при расчетах, занимающих минуты, а не секунды -- окупается. мегапикселей много, отдельные извращенцы запускают на гигапикселе.
где они только берут такие изображения?
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.