Умные книжки много пишут о прелестях итераторов для различных контейнеров данных. Обычно приводятся примеры самостоятельных шаблонных классов, осуществляющих перебор элементов собственно контейнерного класса. Вот снова попалось в литературе, решил спросить мнение гуру. Где и как на практике используется эта крутизна? В чем преимущество перед обыкновенным CList\TList, который перебирает сои элементы сам без всяких сложных конструкций. Лично мне на практике всегда хватало его возможностей. Чего я не понимаю в этой жизни? Где используются эти пресловутые классы-итераторы?
Заранее спасибо!
31.07.10 12:14: Перенесено модератором из 'C/C++. Прикладные вопросы' — Кодт
ND>Заранее спасибо!
Основная польза — итераторы позволяют строить алогритмы, независимые от контейнера. Передаешь в алогоритм пару итераторов — и алогритм выполняет с итераторами, а не с контейнером, таким образом, становится контейнеро-независимым.
Здравствуйте, ND322, Вы писали:
ND>Умные книжки много пишут о прелестях итераторов для различных контейнеров данных. Обычно приводятся примеры самостоятельных шаблонных классов, осуществляющих перебор элементов собственно контейнерного класса. Вот снова попалось в литературе, решил спросить мнение гуру. Где и как на практике используется эта крутизна? В чем преимущество перед обыкновенным CList\TList, который перебирает сои элементы сам без всяких сложных конструкций. Лично мне на практике всегда хватало его возможностей. Чего я не понимаю в этой жизни? Где используются эти пресловутые классы-итераторы? ND>Заранее спасибо!
Вы отстали от жизни, согласно последним инновационным предложениям от классиков итератор не_нужен.
Здравствуйте, 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;
}
}
Здравствуйте, ND322, Вы писали:
ND>Умные книжки много пишут о прелестях итераторов для различных контейнеров данных. Обычно приводятся примеры самостоятельных шаблонных классов, осуществляющих перебор элементов собственно контейнерного класса. Вот снова попалось в литературе, решил спросить мнение гуру. Где и как на практике используется эта крутизна? В чем преимущество перед обыкновенным CList\TList, который перебирает сои элементы сам без всяких сложных конструкций. Лично мне на практике всегда хватало его возможностей. Чего я не понимаю в этой жизни? Где используются эти пресловутые классы-итераторы? ND>Заранее спасибо!
Итератор это абстракция позволяющая представить МНОЖЕСТВО однотипных объектов. Абстракция позволяющая работать как с указателями в памяти так и с очень сложными коллекциями(графы например).
Т.е. это унифицированный интерфейс доступа к элементам множетсва. Не больше ни меньше.
> В чем преимущество перед обыкновенным CList\TList, который перебирает сои элементы сам без всяких сложных конструкций.
Итераторы используются для итерирования произвольных контейнеров.
Итерация при помощи индексов (типа в CList) эффективно работает лишь для тех контейнеров, у которых доступ к произвольному элементу по индексу возможен за константное время. Но имеется туева хуча других типов контейнеров, где индексы ни к селу ни к городу, тот же связный список, не говоря уж о деревьях. Так вот, чтобы не вводить для каждого типа контейнера свой способ итерации и чтобы можно было использовать обобщенные алгоритмы (к примеру, поиск совпадающего элемента последовательным перебором) для различных типов контейнеров были придуманы итераторы. Сорри за небольшой каламбуризм.
И кстати никакой сложности на самом деле нету — просто немного непривычно. И вообще доступ по индексу на самом деле сложнее — ведь тут присутствует дополнительное понятия "индекс" которое может быть совершенно неинтересно с т.з. алгоритма который осуществляет доступ к контейнеру.
> Где используются эти пресловутые классы-итераторы?
Очень даже используется.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, ononim, Вы писали:
>> В чем преимущество перед обыкновенным CList\TList, который перебирает сои элементы сам без всяких сложных конструкций. O>Итераторы используются для итерирования произвольных контейнеров. O>Итерация при помощи индексов (типа в CList) эффективно работает лишь для тех контейнеров, у которых доступ к произвольному элементу по индексу возможен за константное время. Но имеется туева хуча других типов контейнеров, где индексы ни к селу ни к городу, тот же связный список, не говоря уж о деревьях. Так вот, чтобы не вводить для каждого типа контейнера свой способ итерации и чтобы можно было использовать обобщенные алгоритмы (к примеру, поиск совпадающего элемента последовательным перебором) для различных типов контейнеров были придуманы итераторы. Сорри за небольшой каламбуризм. O>И кстати никакой сложности на самом деле нету — просто немного непривычно. И вообще доступ по индексу на самом деле сложнее — ведь тут присутствует дополнительное понятия "индекс" которое может быть совершенно неинтересно с т.з. алгоритма который осуществляет доступ к контейнеру.
>> Где используются эти пресловутые классы-итераторы? O>Очень даже используется.
Я понимаю, ЧТО такое итератор, я понимаю (но не использую пока на практике), что такое графы, очереди, двусвязные списки и т.д. и .п. Я не очень понимаю, в каких конкретно областях эти самые итераторы используются на практике? Вот я и спросил, в нажедже, что опытные люди просто приведут пример из жизни. Лично я вижу единственное реальное преимущество — мы можем для одной структуры (списка, дерева, ассоциативного массива и т.д.) иметь несколько текущих позиций и перебирать объекты в этих контейнерных структурах независимо — ну, например, имеем один стек, но вершин у него несколько и живут они независимо Правда, у меня за всю практическую деятельность, ни в одной реальной программе пока такой необходимости не возникало. Если бы возникло,я бы наверное тупо ввел две переменные-указателя на соответствующие текущие значения, да и перебирал бы себе дальше — дешево-сердито
ND>Я понимаю, ЧТО такое итератор, я понимаю (но не использую пока на практике), что такое графы, очереди, двусвязные списки и т.д. и .п. Я не очень понимаю, в каких конкретно областях эти самые итераторы используются на практике? Вот я и спросил, в нажедже, что опытные люди просто приведут пример из жизни.
Да пажалста. Я системщик. Обертки-итераторы вокруг FindFirstFile/FindNextFile, перечисление процессов, модулей, потоков etc — все это есть и применяется в нашем текущем проекте.
ND>Лично я вижу единственное реальное преимущество — мы можем для одной структуры (списка, дерева, ассоциативного массива и т.д.) иметь несколько текущих позиций и перебирать объекты в этих контейнерных структурах независимо — ну, например, имеем один стек, но вершин у него несколько и живут они независимо
Итератор это обобщенное понятие, придуманное для того чтобы обобщить методы последовательного доступа к элементам различных контейнеров и ничего более.
Что во первых позволяет не за??ирать голову программиста особенностями потрохов различных контейнеров, во вторых позволяет использовать один и тот же обобщенный (читай — шаблонный) С++ код для работы с различными контейнерами. То бишь читай здесь — http://www.cppreference.com/wiki/stl/algorithm/start и обрати внимание что приведенным там алгоритмам пофиг элементы какого контейнера им скармливают.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, 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.]
[Даю очевидные ответы на риторические вопросы]
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
}
Здравствуйте, rm822, Вы писали:
V>>Вопросы новичков в STL воспринимаются уже как троллизм? однако. R>Он нам предлагает сравнить STL c MFC-обрубками, которые тоже построены на итераторах, тока называются они там POSITION.
Как минимум для итераторов дребуется отдельный класс, POSITION это не класс, т.е. у него нет методов. С этой позиции MFC проще, т.к. меньше сущностей.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, ND322, Вы писали:
ND>Умные книжки много пишут о прелестях итераторов для различных контейнеров данных. Обычно приводятся примеры самостоятельных шаблонных классов, осуществляющих перебор элементов собственно контейнерного класса. Вот снова попалось в литературе, решил спросить мнение гуру. Где и как на практике используется эта крутизна? В чем преимущество перед обыкновенным CList\TList, который перебирает сои элементы сам без всяких сложных конструкций. Лично мне на практике всегда хватало его возможностей. Чего я не понимаю в этой жизни? Где используются эти пресловутые классы-итераторы?
Итераторы, это результат попытки унифицировать доступ к элементу, а также унифицировать способ обхода (итерации по контейнеру) контейнера. Таким образом один и тот же способ будет необходим и достаточен, чтобы обойти конейнеры любых типов. Для этого тостаточно, чтобы контейнер объявлял определённый набор методов (begin/end) и эти методы работали с промежуточным объектом — итератором. Тогда способ доступа к элементу и итерации по контейнеру всегда будет одинаковыми.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, ND322, Вы писали:
ND>Умные книжки много пишут о прелестях итераторов для различных контейнеров данных. Обычно приводятся примеры самостоятельных шаблонных классов, осуществляющих перебор элементов собственно контейнерного класса. Вот снова попалось в литературе, решил спросить мнение гуру. Где и как на практике используется эта крутизна? В чем преимущество перед обыкновенным CList\TList, который перебирает сои элементы сам без всяких сложных конструкций. Лично мне на практике всегда хватало его возможностей. Чего я не понимаю в этой жизни? Где используются эти пресловутые классы-итераторы?
Итераторы — это бездарная попытка использовать C++ не по назначению. Теоретически это прикольно, но на практике ничего кроме пожизненного рака головы не получается. Посмотрите на буст — это же просто помойка. Развитие C++ должно закончиться так же как Си и Фортрана. Любые попытки его развивать делают только хуже. В этом плане язык Си — более православный. Он стандартизирован, легок в имплементации и все хорошо. C++ — это монстр и кадавр, обеспокоенный желудочно.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, ND322, Вы писали:
ND>Умные книжки много пишут о прелестях итераторов для различных контейнеров данных. Обычно приводятся примеры самостоятельных шаблонных классов, осуществляющих перебор элементов собственно контейнерного класса. Вот снова попалось в литературе, решил спросить мнение гуру. Где и как на практике используется эта крутизна? В чем преимущество перед обыкновенным CList\TList, который перебирает сои элементы сам без всяких сложных конструкций. Лично мне на практике всегда хватало его возможностей. Чего я не понимаю в этой жизни? Где используются эти пресловутые классы-итераторы? ND>Заранее спасибо!
Определение:
Итератор — это объект, обеспечивающий последовательный доступ к элементам контейнера.
Вот и все.
В этом качестве он и нужен. Обозвать можно по-разному. ъ
Но все равно некая сущность, обеспечивающая последовательный доступ к элементам контейнера, нужна. ИМХО — это плюс.
В С++ его сделали произвольным — по аналогии с указателем.
ИМХО — это минус.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, McSeem2, Вы писали: LVV>>Итератор — это объект, обеспечивающий последовательный доступ к элементам контейнера. LVV>>Вот и все. MS>А тогда что такое "итератор произвольного доступа"? А такой есть и даже свойство такое есть. Это оксиморон.
Я таких иностранных слов не знаю...
Но В С++ многое сделано в угоду пресловутой обратной совместимости с С — это самая большая ошибка Страуструпа.
Вот и итераторы сделаны по аналогии с указателем — "естественным итератором" для массивов.
ИМХО — это дебилизм — обеспечение обратной совместимости. "Хотели — как лучше, а получилось — как всегда"(с)
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, McSeem2, Вы писали:
MS>Итераторы — это бездарная попытка использовать C++ не по назначению. Теоретически это прикольно, но на практике ничего кроме пожизненного рака головы не получается. Посмотрите на буст — это же просто помойка. Развитие C++ должно закончиться так же как Си и Фортрана. Любые попытки его развивать делают только хуже. В этом плане язык Си — более православный. Он стандартизирован, легок в имплементации и все хорошо. C++ — это монстр и кадавр, обеспокоенный желудочно.
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, McSeem2, Вы писали: LVV>>>Итератор — это объект, обеспечивающий последовательный доступ к элементам контейнера. LVV>>>Вот и все. MS>>А тогда что такое "итератор произвольного доступа"? А такой есть и даже свойство такое есть. Это оксиморон. LVV>Я таких иностранных слов не знаю...
Стыдись, ты ж преп!
LVV>Но В С++ многое сделано в угоду пресловутой обратной совместимости с С — это самая большая ошибка Страуструпа. LVV>Вот и итераторы сделаны по аналогии с указателем — "естественным итератором" для массивов. LVV>ИМХО — это дебилизм — обеспечение обратной совместимости. "Хотели — как лучше, а получилось — как всегда"(с)
Демагогия.
Совместимость с Си тут вообще ни при чем.
Произвольные скачки по массиву — это действительно естественный способ обращаться к его элементам, что в С++, что в Фортране.
Свойство массива как структуры данных такое.
А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками.
Здравствуйте, jazzer, Вы писали:
J>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками.
Коллега на работе написал итератор. Есть некая сильно упакованная структура данных, представляющая набор сегментов полигона с кривыми. Все, что требуется — последовательное чтение, типа "дай мне следующий сегмент". Сегменты бывают разные — типа отрезок, квадратическкая курва или кубическая курва. Казалось бы — итератор для этого — то, что доктор прописал. Но получилось настолько все кучеряво и длинно, что разобраться в этом теперь нетривиально. Получилась ненужная усложнистика на ровном месте. На самом деле все гораздо хуже — есть набор этих полигонов, для них используется итератор более высокого уровня. А сверху еще есть layers, для них — еще более отдельный итератор. В результате приключился взрыв на макаронной фабрике в виде недоступного пониманию спагетти-кода. Всех программистов в радиусе офиса засыпало макаронами. Такие дела.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, McSeem2, Вы писали:
MS>Здравствуйте, jazzer, Вы писали:
J>>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками.
MS>Коллега на работе написал итератор. Есть некая сильно упакованная структура данных, представляющая набор сегментов полигона с кривыми. Все, что требуется — последовательное чтение, типа "дай мне следующий сегмент". Сегменты бывают разные — типа отрезок, квадратическкая курва или кубическая курва. Казалось бы — итератор для этого — то, что доктор прописал. Но получилось настолько все кучеряво и длинно, что разобраться в этом теперь нетривиально. Получилась ненужная усложнистика на ровном месте. На самом деле все гораздо хуже — есть набор этих полигонов, для них используется итератор более высокого уровня. А сверху еще есть layers, для них — еще более отдельный итератор. В результате приключился взрыв на макаронной фабрике в виде недоступного пониманию спагетти-кода. Всех программистов в радиусе офиса засыпало макаронами. Такие дела.
Если честно, я мало что понял
Но вообще, Boost.Iterator сильно помогает сократить количество кода — достаточно просто пару функций реализовать (типа dereference), а все операторы она сама сделает.
Но если сами эти две функции получаются сильно кучерявыми — тады ой
Но вообще, конечно, имеет смысл в самих контейнерах дополнительно предусматривать всякие методы типа for_each (так же, как сейчас предоставляется sort) — они зачастую могут быть сделаны на порядок проще аналогичного кода на итераторах.
Здравствуйте, ononim, Вы писали:
ND>>Я понимаю, ЧТО такое итератор, я понимаю (но не использую пока на практике), что такое графы, очереди, двусвязные списки и т.д. и .п. Я не очень понимаю, в каких конкретно областях эти самые итераторы используются на практике? Вот я и спросил, в нажедже, что опытные люди просто приведут пример из жизни. O>Да пажалста. Я системщик. Обертки-итераторы вокруг FindFirstFile/FindNextFile, перечисление процессов, модулей, потоков etc — все это есть и применяется в нашем текущем проекте.
ND>>Лично я вижу единственное реальное преимущество — мы можем для одной структуры (списка, дерева, ассоциативного массива и т.д.) иметь несколько текущих позиций и перебирать объекты в этих контейнерных структурах независимо — ну, например, имеем один стек, но вершин у него несколько и живут они независимо O>Итератор это обобщенное понятие, придуманное для того чтобы обобщить методы последовательного доступа к элементам различных контейнеров и ничего более. O>Что во первых позволяет не за??ирать голову программиста особенностями потрохов различных контейнеров, во вторых позволяет использовать один и тот же обобщенный (читай — шаблонный) С++ код для работы с различными контейнерами. То бишь читай здесь — http://www.cppreference.com/wiki/stl/algorithm/start и обрати внимание что приведенным там алгоритмам пофиг элементы какого контейнера им скармливают.
Понятно.
FindFirst/FindNext использовал неоднократно (тоже системщик), хотя итератор пока к ним прикрутить как-то желания не возникало. Подумаю.
Лично я ничего против итераторов не имею — мне лишь интересно, насколько широко народ их реально использует (ну, то есть, процентное соотношение объема текста умной книжки по СРР, посвященного итераторам к проценту реального их использования в жизни).
Касаемо выгоды шаблонного С++ кода для работы с различными контейнерами — ну, ИМХО, я опять же сужу по практике. При условии, что итератор готовый библиотечный и мы сами его не пишем, остается проблема ресурсов, которые он сжирает за свое существование. По современным меркам — мелочь. Но вот я когда-о еще в институте писал всяике полезняшки на MSVC. Потом по работе пришлось что-то делать на Delphi. Когда было нужно, залезал в свой старый код, брал готовые отлаженные куски (ну там, со строками работа, с файловыми операциями и т.д.), менял {} на begin-end и экономил на этом кучу времени. А написал бы я красиво с шаблонами, итераторами и прочими оптимайзами — переносимость код бы точно потерял как в ту, так и в другую сторону. Но, повторюсь, наверняка есть и свои плюсы внешних классов-итераторов!
Здравствуйте, Vain, Вы писали:
V>Здравствуйте, rm822, Вы писали:
V>>>Вопросы новичков в STL воспринимаются уже как троллизм? однако. R>>Он нам предлагает сравнить STL c MFC-обрубками, которые тоже построены на итераторах, тока называются они там POSITION. V>Как минимум для итераторов дребуется отдельный класс, POSITION это не класс, т.е. у него нет методов. С этой позиции MFC проще, т.к. меньше сущностей.
Точно, в MFC POSITION — просто переменная, а не класс. А если вы возьмете Борландовский TList, то там еще проще.
Здравствуйте, jazzer, Вы писали:
J>Здравствуйте, McSeem2, Вы писали:
MS>>Здравствуйте, jazzer, Вы писали:
J>>>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками.
MS>>Коллега на работе написал итератор. Есть некая сильно упакованная структура данных, представляющая набор сегментов полигона с кривыми. Все, что требуется — последовательное чтение, типа "дай мне следующий сегмент". Сегменты бывают разные — типа отрезок, квадратическкая курва или кубическая курва. Казалось бы — итератор для этого — то, что доктор прописал. Но получилось настолько все кучеряво и длинно, что разобраться в этом теперь нетривиально. Получилась ненужная усложнистика на ровном месте. На самом деле все гораздо хуже — есть набор этих полигонов, для них используется итератор более высокого уровня. А сверху еще есть layers, для них — еще более отдельный итератор. В результате приключился взрыв на макаронной фабрике в виде недоступного пониманию спагетти-кода. Всех программистов в радиусе офиса засыпало макаронами. Такие дела.
J>Если честно, я мало что понял
J>Но вообще, Boost.Iterator сильно помогает сократить количество кода — достаточно просто пару функций реализовать (типа dereference), а все операторы она сама сделает. J>Но если сами эти две функции получаются сильно кучерявыми — тады ой
J>Но вообще, конечно, имеет смысл в самих контейнерах дополнительно предусматривать всякие методы типа for_each (так же, как сейчас предоставляется sort) — они зачастую могут быть сделаны на порядок проще аналогичного кода на итераторах.
Ну, вы же понимаете, что "она сама сделает" вовсе не означает сокращения количества кода, как Вы написали. Сократите в одном месте — удлините в другом Если мне надо пару десятков параметров массива информационного обмена по MIL-1553 запихать в список и потом находить в них нужный, это три-четыре строчки моего пользовательского кода. Микро- если не наносекунды машинного времени. Та же операция через крутую библиотеку с внешним иетратором уложится в 2 строки пользовательского кода. Но взамен, я получу 200 строк кода библиотечного, где будут сотни ненужных проверок, вызовов, подвызовов, создание монстрозных объектов в памяти и т.д. и т.п. Не дай бог, придется это дело потом трассировать, если что не так! Вот я и спрашиваю, скажем, Вас, где, в каких практических случаях у вас на практике была необходимость использования этих шаблонных чудо-конктейнеров с внешними итераторами? Можете ли вы, анализируя сейчас те случаи, что-либо сказать об их эффективности?
Здравствуйте, ND322, Вы писали:
J>>Но вообще, Boost.Iterator сильно помогает сократить количество кода — достаточно просто пару функций реализовать (типа dereference), а все операторы она сама сделает.
ND>Ну, вы же понимаете, что "она сама сделает" вовсе не означает сокращения количества кода, как Вы написали. Сократите в одном месте — удлините в другом Если мне надо пару десятков параметров массива информационного обмена по MIL-1553 запихать в список и потом находить в них нужный, это три-четыре строчки моего пользовательского кода. Микро- если не наносекунды машинного времени. Та же операция через крутую библиотеку с внешним иетратором уложится в 2 строки пользовательского кода. Но взамен, я получу 200 строк кода библиотечного, где будут сотни ненужных проверок, вызовов, подвызовов, создание монстрозных объектов в памяти и т.д. и т.п. Не дай бог, придется это дело потом трассировать, если что не так! Вот я и спрашиваю, скажем, Вас, где, в каких практических случаях у вас на практике была необходимость использования этих шаблонных чудо-конктейнеров с внешними итераторами? Можете ли вы, анализируя сейчас те случаи, что-либо сказать об их эффективности?
Мне заклинание "MIL-1553" ни о чем не говорит, сорри.
Тем не менее, вы знакомы с CRTP?
Там нулевой оверхед, и Boost.Iterator сделана именно через него.
Так что очень интересно, где вы там нашли монструозные объекты и прочая
Насчет практических случаев — да, использовал многажды, никаких нареканий к эффективности, ибо CRTP.
Здравствуйте, Vain, Вы писали:
V>Так и итераторов будет два, если функцию find обернуть — придётся всегда пару итераторов возвращать, тогда как range уже какбе пара итераторов.
Здравствуйте, morm, Вы писали:
V>>Так и итераторов будет два, если функцию find обернуть — придётся всегда пару итераторов возвращать, тогда как range уже какбе пара итераторов. M>чего й то???
А как ты итератор на валидность проверишь?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, 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.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, jazzer, Вы писали:
J>Мне заклинание "MIL-1553" ни о чем не говорит, сорри. J>Тем не менее, вы знакомы с CRTP? J>Там нулевой оверхед, и Boost.Iterator сделана именно через него. J>Так что очень интересно, где вы там нашли монструозные объекты и прочая
в общем все правильно.
только если я правильно понял McSeem, там надо было путешествовать по различным коллекциям.
то есть итератор должен быть абстрактным -> оверхед виртуального вызова и управления памятью или ручная реализация через свитч.
J>Насчет практических случаев — да, использовал многажды, никаких нареканий к эффективности, ибо CRTP.
ND322 wrote:
> Умные книжки много пишут о прелестях итераторов для различных > контейнеров данных. Обычно приводятся примеры самостоятельных шаблонных > классов, осуществляющих перебор элементов собственно контейнерного > класса.
По факту итераторы -- говно.
Но когда говорят о их прелестях, то имеют в виду, что они позволяют
алготирмам, которые обрабатывают данные, абстрагироваться от
структуры тех данных, которые они обрабатывают. В этом их "прелесть"
с точки зрения дизайнеров STL.
ND322 wrote:
> готовый библиотечный и мы сами его не пишем, остается проблема ресурсов, > которые он сжирает за свое существование. По современным меркам — > мелочь. Но вот я когда-о еще в институте писал всяике полезняшки на
В 80% случаем, а может и в 90, итератор в реализации -- это лиш
прикрытый фиговым листком указатель. Так что никакой накладухи там
нет.
Просто итератор, выделенный как абстракция, позволяет делать их
разными, в том числе и тебе самому.
jazzer wrote:
> Произвольные скачки по массиву — это действительно естественный способ > обращаться к его элементам, что в С++, что в Фортране. > Свойство массива как структуры данных такое.
Вот кстати да. Почему бы не сделать было вместо итераторов
заклад на 3 функции :
-- size()
-- T& operator [] (unsigned n)
-- const T& operator [] (unsigned n) const
Здравствуйте, 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 и т.д.
На этот вопрос, кстати, мне так толком никто и не ответил.
Вероятно, истина как всегда где-то рядом, может быть посередине
V>>>Так и итераторов будет два, если функцию find обернуть — придётся всегда пару итераторов возвращать, тогда как range уже какбе пара итераторов. M>>чего й то??? V>А как ты итератор на валидность проверишь?
Проверять в программе надо только входные данные, ибо они не под вашим контролем. Итератор должен _быть_ валиден, ибо код который вы пишете под вашим контролем. Или нет?
Как много веселых ребят, и все делают велосипед...
XC>Лично мне немного понятнее, когда я вижу в коде 'arr[i]', чем когда '*ptr'; хотя с точки зрения производительности указатели будут быстрее. XC>Итераторы УНИВЕРСАЛЬНЕЕ, но НЕ НАГЛЯДНЕЕ... В том смысле, что запись с участием объекта-коллекции лишний раз подчеркивает, ЧТО ИМЕННО мы делаем в этой строчке. Не просто берем из памяти какое-то значение, а берем конкретно i-тое значение из массива с конкретным именем.
А вот и нифиге. Мне индексы совершенно не наглядны. Я даже если пишу for(...) по массиву заданному голым указателем — использую арифметику указателей, а не индексы. Так что это просто дело привычки — для человека который годами в паскале/бейсике писал for i .... индекс будет конечно нагляднее, а вот для человека "со стороны" — совсем даже не факт.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, 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... При этом имейте в виду, что кто-то возможно захочет итерацию по коллекции в цикле...
Здравствуйте, jazzer, Вы писали:
MS>>>А тогда что такое "итератор произвольного доступа"? А такой есть и даже свойство такое есть. Это оксиморон. LVV>>Я таких иностранных слов не знаю... J>Стыдись, ты ж преп!
LVV>>Но В С++ многое сделано в угоду пресловутой обратной совместимости с С — это самая большая ошибка Страуструпа. LVV>>Вот и итераторы сделаны по аналогии с указателем — "естественным итератором" для массивов. LVV>>ИМХО — это дебилизм — обеспечение обратной совместимости. "Хотели — как лучше, а получилось — как всегда"(с)
J>Демагогия. J>Совместимость с Си тут вообще ни при чем.
Еще как причем... Вот нельзя было бы в С арифметические операции с указателями делать, и не стали бы реализовывать "итератор произвольного доступа" — для совместимости с указателем. J>Произвольные скачки по массиву — это действительно естественный способ обращаться к его элементам, что в С++, что в Фортране. J>Свойство массива как структуры данных такое.
Ага. Только обеспечивается оно индексом, а не итератором. J>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками.
Это от задачи зависит.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
J>>Демагогия. J>>Совместимость с Си тут вообще ни при чем. LVV>Еще как причем... Вот нельзя было бы в С арифметические операции с указателями делать, и не стали бы реализовывать "итератор произвольного доступа" — для совместимости с указателем. J>Произвольные скачки по массиву — это действительно естественный способ обращаться к его элементам, что в С++, что в Фортране. J>>Свойство массива как структуры данных такое. LVV>Ага. Только обеспечивается оно индексом, а не итератором.
без разницы, если не касаться вопросов инвалидации.
Индексы точно так же радостно вычитают и складывают.
Ты ж преп, вспомни методы прогонки, численного дифференцирования — они все в терминах итераторов (отношений индексов) формулируются, сплошь i и рядом i+1, i-1 и т.д.
J>>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками. LVV>Это от задачи зависит.
что от задачи зависит? Скорость перемещения итератора произвольного доступа?
Здравствуйте, jazzer, Вы писали:
J>>>Свойство массива как структуры данных такое. LVV>>Ага. Только обеспечивается оно индексом, а не итератором. J>без разницы, если не касаться вопросов инвалидации. J>Индексы точно так же радостно вычитают и складывают. J>Ты ж преп, вспомни методы прогонки, численного дифференцирования — они все в терминах итераторов (отношений индексов) формулируются, сплошь i и рядом i+1, i-1 и т.д.
1. Хорош уже бублик крошить на препода...
2. Не...
Зачем нам две одинаковых сущности на одном месте? Не следует плодить их без надобности.
Итератор — это именно для последовательного доступа предназначен. То, что он в С++ такой произвольный получился — это идеологически неправильно.
Но оправдано наличием указателей для массивов и идеей обратной совместимости. J>>>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками. LVV>>Это от задачи зависит. J>что от задачи зависит? Скорость перемещения итератора произвольного доступа?
Не. Потребность в произвольном итераторе.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, MasterZiv, Вы писали:
MZ>ND322 wrote:
>> готовый библиотечный и мы сами его не пишем, остается проблема ресурсов, >> которые он сжирает за свое существование. По современным меркам — >> мелочь. Но вот я когда-о еще в институте писал всяике полезняшки на
MZ>В 80% случаем, а может и в 90, итератор в реализации -- это лиш MZ>прикрытый фиговым листком указатель. Так что никакой накладухи там MZ>нет.
MZ>Просто итератор, выделенный как абстракция, позволяет делать их MZ>разными, в том числе и тебе самому.
Согласен. Но отдельный класс со своей иерархией, VMT, это все-таки накладуха плюс дополнительный код в котором можно насажать ошибок. Вопрос простой — любая нормальная библиотека, где есть контейнеры, будет иметь для них базовый класс (вероятнее всего, абстрактный). Если в нем предусмотреть методы перебора — next, prev, for_each, operator[]..., а потом их реализовывать в соответствующих потомках (очередь, список, стек...), то разве не будет того же эффекта но проще и дешевле? Разве не логично, что каждый контейнер сам знает, как себя итерировать, но использует для этого стандартный интерфейс?
Здравствуйте, jazzer, Вы писали:
J>Здравствуйте, ND322, Вы писали:
J>>>Но вообще, Boost.Iterator сильно помогает сократить количество кода — достаточно просто пару функций реализовать (типа dereference), а все операторы она сама сделает.
ND>>Ну, вы же понимаете, что "она сама сделает" вовсе не означает сокращения количества кода, как Вы написали. Сократите в одном месте — удлините в другом Если мне надо пару десятков параметров массива информационного обмена по MIL-1553 запихать в список и потом находить в них нужный, это три-четыре строчки моего пользовательского кода. Микро- если не наносекунды машинного времени. Та же операция через крутую библиотеку с внешним иетратором уложится в 2 строки пользовательского кода. Но взамен, я получу 200 строк кода библиотечного, где будут сотни ненужных проверок, вызовов, подвызовов, создание монстрозных объектов в памяти и т.д. и т.п. Не дай бог, придется это дело потом трассировать, если что не так! Вот я и спрашиваю, скажем, Вас, где, в каких практических случаях у вас на практике была необходимость использования этих шаблонных чудо-конктейнеров с внешними итераторами? Можете ли вы, анализируя сейчас те случаи, что-либо сказать об их эффективности?
J>Мне заклинание "MIL-1553" ни о чем не говорит, сорри. J>Тем не менее, вы знакомы с CRTP? J>Там нулевой оверхед, и Boost.Iterator сделана именно через него. J>Так что очень интересно, где вы там нашли монструозные объекты и прочая
J>Насчет практических случаев — да, использовал многажды, никаких нареканий к эффективности, ибо CRTP.
Да, знаком, хотя сам таких финтов ни разу не писал. Действительно, оверхед будет нулевой. Виртуельные методы без VMT А в каких случаях использовали, Если не секрет? Только в Boost или использовали вообще как общий подход в работе с контейнерами?
Здравствуйте, saf_e, Вы писали:
_>Здравствуйте, MasterZiv, Вы писали:
MZ>>jazzer wrote:
>>> Произвольные скачки по массиву — это действительно естественный способ >>> обращаться к его элементам, что в С++, что в Фортране. >>> Свойство массива как структуры данных такое.
MZ>>Вот кстати да. Почему бы не сделать было вместо итераторов MZ>>заклад на 3 функции : MZ>>-- size() MZ>>-- T& operator [] (unsigned n) MZ>>-- const T& operator [] (unsigned n) const
MZ>>Ничем не хуже.
_>А теперь придумайте такой же "лисопед" для list, set, map... При этом имейте в виду, что кто-то возможно захочет итерацию по коллекции в цикле...
Эээ, а в чем принципиальная сложность? Я бы расширил список "закладных" функций еще next() /*ну, или operator ++, если угодно*/ и prev() /*или operator --*/ и в соотсетствующем контейнере list, map, set... — реализовал бы соответствующие методы. В чем криминал?
Здравствуйте, x-code, Вы писали: XC>Основной аргумент в пользу итераторов из предложенных выше — итераторы универсальны, т.е. можно одними и теми же алгоритмами обрабатывать и массивы, и списки, и хз что еще. Однако у меня возникает вопрос практической необходимости такой универсальности. В моих программах, как правило, любая коллелкция — это часть какого-либо класса, и она используется там исключительно для конкретных нужд класса. Методы класса реализуют конкретные алгоритмы, связанные с конкретной предметной областью, и как правило очень сильно заточены под логику этой предметной области. Иными словами, алгоритмы обработки конкретной коллекции совершенно бесполезны и бессмысленны для другой коллекции в другом классе.
Ну, собственно, это и был мой вопрос — если я работаю со списком, значит со списком, если с динамическим массивом (вектором), значит с вектором... Ну, собственно, лично я больше не с чем обычно и не работаю Что мне даст красивый итератор, для создания которого придется отводить отдельную память, тратить быстродействие на кучу его внутренних проверок (валидность, равенства нулю/не нулю и т.д и т.п.), обработчиков исключений и т.д. На практике мне обычно бывает нужно всего пара функций для доступа к данным коллекции. ИМХО, дешево-сердито.
Здравствуйте, ND322, Вы писали:
J>>Насчет практических случаев — да, использовал многажды, никаких нареканий к эффективности, ибо CRTP. ND>Да, знаком, хотя сам таких финтов ни разу не писал. Действительно, оверхед будет нулевой. Виртуельные методы без VMT А в каких случаях использовали, Если не секрет? Только в Boost или использовали вообще как общий подход в работе с контейнерами?
Как общий подход. Для своих контейнеров замечательно все работало (и продолжает замечательно работать).
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, jazzer, Вы писали:
J>>>>Свойство массива как структуры данных такое. LVV>>>Ага. Только обеспечивается оно индексом, а не итератором. J>>без разницы, если не касаться вопросов инвалидации. J>>Индексы точно так же радостно вычитают и складывают. J>>Ты ж преп, вспомни методы прогонки, численного дифференцирования — они все в терминах итераторов (отношений индексов) формулируются, сплошь i и рядом i+1, i-1 и т.д. LVV>1. Хорош уже бублик крошить на препода...
Не покрошишь бублик на препода — потом придет неуч на собеседование LVV>Зачем нам две одинаковых сущности на одном месте? Не следует плодить их без надобности.
зачем for, если есть while (не говоря уже о goto)?
LVV>Итератор — это именно для последовательного доступа предназначен. То, что он в С++ такой произвольный получился — это идеологически неправильно.
Еще раз — это просто оптимизация двунаправленного, не более того. LVV>Но оправдано наличием указателей для массивов и идеей обратной совместимости.
Все наоборот — просто массивы и указатели как раз предоставляют константную сложность, в отличие от общего линейного случая.
J>>>>А итератор произвольного доступа — это просто двунаправленный итератор с дополнительным свойством: время перемещения сразу на несколько элементов не зависит от расстояния, в отличие от линейной зависимости в общем случае. Т.е. чисто оптимизационная вещь. Если тебе на скорость наплевать — пиши алгоритмы в терминах двунаправленных итераторов, они будут работать и с массивами, и со списками. LVV>>>Это от задачи зависит. J>>что от задачи зависит? Скорость перемещения итератора произвольного доступа? LVV>Не. Потребность в произвольном итераторе.
Пока ты не упрешься в требования скорости, с тебя вполне двунаправленного хватит. Произвольный — просто оптимизация. Юзай std::advance и будет тебе счастье
Здравствуйте, jazzer, Вы писали:
LVV>>1. Хорош уже бублик крошить на препода... J>Не покрошишь бублик на препода — потом придет неуч на собеседование
Не... Наших расхватывают прям с момента защиты... Даже троечников... LVV>>Зачем нам две одинаковых сущности на одном месте? Не следует плодить их без надобности. J>зачем for, если есть while (не говоря уже о goto)?
Ты знаешь, я тоже задаюсь этим вопросом: зачем нужен for? Студиозов приходится отучать его использовать по поводу и без повода.
лучше for_each использовать...
А вот цикл в сравнении с if+goto — это операция более высокого уровня.
В отличие от произвольного итератора и индекса — они одного поля ягоды. LVV>>Итератор — это именно для последовательного доступа предназначен. То, что он в С++ такой произвольный получился — это идеологически неправильно. J>Еще раз — это просто оптимизация двунаправленного, не более того. LVV>>Но оправдано наличием указателей для массивов и идеей обратной совместимости. LVV>>Потребность в произвольном итераторе. J>Пока ты не упрешься в требования скорости, с тебя вполне двунаправленного хватит. Произвольный — просто оптимизация. Юзай std::advance и будет тебе счастье
Это все понятно. Но хочется идеологически выдержанного итератора. Раз последовательнный доступ — так уж последовательный... Токмо за чистоту идеи и голос поднимаю.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re: Зачем нужен итератор?
От:
Аноним
Дата:
26.07.10 21:52
Оценка:
Итераторы используют чуть менее, чем все, кто использует STL.
Проблем с пониманием нет, с производительностью тоже нет.
Это абсолютно стандартная вещь для программирования на C++, а не какая-то "новомодная". Скорее даже наоборот, "старомодная".
Лично я вижу в STL-ных итераторах только один недостаток — их всегда нужно два, что удлиняет запись.
Я за то, чтобы итератор сам проверял свою валидность. Тогда можно будет писать:
typedef map<string, Item> Items;
Item* FindItem(string name)
{
Items::iterator it = items.find(name);
if (!it)
return NULL;
return it->second;
}
void EnumerateItems()
{
for (Items::iterator it = items.begin(); it; ++it)
{
//...
}
}
Здравствуйте, MasterZiv, Вы писали:
MZ>Вот кстати да. Почему бы не сделать было вместо итераторов MZ>заклад на 3 функции : MZ>-- size() MZ>-- T& operator [] (unsigned n) MZ>-- const T& operator [] (unsigned n) const
MZ>Ничем не хуже.
В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет линейной, поэтому сложность перебора всех элементов с помощью этого интерфейса будет квадратичной.
Здравствуйте, Vain, Вы писали:
V>Здравствуйте, morm, Вы писали:
V>>>Так и итераторов будет два, если функцию find обернуть — придётся всегда пару итераторов возвращать, тогда как range уже какбе пара итераторов. M>>чего й то??? V>А как ты итератор на валидность проверишь?
Тупанул, да А как быть если возвращаешь, допустим, range, потом erase исходного контейнера. Что делать с end'ом в range??
Здравствуйте, x-code, Вы писали:
XC>Основной аргумент в пользу итераторов из предложенных выше — итераторы универсальны, т.е. можно одними и теми же алгоритмами обрабатывать и массивы, и списки, и хз что еще. Однако у меня возникает вопрос практической необходимости такой универсальности. В моих программах, как правило, любая коллелкция — это часть какого-либо класса, и она используется там исключительно для конкретных нужд класса. Методы класса реализуют конкретные алгоритмы, связанные с конкретной предметной областью, и как правило очень сильно заточены под логику этой предметной области. Иными словами, алгоритмы обработки конкретной коллекции совершенно бесполезны и бессмысленны для другой коллекции в другом классе.
Вы пользуетесь algorithm? Если да то вопросов не должно возникать, сортировка поиск первого элемента и т.д., все единообразно для большинства контейнеров. Алгоритм написан и отлажен 1 раз, а не в каждом классе своя вариация.
XC>С точки зрения замены типов коллекций. Часто вижу такой аргумент: если вдруг захочется заменить vector на list или наоборот, то все что нужно сделать — просто заменить тип в объявлении объекта-коллекции. XC>Народ, вот это мне как минимум непонятно... Выбор типа для коллекции — фундаментальная вещь, которая должна делаться один раз в самом начале разработки того или иного класса. Мне и в бреду не придет мысль менять list на vector, если я знаю КАК ИМЕННО я работаю с коллекцией, для каких целей я ее вводил в программ и для чего она там используется...
Ну, бывает и хуже, пишешь новый класс, и понимаешь что у тебя есть какое то множество, объявляешь его std::set<myenum>, написал половину класса и понимаешь что для одного из методов тебе важен порядок в какой было все считано, и меняешь set на vector, часть написанного кода остается а добавление меняется, вот это кстати минус, есть универсальный способ доступа к контейнерам, есть удаление, а вот одного и того же insert нету
Менять list на vector вроде не приходилось, а вот set->multiset в связи с развитием задачи было.
Замена list, vector, deque легко может произойти при оптимизации задач, когда будет видно что узкое горлышко именно из-за контейнера, если у вас в задачах нету ограничений по памяти и времени, то вам вряд ли придется столкнуться с этим.
я стараюсь писать
typedef std::vector<int> TSomeEssence;
а внутри
for (TSomeEssence::iterator it ...), такой код мне банально легче читать, сразу видно какая сущность лежит в контейнере.
Здравствуйте, Аноним, Вы писали:
А>Лично я вижу в STL-ных итераторах только один недостаток — их всегда нужно два, что удлиняет запись.
... причём из одного домена (контейнера), что ещё более удлинняет запись. Особенно, когда ссылка на контейнер приходит извне.
В этом плане, интервалы (range) более удобны.
Изредка требуется тройка итераторов: begin <= middle <= end, которую можно выразить двумя интервалами [begin,middle), [middle,end).
Правда, где тройка, там и четвёрка может потребоваться...
А>Я за то, чтобы итератор сам проверял свою валидность. Тогда можно будет писать:
Для этого
— либо итератор должен иметь доступ к end своего домена, или хранить другой признак вылета за диапазон (особенно, когда речь идёт о поддиапазонах)
— либо это однонаправленный итератор, так что все end можно считать эквивалентными, и заменять на специальное значение (например, NULL)
То есть, или оверхед, или неоправданные ограничения.
Было бы проще написать такой find, который возвращает пару (итератор, успешность).
Тот же самый lower_bound мог бы сразу сообщать, указывает итератор на "меньшее" или "равное" значение.
XC>И еще. Для работы с GUI часто требуется привязать какие-то "итераторы" к элементам контролов (методы типа SetItemData()/GetItemData()). POSITION — это гарантированно 4-байтовое значение, которое легко привязывается простым приведением типов. С итераторами такой номер не прокатит, это класс, который разумеется нельзя приводить к DWORD, void*, LPARAM и т.д. XC>На этот вопрос, кстати, мне так толком никто и не ответил.
Юрий Жмеренецкий wrote: > MZ>Ничем не хуже. > > В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет > линейной, поэтому сложность перебора всех элементов с помощью этого > интерфейса будет квадратичной.
Так а не надо одними алгоритмами обрабатывать и контейнеры с произвольным
доступом, и с последовательным. Ну, максимум будет в два раза больше
реализаций алгоритмов. Это проблема для СТАНДАРТНОЙ библиотеки, которая
один раз пишется ?
x-code wrote:
> Кстати, интересный вопрос. Давайте сравним MFC CList с POSITION и > std:list с его итераторами. > Пользуюсь и тем и другим, но как ни странно, больше нравится CList. Даже > сделал с MFC'шных классов кроссплатформенную реализацию.
+1 (тоже кстати сделали такое, внутри -- реализация на STL )
> Итераторы УНИВЕРСАЛЬНЕЕ, но НЕ НАГЛЯДНЕЕ... В том смысле, что запись с
...
> В случае с MFC CList требуется передавать и итератор, и ссылку на саму > коллекцию.
Это всё -- ерунда. Это проблемы идеологические, проблемы непонимания
> Основной аргумент в пользу итераторов из предложенных выше — итераторы > универсальны, т.е. можно одними и теми же алгоритмами обрабатывать и > массивы, и списки, и хз что еще. Однако у меня возникает вопрос > практической необходимости такой универсальности. В моих программах, как > правило, любая коллелкция — это часть какого-либо класса, и она > используется там исключительно для конкретных нужд класса. Методы класса > реализуют конкретные алгоритмы, связанные с конкретной предметной > областью, и как правило очень сильно заточены под логику этой предметной > области. Иными словами, алгоритмы обработки конкретной коллекции > совершенно бесполезны и бессмысленны для другой коллекции в другом классе. > > С точки зрения замены типов коллекций. Часто вижу такой аргумент: если > вдруг захочется заменить vector на list или наоборот, то все что нужно > сделать — просто заменить тип в объявлении объекта-коллекции.
Это кстати почти миф. Не всегда можно один заменять на другой. Меерс описывал.
> Народ, вот это мне как минимум непонятно... Выбор типа для коллекции — > фундаментальная вещь, которая должна делаться один раз в самом начале > разработки того или иного класса. Мне и в бреду не придет мысль менять > list на vector, если я знаю КАК ИМЕННО я работаю с коллекцией, для каких > целей я ее вводил в программ и для чего она там используется...
+1 +2 ... +100
> И еще. Для работы с GUI часто требуется привязать какие-то "итераторы" к > элементам контролов (методы типа SetItemData()/GetItemData()). POSITION > — это гарантированно 4-байтовое значение, которое легко привязывается > простым приведением типов.
А это вообще хаки грязные. Ты не должен думать, что знаешь, что POSITION
— это гарантированно 4-байтовое значение
Главное, в общем, не это всё. А удобство коллекций с практической точки зрения.
STL академичен и неудобен. Раскрывать идею не буду, думаю и так все согласны.
Здравствуйте, MasterZiv, Вы писали:
MZ>Юрий Жмеренецкий wrote: >> MZ>Ничем не хуже. >> >> В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет >> линейной, поэтому сложность перебора всех элементов с помощью этого >> интерфейса будет квадратичной.
MZ>Так а не надо одними алгоритмами обрабатывать и контейнеры с произвольным MZ>доступом, и с последовательным.
Как будет выглядеть алгоритм перебора всех элементов списка с использованием предложенного интерфейса за линейное время?
ND322 wrote:
> Вопрос простой — любая нормальная библиотека, где есть контейнеры, будет > иметь для них базовый класс (вероятнее всего, абстрактный). Если в нем > предусмотреть методы перебора — next, prev, for_each, operator[]..., а > потом их реализовывать в соответствующих потомках (очередь, список, > стек...), то разве не будет того же эффекта но проще и дешевле?
Разве не > логично, что каждый контейнер сам знает, как себя итерировать, но > использует для этого стандартный интерфейс?
Ты расскажи это создателям STL-я лучше. У них логика особая.
MZ>Ты это кому другому бы рассказывал. Именно "новомодная" эта штука. MZ>Не было ни итераторов, ни вообще STL-я в С++ классическом. MZ>Даже шаблонов не было.
этой "новомодной" штучкой мы на проекте живом пользуемся уже лет 7
если тебе попадаются прикладные проекты на С++ без stl могу только посочувствовать.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, morm, Вы писали:
V>>А как ты итератор на валидность проверишь? M>Тупанул, да А как быть если возвращаешь, допустим, range, потом erase исходного контейнера. Что делать с end'ом в range??
Неподходящее слово "валидность", перегруженное смыслами.
Итераторы, — равно как и ссылки, указатели, диапазоны и прочие косвенности, — инвалидируются при некоторых изменениях контейнера.
Однако, помимо невалидных, есть ещё и сигнальные значения.
У указателей есть одно универсальное сигнальное значение — NULL, а также в роли сигнальных могут выступать указатели за конец массива (end()).
Разыменовывать сигнальный указатель или итератор нельзя. Но если это end, то можно применять к нему адресную арифметику.
В нашем случае, надо проверять не на валидность, а на сигнальность.
Здравствуйте, Vain, Вы писали:
V>Как минимум для итераторов дребуется отдельный класс, POSITION это не класс, т.е. у него нет методов. С этой позиции MFC проще, т.к. меньше сущностей.
Ну как же меньше сущностей: ввели хэндл элемента, в дополнение к адресу и индексу.
POSITION — непрозрачный указатель на узел контейнера, итератор — полупрозрачный указатель на узел (с перегруженными операциями *, ->, ++ и т.д.)
Итератор позволяет совершать некоторые действия напрямую, а хэндл и индекс — только в связке с самим контейнером.
Здравствуйте, ND322, Вы писали:
_>>А теперь придумайте такой же "лисопед" для list, set, map... При этом имейте в виду, что кто-то возможно захочет итерацию по коллекции в цикле... ND>Эээ, а в чем принципиальная сложность? Я бы расширил список "закладных" функций еще next() /*ну, или operator ++, если угодно*/ и prev() /*или operator --*/ и в соотсетствующем контейнере list, map, set... — реализовал бы соответствующие методы. В чем криминал?
... и получил бы опять итератор
Только в профиль и ущербный.
Ибо:
— или контейнер stateful (хранит внутри текущую позицию), и за внешней красотой next(void)/prev(void) мы немедленно лишаемся не то что многопоточности, а даже реентерабельности
— или для итерирования требуется вынести эту текущую позицию наружу: либо в виде итератора (самостоятельного объекта с функциями доступа и навигации), либо в виде хэндла (аргумента этих самых функций Elem& at(POSITION), POSITION next(POSITION))
Юрий Жмеренецкий wrote:
> Как будет выглядеть алгоритм перебора всех элементов списка с > использованием предложенного интерфейса за линейное время?
Я не предлагаю ТОТ ЖЕ алгоритм перебора писать, и С ТЕМИ ЖЕ
функциями. Можно -- давайте те же. Нельзя -- напишим другие,
с другими функциями доступа к коллекции, в чём проблема ?
Даже если они не будут выглядеть одинаково снаружи -- не
проблема, а ещё и лучше -- сразу видно, что контейнеры разные.
ononim wrote:
> этой "новомодной" штучкой мы на проекте живом пользуемся уже лет 7
Я на С++ пишу дольше значит.
> если тебе попадаются прикладные проекты на С++ без stl могу только > посочувствовать.
Да нет у меня таких. Просто и до STL-я и шаблонов С++ жил себе
радостно и не тужил особо. Да, плохо, что не было хорошей стандартной
библиотеки, но её и сейчас нет (хорошей).
Здравствуйте, MasterZiv, Вы писали:
MZ>ND322 wrote:
>> Вопрос простой — любая нормальная библиотека, где есть контейнеры, будет >> иметь для них базовый класс (вероятнее всего, абстрактный). Если в нем >> предусмотреть методы перебора — next, prev, for_each, operator[]..., а >> потом их реализовывать в соответствующих потомках (очередь, список, >> стек...), то разве не будет того же эффекта но проще и дешевле? MZ>Разве не >> логично, что каждый контейнер сам знает, как себя итерировать, но >> использует для этого стандартный интерфейс?
MZ>Ты расскажи это создателям STL-я лучше. У них логика особая.
Ну, хорошо хоть е один я так думаю. А то я уж решил, что совсем ничего не рублю, раз у меня такие вопросы возникают
MZ>Да нет у меня таких. Просто и до STL-я и шаблонов С++ жил себе MZ>радостно и не тужил особо. Да, плохо, что не было хорошей стандартной MZ>библиотеки, но её и сейчас нет (хорошей).
ясно, не перешагнул барьер между "мля, как же все непривычно" и "а блин, как я раньше без этого жил"
ЗЫ А меня от всего МФСшного, включая CList несварение желудка случается. Более отстойной библиотеки чем MFC пожалуй не найти.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, ND322, Вы писали:
_>>>А теперь придумайте такой же "лисопед" для list, set, map... При этом имейте в виду, что кто-то возможно захочет итерацию по коллекции в цикле... ND>>Эээ, а в чем принципиальная сложность? Я бы расширил список "закладных" функций еще next() /*ну, или operator ++, если угодно*/ и prev() /*или operator --*/ и в соотсетствующем контейнере list, map, set... — реализовал бы соответствующие методы. В чем криминал?
К>... и получил бы опять итератор К>Только в профиль и ущербный.
К>Ибо: К>- или контейнер stateful (хранит внутри текущую позицию), и за внешней красотой next(void)/prev(void) мы немедленно лишаемся не то что многопоточности, а даже реентерабельности К>- или для итерирования требуется вынести эту текущую позицию наружу: либо в виде итератора (самостоятельного объекта с функциями доступа и навигации), либо в виде хэндла (аргумента этих самых функций Elem& at(POSITION), POSITION next(POSITION))
Ну и что? Действительно, будет тот же итератор, но внутри самого контейнера. Почему реентерабильности лишусь? Насчет многопоточности, да, я и сам об этом выше писал — это плюс внешних итераторов. Мы имеем один контейнер и сколько угодно текущих позиций для него, который можно двигать туда-сюда независимо от самого контейнера. Ну, как бы, это вполне логично для того узкого круга задач, где несколько потоков должны использовать одну коллекцию. Не скажу за CList, а в борландовской реализации можно спокойно брать i-й элемент списка из разных потоков. Правда, я это делал от силы раз или два... Вопрос, насколько широк круг таких задач на практике?
Здравствуйте, Юрий Жмеренецкий, Вы писали:
ЮЖ>Здравствуйте, MasterZiv, Вы писали:
MZ>>Юрий Жмеренецкий wrote: >>> MZ>Ничем не хуже. >>> >>> В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет >>> линейной, поэтому сложность перебора всех элементов с помощью этого >>> интерфейса будет квадратичной.
MZ>>Так а не надо одними алгоритмами обрабатывать и контейнеры с произвольным MZ>>доступом, и с последовательным.
ЮЖ>Как будет выглядеть алгоритм перебора всех элементов списка с использованием предложенного интерфейса за линейное время?
Не понял, а если те же функции сидят в итераторе в виде самостоятельного класса, у них время перебора будет линейным?
Здравствуйте, ononim, Вы писали:
MZ>>Ты это кому другому бы рассказывал. Именно "новомодная" эта штука. MZ>>Не было ни итераторов, ни вообще STL-я в С++ классическом. MZ>>Даже шаблонов не было. O>этой "новомодной" штучкой мы на проекте живом пользуемся уже лет 7 O>если тебе попадаются прикладные проекты на С++ без stl могу только посочувствовать.
Странно, мне сплошь и рядом попадаются исходники, в которых от STL разве что <stdio> да <string> какие-нибудь.
MZ>>>Не было ни итераторов, ни вообще STL-я в С++ классическом. MZ>>>Даже шаблонов не было. O>>этой "новомодной" штучкой мы на проекте живом пользуемся уже лет 7 O>>если тебе попадаются прикладные проекты на С++ без stl могу только посочувствовать. ND>Странно, мне сплошь и рядом попадаются исходники, в которых от STL разве что <stdio> да <string> какие-нибудь.
Я тоже когдато работал в такой конторе. Контора была полувоенная кстати. Вспоминаю ее как плохой сон.
Кстати что касается контейнеров, то в нашем коде (multi_)set'ов и (multi_)map'ов возможно даже больше чем list'ов и vector'ов. Потому аргументы в данном треде типа вектор и лист ацтой я воще читаю с улыбкой.
Буст тоже используется, но очень в меру.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, ND322, Вы писали:
К>>- или контейнер stateful (хранит внутри текущую позицию), и за внешней красотой next(void)/prev(void) мы немедленно лишаемся не то что многопоточности, а даже реентерабельности К>>- или для итерирования требуется вынести эту текущую позицию наружу: либо в виде итератора (самостоятельного объекта с функциями доступа и навигации), либо в виде хэндла (аргумента этих самых функций Elem& at(POSITION), POSITION next(POSITION))
ND>Ну и что? Действительно, будет тот же итератор, но внутри самого контейнера. Почему реентерабильности лишусь? Насчет многопоточности, да, я и сам об этом выше писал — это плюс внешних итераторов. Мы имеем один контейнер и сколько угодно текущих позиций для него, который можно двигать туда-сюда независимо от самого контейнера. Ну, как бы, это вполне логично для того узкого круга задач, где несколько потоков должны использовать одну коллекцию. Не скажу за CList, а в борландовской реализации можно спокойно брать i-й элемент списка из разных потоков. Правда, я это делал от силы раз или два... Вопрос, насколько широк круг таких задач на практике?
Реентерабельности лишишься, потому что, если контейнер stateful, то в каждый момент может быть запущен только один алгоритм перебора. Никаких вложенных циклов, поскольку самый внутренний цикл изменяет состояние. Либо куча возни по сохранению-восстановлению исходного состояния.
А вынесенный наружу хэндл перебора (будь то явный указатель, или обёрнутый итератор, или осмысленный индекс, или непрозрачный ключ) — тут, разумеется, никаких проблем нет.
С той лишь разницей, что указатели и итераторы позволяют обращаться к элементам напрямую, без контейнера (а итераторы — ещё и перемещаться), тогда как индексы и хэндлы идут строго в паре с контейнером.
Здравствуйте, ononim, Вы писали:
O>ЗЫ А меня от всего МФСшного, включая CList несварение желудка случается. Более отстойной библиотеки чем MFC пожалуй не найти.
Это ты ещё ATL не видел.
Там, блин, для одного и того же есть две сущности: CArray (пришедший из MFC) и CSimpleArray (из WTL?)
И у них разные интерфейсы, вплоть до того, что один использует size_t в качестве размеров и индексов, а другой — int.
CArray, кстати говоря, по умолчанию эксплуатирует неопределённое поведение!!! (Перемещает элементы с помощью memmove).
Кому не нравится — пишите свой трейтс.
К>Это ты ещё ATL не видел.
видел и даже пользуюсь изредка когда ченить комовское по быстрому нуна забодяжить. как то приятнее почему-то, наверно тем что легче и прозрачнее, хотя тяжелое наследие мфц гнетет
Как много веселых ребят, и все делают велосипед...
Здравствуйте, ND322, Вы писали:
ЮЖ>>Как будет выглядеть алгоритм перебора всех элементов списка с использованием предложенного интерфейса за линейное время? ND>Не понял, а если те же функции сидят в итераторе в виде самостоятельного класса, у них время перебора будет линейным?
Да. Итератор хранит текущую позицию, тогда как в 'T& operator [] (unsigned n)' для списка будет использован аналог std::advance (а это уже O(n)).
Здравствуйте, MasterZiv, Вы писали:
>> Как будет выглядеть алгоритм перебора всех элементов списка с >> использованием предложенного интерфейса за линейное время?
MZ>Я не предлагаю ТОТ ЖЕ алгоритм перебора писать, и С ТЕМИ ЖЕ MZ>функциями. Можно -- давайте те же. Нельзя -- напишим другие, MZ>с другими функциями доступа к коллекции, в чём проблема ? MZ>Даже если они не будут выглядеть одинаково снаружи -- не MZ>проблема, а ещё и лучше -- сразу видно, что контейнеры разные.
ок. вот пример:
struct test {
slist_node<test> asc;
slist_node<test> desc;
typedef typename list_iterator< slist_node<test>, &test::asc >::type asc_iterator;
typedef typename list_iterator< slist_node<test>, &test::asc >::type desc_iterator;
int data;
};
slist< test, test::asc_iterator > asc_list;
slist< test, test::desc_iterator > desc_list;
template< typename Range >
void print ( Range const & r ) {
for( Range::iterator it = begin( r ); it != end( r ); increment( it ) ) {
std::cout << it->data << std::endl;
}
}
до вот этого твоего поста, я думал что высказывающиеся здесь против STL и итераторов валяют дурака, застряли в 90х и т.п.
теперь во всяком случае понятно откуда может взяться такая точка зрения
Здравствуйте, rm822, Вы писали:
R>до вот этого твоего поста, я думал что высказывающиеся здесь против STL и итераторов валяют дурака, застряли в 90х и т.п. R>теперь во всяком случае понятно откуда может взяться такая точка зрения
пример надуманный, просто было интересно, как предлагается обходить коллекции с различными алгоритмами итерирования.
ononim wrote:
> ЗЫ А меня от всего МФСшного, включая CList несварение желудка случается. > Более отстойной библиотеки чем MFC пожалуй не найти.
Меня тоже от CList передёргивает, но попробуй на STD напиши коллекцию-
хранилище полиморфных объектов, которое бы само удаляло объекты
при удалении их из хранилища. (shared-ptr не предлагать — +4 байта на
каждый хранимый объект не катит). А на MFC-шных -- в момент пишется.
STL не различает ситуацию удаления элемента из коллекции и ситуацию
перенесения объекта из одного буфера коллекции в другой (новый).
Потому что академичный, блин.
MZ>Меня тоже от CList передёргивает, но попробуй на STD напиши коллекцию- MZ>хранилище полиморфных объектов, которое бы само удаляло объекты MZ>при удалении их из хранилища. (shared-ptr не предлагать — +4 байта на MZ>каждый хранимый объект не катит). А на MFC-шных -- в момент пишется.
в std алгоритмах бывает используются временные переменные, так что твое решение не катит.
формально, задачу решает наследование от std::vector<FooPtr> и нужного определение деструктора.
Здравствуйте, Юрий Жмеренецкий, Вы писали:
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];
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> и нужного > определение деструктора.
Этого, блин, МАЛО. Нужно ещё заставить различаться ситуацию удаления
элементов НАСОВСЕМ от переноса их в новое хранилище.
Я ничего кроме написания собственного аллокатора с состоянием не
придумал. Решение непереносимо и ужасно.
Здравствуйте, MasterZiv, Вы писали:
MZ>Меня тоже от CList передёргивает, но попробуй на STD напиши коллекцию- MZ>хранилище полиморфных объектов, которое бы само удаляло объекты MZ>при удалении их из хранилища. (shared-ptr не предлагать — +4 байта на MZ>каждый хранимый объект не катит). А на MFC-шных -- в момент пишется.
Скорее, потому что в стандарте 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();
Кодт wrote:
> Скорее, потому что в стандарте 98 нет move constructor.
Так почему было либо не добавить его туда
либо не использовать просто функцию ?
> А MFC-шные фокусы с memmove — имеют ограниченную применимость.
Ни разу ещё на это не напарывался.
Впрочем, я в своём коде давно отказался от использования MFC-шных
коллекций.
> Но, если очень хочется, можно сделать руками.
Я не про это. Я про перенос ЭЛЕМЕНТОВ коллекций из одного
хранилища в другое. При переносе вызываются конструктор
в новом месте (копирования) и деструктор в старом месте.
В случае удаления -- просто деструктор. Ну и как
определить, что элемент из коллекции удаляют насовсем ?
Только без защиты от использования с стандартными контейнерами, которые требуют от элементов, чтобы они были CopyConstructible и CopyAssignable, с обязательной эквивалентностью копий.
Здравствуйте, MasterZiv, Вы писали:
>> Скорее, потому что в стандарте 98 нет move constructor.
MZ>Так почему было либо не добавить его туда либо не использовать просто функцию ?
Добавить КУДА? в интерфейс произвольного объекта (рядом с ctor, cctor, dtor) или в интерфейс контейнера?
>> А MFC-шные фокусы с memmove — имеют ограниченную применимость.
MZ>Ни разу ещё на это не напарывался. MZ>Впрочем, я в своём коде давно отказался от использования MFC-шных коллекций.
>> Но, если очень хочется, можно сделать руками.
MZ>Я не про это. Я про перенос ЭЛЕМЕНТОВ коллекций из одного хранилища в другое. MZ>При переносе вызываются конструктор в новом месте (копирования) и деструктор в старом месте. MZ>В случае удаления -- просто деструктор. MZ>Ну и как определить, что элемент из коллекции удаляют насовсем ?
А его в обоих случаях удаляют насовсем.
Просто, вместо глубокого копирования и глубокого разрушения можно применить трюк с созданием пустого объекта и обменом содержимым.
Для POD-типов и некоторых других вместо обмена можно применить memmove, что, собственно, CArray и делает.
Или ты имеешь в виду именно списки?
Так у std::list есть функция splice, как раз для того, чтобы переносить цепочку узлов из одного контейнера в другой, без конструирования-разрушения.
Кодт wrote:
> Добавить КУДА? в интерфейс произвольного объекта (рядом с ctor, cctor, > dtor) или в интерфейс контейнера?
Да в стандарт. STL добавили, а
> А его в обоих случаях удаляют насовсем.
Здрасте, приехали.
> Просто, вместо глубокого копирования и глубокого разрушения можно > применить трюк с созданием пустого объекта и обменом содержимым. > Для POD-типов и некоторых других вместо обмена можно применить memmove, > что, собственно, CArray и делает. > > Или ты имеешь в виду именно списки? > Так у std::list есть функция splice, как раз для того, чтобы переносить > цепочку узлов из одного контейнера в другой, без конструирования-разрушения.
Нет, именно вектора.
Я не понимаю, как можно не понимать глубокой разницы между ПЕРЕМЕЩЕНИЕМ
элемента коллекции из одного хранилища в другое (что вообще-то внутреннее
дело коллекции и нас вообще касаться не должно) и УДАЛЕНИЕМ элемента или
добавлением элемента в коллекцию. Разные же вещи. В STL -- одно и то же.
В MFC-шных коллекциях различается чётко и ясно.
>> C>Поздравляю, ononim, Вы изобрели std::auto_ptr<T>: >> я знаю MZ>Интересно, а что std::auto_ptr<T> в стандартных контейнерах MZ>хранить нельзя, не знал ?
знал
но в некоторых реализациях STL можно
но так делать нельзя, я знаю
Как много веселых ребят, и все делают велосипед...
Здравствуйте, 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-безопасных).
Здравствуйте, zitz, Вы писали: ЮЖ>>В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет линейной, поэтому сложность перебора всех элементов с помощью этого интерфейса будет квадратичной. Z>Я делал себе такую штуку для множества, достаточно ввести m_nNextIndex и последовательный перебор всех значений (а у меня в основном такой) будет иметь обычную сложность. Z>Эх, люблю я цикл for( int i=0; i<set.GetCount(); i++) set[i];
В таком решении присутствует нарушение SRP — на контейнер возложено больше обязанностей, чем необходимо, соответственно на ровном месте возникает усложнение контракта контейнера и его реализации. Как следствие — потеря реентерабельности (см. сообщение Кодт'а). Кстати, перечисление в обратном порядке выполняется за O(n^2).
Здравствуйте, 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>придумал. Решение непереносимо и ужасно.
деструктор это и есть удаление элементов насовсем.
можно более конкретно описать задачу?
night beast wrote:
> или я не понял задачу, или одно из двух; > расширение вектора не вызывает деструкторов хранящихся в нем объектов. > итераторы вектора да, становятся не валидными. хочешь обратного, > используй list
Ты уверен ?
> деструктор это и есть удаление элементов насовсем. > можно более конкретно описать задачу?
Да я уже описал. Хранить в коллекции (ну давай для конкретики вектор)
полиморфные объекты, унаследованные от класса, скажем, CMyFavoriteObject,
по ссылке, без дополнительных накладных расходов по памяти и так,
чтобы коллекция была бы ответственна за удаление этих объектов
(т.е. клиент удалил из коллекции элемент -- он удалился вообще,
т.е. delete).
Кодт wrote:
> Объект располагается где-то в памяти. Когда мы освобождаем эту память > (возвращаем её в кучу, либо оставляем пустой для грядущих добавлений), > куда девается объект? Уничтожается.
Ты по-моему совсем меня не понимаешь. Я совсем о другом.
> Ну хорошо, в MFC/ATL есть у контейнеров метод RelocateElements. > И часто ты им пользуешься?
Вообще не использую. Но там есть замечательный
глобальный метод типа
void AFXAPI DestructElements( MyClass **pElements, int nCount );
который достаточно определить для твоего хранимого
в контейнере типа и он будет вызываться при удалении
элементов из контейнера.
> Вообще, идеология STL такова, что обычные контейнеры необязательно > эффективны, но зато универсальны. > Когда возникает желание побороться за производительность, — пиши свой > контейнер. Хочешь — делай его STL-like, не хочешь — не делай.
Дело не в производительности, а именно в универсальности. Перемещение
элемента в другое хранилище -- отдельная операция, она НЕ СВЯЗАНА
с удалением объекта вообще никак. Так вот именно она должна
была специфицирована в стандарте и как-то реализована. Но ребята
решили притвориться академиками и не париться. Конструктор-деструктор.
Типа другого пути нет.
Здравствуйте, MasterZiv, Вы писали:
>> или я не понял задачу, или одно из двух; >> расширение вектора не вызывает деструкторов хранящихся в нем объектов. >> итераторы вектора да, становятся не валидными. хочешь обратного, >> используй list
MZ>Ты уверен ?
был уверен. посмотрел -- облом
в оправдание могу сказать, что пользуюсь своими поделками
>> деструктор это и есть удаление элементов насовсем. >> можно более конкретно описать задачу?
MZ>Да я уже описал. Хранить в коллекции (ну давай для конкретики вектор) MZ>полиморфные объекты, унаследованные от класса, скажем, CMyFavoriteObject, MZ>по ссылке, без дополнительных накладных расходов по памяти и так, MZ>чтобы коллекция была бы ответственна за удаление этих объектов MZ>(т.е. клиент удалил из коллекции элемент -- он удалился вообще, MZ>т.е. delete).
boost::ptr_vector (уже было озвучено) не подходит?
Здравствуйте, MasterZiv, Вы писали:
MZ>Дело не в производительности, а именно в универсальности. Перемещение MZ>элемента в другое хранилище -- отдельная операция, она НЕ СВЯЗАНА MZ>с удалением объекта вообще никак. Так вот именно она должна MZ>была специфицирована в стандарте и как-то реализована. Но ребята MZ>решили притвориться академиками и не париться. Конструктор-деструктор. MZ>Типа другого пути нет.
Ты, видимо, упорно путаешь CArray и его производные — CPtrArray, CObArray.
Их элементы — указатели. Понимаешь, указатели, а не указуемые значения.
Если тебе хочется, чтобы контейнер выполнял глубокое копирование и глубокое удаление (указателей вместе с указуемыми) — пожалуйста, boost::ptr_vector.
Или vector<shared_ptr>, если не хочешь иметь разные траблы с монопольным владением.
Здравствуйте, MasterZiv, Вы писали:
>> был уверен. посмотрел -- облом >> в оправдание могу сказать, что пользуюсь своими поделками
MZ>Ты так не шути больше. Меня чуть кандратий не хватил. MZ>Думал -- усё, сбрендил.
>> boost::ptr_vector (уже было озвучено) не подходит?
MZ>Это не STL. Я могу и сам написать ( и сделал так ). MZ>Вопрос не в этом, а в том, что это должно быть в стандартной MZ>библиотеке.
дык претензии были к итераторам. по крайней мере в топике так написано.
а итераторы вполне полезная вещь.
MZ>Ну ладно, пора кончать уже с этим топиком.
Здравствуйте, MasterZiv, Вы писали:
MZ>Юрий Жмеренецкий wrote:
>> Как будет выглядеть алгоритм перебора всех элементов списка с >> использованием предложенного интерфейса за линейное время?
MZ>Я не предлагаю ТОТ ЖЕ алгоритм перебора писать, и С ТЕМИ ЖЕ MZ>функциями. Можно -- давайте те же. Нельзя -- напишим другие, MZ>с другими функциями доступа к коллекции, в чём проблема ? MZ>Даже если они не будут выглядеть одинаково снаружи -- не MZ>проблема, а ещё и лучше -- сразу видно, что контейнеры разные.
Тогда это ухудшение , потому что теряется универсальность. ПОпробуйте рассуждать в терминах , преимущества недостатки различных подходов. вместо "мне обычно хватает доступа по индекусу".
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, morm, Вы писали:
V>>>А как ты итератор на валидность проверишь? M>>Тупанул, да А как быть если возвращаешь, допустим, range, потом erase исходного контейнера. Что делать с end'ом в range??
К>Неподходящее слово "валидность", перегруженное смыслами.
К>Итераторы, — равно как и ссылки, указатели, диапазоны и прочие косвенности, — инвалидируются при некоторых изменениях контейнера.
К>Однако, помимо невалидных, есть ещё и сигнальные значения. К>У указателей есть одно универсальное сигнальное значение — NULL, а также в роли сигнальных могут выступать указатели за конец массива (end()). К>Разыменовывать сигнальный указатель или итератор нельзя. Но если это end, то можно применять к нему адресную арифметику.
К>В нашем случае, надо проверять не на валидность, а на сигнальность.
Согласен и ,тем не менее, при изменении end() контейнера ВСЕ range, допустим, полученые через MType::range = m.find(v); — тю-тю...
Мне что-то больше нравится с итератором вариант.
Здравствуйте, morm, Вы писали:
К>>В нашем случае, надо проверять не на валидность, а на сигнальность. M>Согласен и ,тем не менее, при изменении end() контейнера ВСЕ range, допустим, полученые через MType::range = m.find(v); — тю-тю... M>Мне что-то больше нравится с итератором вариант.
Следовательно, если мы хотим хранить результат поиска — то должны хранить лишь то, что нам нужно.
Не [it,end), а [it,it]
С итератором, кстати, та же фигня, только немного реже. Ведь мы можем использовать значение it=end() в каких-то своих целях позже.
Начиная с отложенной проверки на сигнальность, и кончая вставкой в заданную позицию.
Впрочем, есть хорошие новости!
Для контейнеров с индивидуальными узлами (list, set, map...) значение end() неизменно, поэтому ни итератор, ни диапазон поиска не инвалидируется.
А вот для вектора — уменьшение размера инвалидирует все хвостовые итераторы, включая end(). Тут будет всё плохо.
Здравствуйте, ND322, Вы писали:
ND>Умные книжки много пишут о прелестях итераторов для различных контейнеров данных. Обычно приводятся примеры самостоятельных шаблонных классов, осуществляющих перебор элементов собственно контейнерного класса. Вот снова попалось в литературе, решил спросить мнение гуру. Где используются эти пресловутые классы-итераторы?
Оценить мощь итераторов и внешних алгоритмов на простых примерах не выйдет. Фундаментальное отличие STL от других библиотек состоит в том что STL — это конструктор из которого лего собрать все что портебуется.
Как примеры приведу http://stxxl.sourceforge.net/ — "STXXL implements containers and algorithms that can process huge volumes of data" http://tech.unige.ch/omptl/ — "The OMPTL re-implement the algorithm and numeric part of the STL. The range is partitioned, then the computation is executed in parallel." http://code.google.com/p/thrust/ — "Thrust is a CUDA library of parallel algorithms with an interface resembling the C++ STL."
Для того чтобы эта круть была востребована нужно выйти за рамки тривиальных задач: нужны особые требования к быстродействию, потреблению памяти, масштабируемости на multicpu\multicore машинах, транзакцонности, нужно обрабатывать большие массивы данных, писать свои собственные алгоритмы и контейнеры и т.д. и т.п.
ND>Лично мне на практике всегда хватало его возможностей. Чего я не понимаю в этой жизни?
угу. Уже довольно давно нет одноядерных процессоров, как циклы параллелить будешь?
Здравствуйте, McSeem2, Вы писали:
MS>Итераторы — это бездарная попытка использовать C++ не по назначению. Теоретически это прикольно, но на практике ничего кроме пожизненного рака головы не получается.
Здравствуйте, MasterZiv, Вы писали:
MZ>jazzer wrote:
>> Произвольные скачки по массиву — это действительно естественный способ >> обращаться к его элементам, что в С++, что в Фортране. >> Свойство массива как структуры данных такое.
MZ>Вот кстати да. Почему бы не сделать было вместо итераторов MZ>заклад на 3 функции : MZ>-- size() MZ>-- T& operator [] (unsigned n) MZ>-- const T& operator [] (unsigned n) const
MZ>Ничем не хуже.
Здравствуйте, ND322, Вы писали:
ND>Если мне надо пару десятков параметров массива информационного обмена по MIL-1553 запихать в список и потом находить в них нужный, это три-четыре строчки моего пользовательского кода. Микро- если не наносекунды машинного времени. Та же операция через крутую библиотеку с внешним иетратором уложится в 2 строки пользовательского кода. Но взамен, я получу 200 строк кода библиотечного, где будут сотни ненужных проверок, вызовов, подвызовов, создание монстрозных объектов в памяти и т.д. и т.п.
ND>Вот я и спрашиваю, скажем, Вас, где, в каких практических случаях у вас на практике была необходимость использования этих шаблонных чудо-конктейнеров с внешними итераторами? Можете ли вы, анализируя сейчас те случаи, что-либо сказать об их эффективности?
Здравствуйте, Юрий Жмеренецкий, Вы писали:
ЮЖ>В таком решении присутствует нарушение SRP — на контейнер возложено больше обязанностей, чем необходимо, соответственно на ровном месте возникает усложнение контракта контейнера и его реализации. Как следствие — потеря реентерабельности (см. сообщение Кодт'а). Кстати, перечисление в обратном порядке выполняется за O(n^2).
Это мой контейнер, я возложил на него столько обязанностей сколько мне необходимо, это раз
На сколько сложна реализация контейнера лично мне не принципиально, лишь бы он выполнял возложенные на него обязанности, это два
Мне не нужно перечисление в обратном порядке, а если станет нужно и если данная функция будет сильно тормозить весь код, то я без проблем допишу, ведь так? Это три
Я это к чему всё? Не к тому что я придумал универсальный контейнер который покроет все нужны (этот класс не публичный и только для моих целей используется), а к тому что, приложив немного серого вещества можно опровергнуть теорему Юрия Жмеренецкого: ЮЖ>В случае, например списка, сложноть 'T& operator [] (unsigned n)' будет линейной, поэтому сложность перебора всех элементов с помощью этого интерфейса будет квадратичной.
Здравствуйте, zitz, Вы писали:
ЮЖ>>В таком решении присутствует нарушение SRP — на контейнер возложено больше обязанностей, чем необходимо, соответственно на ровном месте возникает усложнение контракта контейнера и его реализации. Как следствие — потеря реентерабельности (см. сообщение Кодт'а). Кстати, перечисление в обратном порядке выполняется за O(n^2).
Z>Это мой контейнер, я возложил на него столько обязанностей сколько мне необходимо, это раз
Как говорится, wish you happy debug.
Я встречал ситуации, когда кривой дизайн аукался спустя год успешного использования.
И один из таких случаев был, как раз, — склеивание коллекции с итератором.
Там была такая история: некий ком-объект, содержащий список. И выбор — либо реализовывать ещё один ком-класс с итератором, либо сделать по-быстрому, расширить интерфейс коллекции.
Здравствуйте, Кодт, Вы писали:
Z>>Это мой контейнер, я возложил на него столько обязанностей сколько мне необходимо, это раз
К>Как говорится, wish you happy debug. К>Я встречал ситуации, когда кривой дизайн аукался спустя год успешного использования. К>И один из таких случаев был, как раз, — склеивание коллекции с итератором. К>Там была такая история: некий ком-объект, содержащий список. И выбор — либо реализовывать ещё один ком-класс с итератором, либо сделать по-быстрому, расширить интерфейс коллекции.
Спасибо за предупреждение! И за то что делетись опытом!
У меня всё не так критично и печально, т.к. по сути мой класс является обёрткой над std::set с очень урезанным интерфейсом (он собственно для этого и написан — чтобы лишнего ничего не было), ввобдить для него итераторы только для последовательного перебора — я посчитал это лишим и сделал operator[].
Здравствуйте, zitz, Вы писали:
Z>У меня всё не так критично и печально, т.к. по сути мой класс является обёрткой над std::set с очень урезанным интерфейсом (он собственно для этого и написан — чтобы лишнего ничего не было), ввобдить для него итераторы только для последовательного перебора — я посчитал это лишим и сделал operator[]. 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).
А для однопоточного применения — создание копий сильно избыточно.
Эрго, арбитражем таких взаимодействий должен заниматься тот, кто в арбитраже компетентен. То есть, владелец обоих контейнеров.
К>А зачем здесь m_pNextPosition и m_nNextIndex ? В интерфейсе же нет GetCurrent() / SeekNext() / etc. К>Да, собственно, и std::set не наблюдается.
Это закрытая часть класса, тот кто его использует не должен об этом задумываться
std::set скрыт через void*, чтобы не делать лишние инклюды
Можно было конечно пойти до конца и скрыть вообще всё в void* m_pData, но я пока не настолько фанатичен
Зачем они используются можно глянуть тут: Re[7]: Зачем нужен итератор?
Z>>З.Ы. У меня основная причина (не относящаяся к данному случаю) happy debug — выход за границы массива/памяти и многопоточность
К>С многопоточностью всё просто: объявить, что контейнер не многопоточный. И пусть владельцы контейнера самостоятельно сериализуют доступ к нему.
Да я не про контейнеры, я вообще в целом. Вот последний пример happy debug — это падение из-за WM_PAINT когда при отрисовке идет обращение к данным которые были уничтожены вторым потоком (причем уничтожены не явно, вызовом какого-нить внешне безобидного метода), тут бывает вообще трудно уловить из-за чего падает и даже где падает. В общем страсти-мордасти
Здравствуйте, ND322, Вы писали:
ND>Вот снова попалось в литературе, решил спросить мнение гуру. Где и как на практике используется эта крутизна? В чем преимущество перед обыкновенным CList\TList, который перебирает сои элементы сам без всяких сложных конструкций. Лично мне на практике всегда хватало его возможностей. Чего я не понимаю в этой жизни? Где используются эти пресловутые классы-итераторы? ND>Заранее спасибо!
Я не гуру, и итераторы не люблю. Но пример приведу.
Просто для того, чтобы было яснее что такое итераторы и зачем они нужны.
Вот представь себе, что нам надо сделать коллекцию, которая хранит последовательность часто повторяющихся элементов.
Ну типа последовательность атрибутов букв текста. Скажем имён шрифтов или стилей.
Понятно, что если мы сделаем просто массив и работать будем просто по индексу, то будет большой перерасход памяти. Так как стиль переключают всего несколько раз на абзац. Кроме того доступ к группам (найти следующую буквы другого стиля) будет трудный.
Можно сделать массив пар из диапазона индексов и имени стиля. Но доступ по индексу будет непростой. Зато доступ к группам будет простой.
Подход с итераторами позволяет хранить просто массив пар {атрибут, сколько повторов}. Написать итератор по буквам поверх итератора такой структуры -- просто. Написать итератор по группам -- вообще ничего писать не надо. Всё просто, быстро, удобно
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
ND>Вопрос простой — любая нормальная библиотека, где есть контейнеры, будет иметь для них базовый класс (вероятнее всего, абстрактный).
есть просто куча нормальных библ, ни разу ни ООП при этом
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Igore, Вы писали:
I>Ну, бывает и хуже, пишешь новый класс, и понимаешь что у тебя есть какое то множество, объявляешь его std::set<myenum>, написал половину класса и понимаешь что для одного из методов тебе важен порядок в какой было все считано, и меняешь set на vector, часть написанного кода остается а добавление меняется, вот это кстати минус, есть универсальный способ доступа к контейнерам, есть удаление, а вот одного и того же insert нету
Это действительно бывает и действительно намного хуже. Чтобы так не было программы стоит проектировать, однако
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, ononim, Вы писали:
O>ЗЫ А меня от всего МФСшного, включая CList несварение желудка случается. Более отстойной библиотеки чем MFC пожалуй не найти.
Не-не-не! Пределов совершенству нет!!!
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, minorlogic, Вы писали:
M>Тогда это ухудшение , потому что теряется универсальность. ПОпробуйте рассуждать в терминах , преимущества недостатки различных подходов. вместо "мне обычно хватает доступа по индекусу".
Ну так давно же известно, что универсальные решения в каждом конкретном случае хуже, зато они универсальные...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
M>Согласен и ,тем не менее, при изменении end() контейнера ВСЕ range, допустим, полученые через MType::range = m.find(v); — тю-тю... M>Мне что-то больше нравится с итератором вариант.
Что-то тут не так. Если тухнет end, то тухнут и все остальные итераторы вроде как...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, minorlogic, Вы писали:
M>>Тогда это ухудшение , потому что теряется универсальность. ПОпробуйте рассуждать в терминах , преимущества недостатки различных подходов. вместо "мне обычно хватает доступа по индекусу".
E>Ну так давно же известно, что универсальные решения в каждом конкретном случае хуже, зато они универсальные...
Восхитительный техничекий аргумент. Особенно перфоманс бенчмарки.
Здравствуйте, minorlogic, Вы писали:
E>>Ну так давно же известно, что универсальные решения в каждом конкретном случае хуже, зато они универсальные... M>Восхитительный техничекий аргумент. Особенно перфоманс бенчмарки.
Ты оспариваешь тезис, что универсальность обычно небесплатна?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, minorlogic, Вы писали:
E>>>Ну так давно же известно, что универсальные решения в каждом конкретном случае хуже, зато они универсальные... M>>Восхитительный техничекий аргумент. Особенно перфоманс бенчмарки. E>Ты оспариваешь тезис, что универсальность обычно небесплатна?
Здравствуйте, Кодт, Вы писали:
К>begin и middle валидны, end протух, last... как минимум, стал нечитаемым (v.end()==last), формально — протух.
Гарантии нет. Вдруг был всего один элемент в векторе?
Кроме того, я не помню, есть ли гарантии для вектора в котором, скажем, 10 элементов.
Если помнишь, процитируй, что ли, как они формулируются. Чисто для полноты картины.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, 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.
То есть, стандарт умалчивает, происходит ли переразмещение при удалениях.
Но можно предположить, что — нет, не происходит. Иначе бы последняя фраза звучала так: заведомо инвалидирует хвост, но и в голове тоже поберегись!
Здравствуйте, ononim, Вы писали:
V>>>>Так и итераторов будет два, если функцию find обернуть — придётся всегда пару итераторов возвращать, тогда как range уже какбе пара итераторов. M>>>чего й то??? V>>А как ты итератор на валидность проверишь? O>Проверять в программе надо только входные данные, ибо они не под вашим контролем. Итератор должен _быть_ валиден, ибо код который вы пишете под вашим контролем. Или нет?
Не обязательно, если итератор будет потом использоваться, то его надо проверить на валидность посредством сравнения с концом.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, 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.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, Vain, Вы писали:
V>Не обязательно, если итератор будет потом использоваться, то его надо проверить на валидность посредством сравнения с концом.
Вообще-то, валидность/невалидность итератора никак не связана с равенством/неравенством концу контейнера. Итератор, полученный с помощью end(), изначально валиден, и может стать невалидным впоследствии, в результате переаллокации, например. Невалидность итератора означает, что над ним нельзя выполнять никакие операции, в т.ч. сравнения, в т.ч. с концом. И проверить валидность итератора в общем случае нельзя, программа должна отслеживать валидность итераторов исходя из собственной логики.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
V>>Не обязательно, если итератор будет потом использоваться, то его надо проверить на валидность посредством сравнения с концом. R>Вообще-то, валидность/невалидность итератора никак не связана с равенством/неравенством концу контейнера. Итератор, полученный с помощью end(), изначально валиден, и может стать невалидным впоследствии, в результате переаллокации, например. Невалидность итератора означает, что над ним нельзя выполнять никакие операции, в т.ч. сравнения, в т.ч. с концом. И проверить валидность итератора в общем случае нельзя, программа должна отслеживать валидность итераторов исходя из собственной логики.
Ну если радеть за чистоту понятий то да
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, rg45, Вы писали:
V>>Не обязательно, если итератор будет потом использоваться, то его надо проверить на валидность посредством сравнения с концом. R>Вообще-то, валидность/невалидность итератора никак не связана с равенством/неравенством концу контейнера. Итератор, полученный с помощью end(), изначально валиден, и может стать невалидным впоследствии, в результате переаллокации, например. Невалидность итератора означает, что над ним нельзя выполнять никакие операции, в т.ч. сравнения, в т.ч. с концом. И проверить валидность итератора в общем случае нельзя, программа должна отслеживать валидность итераторов исходя из собственной логики.
Я имел ввиду под валидностью — валидность на разименовывание.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
J>>Насчет практических случаев — да, использовал многажды, никаких нареканий к эффективности, ибо CRTP. ND>Да, знаком, хотя сам таких финтов ни разу не писал. Действительно, оверхед будет нулевой. Виртуельные методы без VMT А в каких случаях использовали, Если не секрет? Только в Boost или использовали вообще как общий подход в работе с контейнерами?
вообще-то классы итераторов не обязаны иметь общего предка. поэтому vmt — не из этой оперы.
что касается CRTP — штука мощная и полезная.
У нас используется для инлайна произвольного алгоритма внутрь цикла по точкам текущего тайла, при этом базовый шаблон занимается обеспечением инфраструктуры: порядок обхода тайлов, попиксельная обработка или заливка/пропуск тайла, нужна ли проверка условия на каждую точку, блокировка нужных данных в памяти чтобы не уползли на диск (2 гб адресов хватает не всегда, поэтому ручной своп)... а сама обработки и при желании проверка условия на каждую точку -- инлайнится внутрь цикла.
Да, разбухает код — вместо вызова call_func() с указателем на функцию у нас для каждого варианта обработки получается отдельный скомпилированный цикл. Но при расчетах, занимающих минуты, а не секунды -- окупается. мегапикселей много, отдельные извращенцы запускают на гигапикселе.
где они только берут такие изображения?