Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Кодт, Вы писали: К>>Однако, мешает. sort нуждается в итераторах произвольного доступа (с дешёвой арифметикой). Конечно, можно определить её через advance — но это будет очень дорого стоить. Вместо O(n*log(n)) получим что-то кубическое. S>А это смотря какой сорт. Если обратиться к Кнуту III, то можно найти штук десять всяких сортировок. И в основном они отличаются как раз требованиями к нижележащему интерфейсу. В частности, значительная доля отведена сортировке потоков.
Моя знать. Однако, std::sort — это быстрая сортировка.
Впрочем, возможно, что после некоторой доработки напильником алгоритм быстрой сортировки вполне подойдёт и для списка.
Тем более, что для списка есть возможность обмена элементов без глубокого копирования. Указатели перебросить, и всё.
Здравствуйте, VladD2, Вы писали:
К>>А в STL — не восходящая иерархия итераторов (от простейшего input/output до крутейшего random), а деградирующая иерерхия указателей (с постепенным наложением ограничений: дешёвая арифметика, дорогая арифметика, затем запрещение декрементов, и наконец, жёсткий протокол)
VD>Это мягко говоря не итератор. Итератор — это паттерн описанный в GoF. В яве тоже есть IList и т.п. Но к итераторам это отношения не имеет.
Дык я и говорю: терминологическая путаница. Исторически очевидно, что STL iterator-ы — это аксиоматика "указатель на элементы массива". В общем, все вопросы к Степанову.
Ну а пока что — хоть горшком назови. А что? "Горшок произвольного доступа", "горшок ввода" и "горшок вывода".
Горшочек, вари!
VladD2 wrote:
> КЕ>И чем же не устраивает возможность гонять назад и т.п.? > > Несоотвествованием сути паттерна. Про бритву Окама слышал?
Слышал. Также слышал, что с острыми предметами следует обращаться осторожно — можно и порезаться
> Грамотное деление было бы следующим: > Итератор — перечисление. > Коллекция — возможность узнанать количество элементов и возможности получения их списка. > Список с произвольным доступом — произвольный доступ к элементам. > > Причем каждая последующая абстракция должна поддерживать возможности предыдущей.
Во-1х имо выделенное неверно. Ты понимаешь под итератором вообще лишь некий минимальный интерфейс итератора. Думаю возникнет меньше терминологических споров, если называть эту сущность энумератором. А итератор — более широкое понятие.
Во-2х имо логичнее такая иерархия: итератор потока — forward iterator — bidirectional iterator — random access iterator. При этом надо помнить что работать с файлами через итераторы потока не очень эффективно, да и не всегда удобно.
Не знаю, надо ли оно тебе, но на всякий случай расскажу как оно в STL.
Для итераторов потока определены определены операции ++, ==, != и разыменование, с их помощью нельзя организовать несколько обходов одного и того же потока, они могут использоваться только в однопроходных алгоритмах.
Forward итератор — то же самое, но возможно несколько проходов, пример контейнера — односвязный список.
Для bidirectional дополнительнительно определена операция --, пример контейнера — двусвязный список.
Random access iterator — по сути указатель, дополнительно определены операции +, -, <, >, [].
Итераторы более высокой категории поддерживают все операции более низких категорий.
Соответственно алгоритмы деляться на однопроходные и т.д.
Через неконстантые итераторы можно модифицировать элементы, но нельзя добавлять/удалять элементы. Это делается через методы контейнера. Иногда делается так — ссылка на контейнер инкапсулируется в итератор потока, вывод в который добавляет элементы в контейнер.
> Именно так и сделно в дотнете (IEnumerable<T>, ICollection<T>, IList<T>). К сожалению тоже не очень грамотно. Так как в интерфейсы коллекции и списка введены методы модификации, а по мне так они должны размещаться в отдельных интерфейсах.
В этом смысле подход STL грамотнее, но для организации итератора писанины надо немало, это мешает больше всего.
> это использование итераторов не по назначению. Я бы сказал извращение самого понятия итератора, так как эффективная сотрировка требует произвольного доступа, а итератор принципиально предназначен для перебора по элементу.
Неверно. Есть так называемые random access iterators, как следует из названия, поддерживающие произвольный доступ. И, вообще, видов итераторов много, хороших и разных.
> Например, в дотнете для подобных целей введено понятие коллекции, что отражается в реализации интерфейса ICollectin. У этого интерфейса есть свойство Count и метод CoppyTo с помощью которых содержимое коллекции можно скопировать в массив и произвести над этим массивом опреации тербующие последовательного доступа.
Наличие алгоритмов, работающих через итераторы, как раз позволяет избегать этих ненужных операций (копирование в массив и т.п.), если контейнер уже поддерживает произвольный доступ. Типичный пример — std::deque, для которого повторно, отдельно от std::vector, делать sort не нужно. Реализовывать сортировку для "своих" итераторов, поддерживающих произвольный доступ, тоже не надо, т.к. обобщенный алгоритм std::sort работает с любыми random access iterators.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
c-smile,
> CS>> А что означает > CS>> container.begin() + 10 > CS>> для котейнера типа list?
> ЗХ> Для list — ничего не означает. Я всего лишь привел пример. Пойнт мой был: возможность вызова функции, которая принимает начальный и конечный итераторы, но передать ей не begin и end, а что-то другое; таким образом, обработать лишь часть контейнера.
> Вот меня и инетересует это самое "а что-то другое": що ж це воно такэ, г`а?
Например, передать в <container>.erase() результат функции std::remove(). Будет работать для std::vector, std::deque etc. Будет даже работать для std::list и slist, хотя для того же std::list, ессно, есть более эффективная std::list::remove().
> Это примерно как приделать seekg с stream. Эх глянуть бы в глаз тому кто это придумал.
Кста, в Бусте уже давно маются с разделением двух концепций, совмещенных в стандартных итераторах: обход и доступ к элементу.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
VladD2,
> Вдумайся в свои слова "предоставляет концепция итератора stl". Концепция есть концепция. А реализация — реализация. Так что в СТЛ просто неудачная реализация очень правильной концепции.
В STL — именно набор концепций. Просто что-то назвать недостаточно, чтобы это что-то стало концепцией. Нужно это что-то еще и точно специфицировать. Без привязки к конкретном описанию "итератор" концепцией не является, а является просто неоднозначным словом. А вот, скажем, ForwardIterator — одна из таких концепций. Реализации — соответственно, в конкретных реализациях STL.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, VladD2, Вы писали:
CS>>Ссылка на источник в первоначальном сообщении.
VD>Для спрвки, чтобы индусам объяснить казалось бы простые и очевидные вещи приходится придумывать вот такую белеберду. Но ты-то вроещ не индус? Тогда должен понимать, что целочисленный индекст не может быть между элементами.
Влад, ты как всегда неподражаем.
Причем здесь индекс и итератор? Весь сыр бор как раз о том
что итератор не должен иметь ничего общего с индексом.
Загадка: в Java справедливо следующее:
Object a = Enum.next();
Object b = Enum.prev();
assert(a == b); // это true.
Здравствуйте, Костя Ещенко, Вы писали:
>> Итератор — перечисление.
КЕ>Во-1х имо выделенное неверно. Ты понимаешь под итератором вообще лишь некий минимальный интерфейс итератора. Думаю возникнет меньше терминологических споров, если называть эту сущность энумератором. А итератор — более широкое понятие.
КЕ>Во-2х имо логичнее такая иерархия: итератор потока — forward iterator — bidirectional iterator — random access iterator. При этом надо помнить что работать с файлами через итераторы потока не очень эффективно, да и не всегда удобно.
КЕ>Не знаю, надо ли оно тебе, но на всякий случай расскажу как оно в STL. КЕ>Для итераторов потока определены определены операции ++, ==, != и разыменование, с их помощью нельзя организовать несколько обходов одного и того же потока, они могут использоваться только в однопроходных алгоритмах. КЕ>Forward итератор — то же самое, но возможно несколько проходов, пример контейнера — односвязный список. КЕ>Для bidirectional дополнительнительно определена операция --, пример контейнера — двусвязный список. КЕ>Random access iterator — по сути указатель, дополнительно определены операции +, -, <, >, []. КЕ>Итераторы более высокой категории поддерживают все операции более низких категорий. КЕ>Соответственно алгоритмы деляться на однопроходные и т.д.
В том-то и дело, что вот такая "аксиоматика" STL-итераторов с головой выдаёт в них указатели.
Только строится иерархия не от меньшего к большему, а наоборот:
1) указатель на элементы некоего обобщённого массива — random access tranklukator, над которым определены
— разыменование (очевидно)
— эквивалентность
— адресная арифметика
2) указатель без адресной арифметики — bidirectional tranklukator
— из всей арифметики оставлены только автоинкремент/автодекремент
3) указатель с односторонним инкрементом — forward tranklukator
— оставили только автоинкремент
4) указатель, который совместим с протоколом чтения из последовательного устройства — input tranklukator
— наложили ряд ограничений; использование вне протокола — undefined.
5) указатель, который совместим с протоколом записи — output tranklukator
— наложили другие ограничения
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>Кста, в Бусте уже давно маются с разделением двух концепций, совмещенных в стандартных итераторах: обход и доступ к элементу.
Можно ли малой кровью разделить два этих явления — и переключаться между ними в своё удовольствие?
Например, пусть у нас есть Accessor — сущность для доступа, и Generator — сущность для обхода.
some_generator g(some_begin, some_end);
some_accessor a;
...
while(!g.eof())
{
a = g.peek(); // не меняет состояние генератора
a.put(some_value()); // я сознательно не пишу здесь операторы, чтобы не проводить лишних аналогий
a = g.read(); // меняет состояние генератора - тот уезжает вперёд, оставляя за собой Accessor
some_data d = a.get();
...
some_generator h(some_begin, a); // новый генератор: от начала до этого элемента исключительно
...
}
При этом, если генератор определён над потоком (или вычисляемой последовательностью), то возвращаемый аксессор не может быть приведён к какому-либо генератору (кроме генератора одноэлементной последовательности — да и та, скорее всего, будет стремительно инвалидирована).
А если генератор — над хранимой последовательностью, то по его аксессорам можно построить новые генераторы.
(Причём разные!)
Здравствуйте, c-smile, Вы писали:
CS>В D есть понятие slice:
.... CS>Т.е. с точки зрения D массив и диапазон это одно и то же. CS>Такие решения возможны по всей видимости только "под GC". CS>В принципе можно и на C++ что-то на эту тему придумать с подсчетом ссылок но CS>думаю коряво получится.
К слову сказать, я как раз вчера такое делал для своего контейнерообразного класса. Интересно, что в поисках удачного внешнего интерфейса наткнулся на механизм "срезов" (slice) у std::valarray. Как говаривал Кодт, "все украдено до нас"
Здравствуйте, VladD2, Вы писали:
MS>> Я вижу здесь скрытую проблему. Перебор всех элементов в любом контейнере должен иметь сложность O(N). А из подобной записи это совсем не очевидно.
VD>1. Никто ничего никому не должен. Например, при переборе элементов дерева O(n) получить сложно (хотя в принципе можно, как например в BTree+).
Э... в двоичном дереве это тоже O(n). Правда, каждый отдельный переход занимает от O(1) до O(log n)...
VladD2,
> КЕ>И чем же не устраивает возможность гонять назад и т.п.? > > Несоотвествованием сути паттерна. Про бритву Окама слышал?
Сути паттерна GoF Iterator (*) не соответствует то, что ты написал ниже:
> Грамотное деление было бы следующим: > Итератор — перечисление. > Коллекция — возможность узнанать количество элементов и возможности получения их списка. > Список с произвольным доступом — произвольный доступ к элементам. > > Причем каждая последующая абстракция должна поддерживать возможности предыдущей.
Итератор и коллекция — понятия разного порядка: итераторы используются для доступа к коллекции, и вводятся как раз для того, чтоб изолировать доступ к содержимому коллекции от конкретного типа коллекции. Соответственно, ставить в один ряд итераторы и коллекции, и говорить о порядке абстракций в этом ряду совершенно бессмысленно. У "списка с произвольным доступом" (что само по себе оксюморон) в случае применения паттерна Iterator будут свои итераторы.
Пока что к итераторам (особенно к тем, что с произвольным доступом), насколько я вижу, есть одна претензия по существу — название. Возможно, более удачным было бы использование термина Cursor, чтобы не смущать пользователей ассоциациями: "iterator -> перебор". Но, имхо, по отношению к самой концепции название уже вторично.
> Именно так и сделно в дотнете (IEnumerable<T>, ICollection<T>, IList<T>).
IEnumerable != iterator. Итераторам более-менее соответствует IEnumerator, только с той разницей, что в STL итераторы поддерживают большее количество возможностей.
Кодт,
> S>А это смотря какой сорт. Если обратиться к Кнуту III, то можно найти штук десять всяких сортировок. И в основном они отличаются как раз требованиями к нижележащему интерфейсу. В частности, значительная доля отведена сортировке потоков.
> Моя знать. Однако, std::sort — это быстрая сортировка.
Не обязательно.
> Впрочем, возможно, что после некоторой доработки напильником алгоритм быстрой сортировки вполне подойдёт и для списка.
Что интересно, в новой Dinkumware std::sort применима к std::list. Естественно, с другими гарантиями сложности.
> Тем более, что для списка есть возможность обмена элементов без глубокого копирования. Указатели перебросить, и всё.
Для этого есть std::list::sort
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>У "списка с произвольным доступом" (что само по себе оксюморон) в случае применения паттерна Iterator будут свои итераторы.
Если уж совсем буквоедствовать, то это как раз нормально. Пишем на листочке список продуктов для покупки — он имеет произвольный доступ. В программировании это соответствует массиву. Так что само по себе понятие "список" не указывет, какие методы доступа к нему применимы. Вектор тоже является списком. Другое дело — сложившиеся традиции. Для простоты под понятием "список" подразумевается именно "linked list с последовательным доступом" и ничто другое. С учетом сложившихся традиций, "список с произвольным доступом" действительно является оксюмороном, а вообще — нет. Но это хорошая традиция, достойная уважения. Неуважение к традициям приводит к образованию каких-то совсем уж нелепых сущностей, типа ArrayList. Судя по названию (с учетом традиций) это должен быть связный список массивов, а не массив, в который добавлен IList.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, Кодт, Вы писали:
К>В том-то и дело, что вот такая "аксиоматика" STL-итераторов с головой выдаёт в них указатели.
Это плохо?
К>Только строится иерархия не от меньшего к большему, а наоборот:
К>1) указатель на элементы некоего обобщённого массива — random access tranklukator, над которым определены К>- разыменование (очевидно) К>- эквивалентность К>- адресная арифметика К>2) указатель без адресной арифметики — bidirectional tranklukator К>- из всей арифметики оставлены только автоинкремент/автодекремент К>3) указатель с односторонним инкрементом — forward tranklukator К>- оставили только автоинкремент К>4) указатель, который совместим с протоколом чтения из последовательного устройства — input tranklukator К>- наложили ряд ограничений; использование вне протокола — undefined. К>5) указатель, который совместим с протоколом записи — output tranklukator К>- наложили другие ограничения
McSeem2,
> Воот! random access iterator — это pointer и есть. Надо было так и назвать его — pointer, а не итератор. При этом поинтер обладает всеми свойствами итератора, но итератор не обладает некоторыми свойствами поинтера. И всех делов. Сортировка требует именно поинтеров. С итераторами она работать не умеет.
Как от того, что мы бы переименовали текущие random access iterators в pointers, а текущие forward iterators в iterators изменился бы интерфейс шаблона std::sort(), если не принимать в учет названия параметров шаблона?
На всякий случай напоминаю, что изменить его на такой:
template<class T>
void sort(T* first, T* last);
нельзя из-за того, что в других контейнерах, не в std::vector, итераторы (pardon my French) указателями быть не могут; например, std::deque.
> При этом вектор имеет поинтеры, а список — итераторы.
Пока что я не вижу за этим ничего, кроме смены названий...
> И никаких полисей.
В стандартной std::sort() никакие policies не нужны, т.к., перефразируя, ни с чем, кроме random access iterators она работать не умеет. (Предполагаемое) их наличие в реализации Dinkumware означает, что там в виде расширения решили реализовать std::sort() таким образом, чтоб она умела работать не только с random access iterators, но и с forward iterators.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Костя Ещенко, Вы писали:
КЕ>>И чем же не устраивает возможность гонять назад и т.п.?
VD>Несоотвествованием сути паттерна. Про бритву Окама слышал?
VD>Грамотное деление было бы следующим: VD>Итератор — перечисление. VD>Коллекция — возможность узнанать количество элементов и возможности получения их списка. VD>Список с произвольным доступом — произвольный доступ к элементам.
VD>Причем каждая последующая абстракция должна поддерживать возможности предыдущей.
VD>Именно так и сделно в дотнете (IEnumerable<T>, ICollection<T>, IList<T>). К сожалению тоже не очень грамотно. Так как в интерфейсы коллекции и списка введены методы модификации, а по мне так они должны размещаться в отдельных интерфейсах.
Почему-то ты не можешь понять различие в целях дизайна STL и библиотеки коллекций .NET. В STL первоочередной задачей стояло разделение коллекций и алгоритмов. Отсюда и вытекает дизайн STL-ных итераторов, который ты почему-то считаешь убогим. Тем не менее свою задачу STL итераторы выполняют прекрасно. Адгоритмы существуют отдельно, коллекции отдельно, а итераторы позволяют им взаимодействовать через loose coupling.
В .NET цели были совершенно другие. Там итераторы (точнее энумераторы) создавались для того, чтобы можно было пробегать по коллекции от начала до конца в одном направлении желательно с применением foreach. Эта цель достигнута. Foreach работает превосходно. К сожалению не для чего другого энумераторы не подходят. Алгоритмы и коллекции жестко связаны. Но этого достаточно для большинства, которые кстати пришли на .NET c Java или с VB, где положение не лучше.
Здравствуйте, McSeem2, Вы писали:
MS>Здравствуйте, Шахтер, Вы писали:
Ш>>Ну почему же. Это просто разные способы применения. Указатель, скажем, позволяет и итерировать, и произвольный доступ. Причем естественным образом.
Ш>>Дело не в стремлении впихнуть все сущности в одно понятие, а в природе вещей. Голый указатель обладает набором определённых свойств -- вот эти свойства и были аксиоматизированы. Получился randon access iterator.
MS>Воот! random access iterator — это pointer и есть. Надо было так и назвать его — pointer, а не итератор.
Ну что поделаешь. Мы живем в эпоху постмодернизма. Афро-американцы, random access iterator ы, список продолжи сам. И никого не смущает, что нет такого континента -- Афро-Америка.
Здравствуйте, c-smile, Вы писали:
CS>Здравствуйте, Шахтер, Вы писали:
CS>Я отношу фразу "random access iterator" к разряду хохм CS>типа "старый опытный камикадзе"
CS>Итератор — это итератор. Random access это нечто абсолютно противоположное.
Я думаю, не противоположное, а ортогональное. Именно поэтому голый указатель обладает свойствами и итератора, и random access.
CS>--------------------------- CS>В D есть понятие slice:
CS>
CS>char[] range = "Hello world";
CS>foreach(char c; range) { writef("%c", c); }
CS>range = range[0..5]; // slicing
CS>foreach(char c; range) { writef("%c", c); } // та же самая операция но уже над slice
CS>
CS>Т.е. с точки зрения D массив и диапазон это одно и то же.
Просто в D диапазон удерживает массив, из которого он образовался.
CS>Такие решения возможны по всей видимости только "под GC". CS>В принципе можно и на C++ что-то на эту тему придумать с подсчетом ссылок но CS>думаю коряво получится.
Ну почему, сделать можно. Вопрос только -- нужно ли.
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>Как от того, что мы бы переименовали текущие random access iterators в pointers, а текущие forward iterators в iterators изменился бы интерфейс шаблона std::sort(), если не принимать в учет названия параметров шаблона? ПК>
ПК>нельзя из-за того, что в других контейнерах, не в std::vector, итераторы (pardon my French) указателями быть не могут; например, std::deque.
Ну вообще-то, я имел в виду не T*, а некий std::deque<>::pointer, который отличается от T*. Но с этой точки зрения ты прав — дело лишь в названии. Pointer — тоже не вполне удачно, признаю. Наверное Степанов тоже не мог придумать лучшего названия и оставил так.
Что же касается семантики вызова sort, то она должна быть еще проще:
И у коллекции должно быть два метода — operator[] и size(). Сортировка в диапазоне реализуется с помощью простейшего адаптора, сортировка голого массива — с помощью другого простейшего адаптора.
Но! Здесь я сам поймался на собственном словоблудии
У std::map имеется вышеуказанный интерфейс. Вопрос — что случится, если мы дадим его функции сортировки?
В общем, со всех сторон засада...
ПК>В стандартной std::sort() никакие policies не нужны, т.к., перефразируя, ни с чем, кроме random access iterators она работать не умеет. (Предполагаемое) их наличие в реализации Dinkumware означает, что там в виде расширения решили реализовать std::sort() таким образом, чтоб она умела работать не только с random access iterators, но и с forward iterators.
Вот это уже плохо. Для списков требуется отдельные методы сортировки, с отдельными названиями. Ну не надо все валить в одну кучу — имеется опасность самовозгорания.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Перекуём баги на фичи!
