Здравствуйте, McSeem2, Вы писали:
MS>Ну вообще-то, я имел в виду не T*, а некий std::deque<>::pointer, который отличается от T*. Но с этой точки зрения ты прав — дело лишь в названии. Pointer — тоже не вполне удачно, признаю. Наверное Степанов тоже не мог придумать лучшего названия и оставил так.
Ну, а чего тут думать, вон Кодт уже предложил
Answer:
An iterator is a union of two theories. The first theory is a theory of name (handle, cookie, address). A name is something that points to something else. (operator*). We call it Trivial Iterator theory in our site. In addition to the dereferencing, it has equality defined that satisfies the following axiom:
i == j iff &*i == &*j
That is, two iterators are equal if and only if they point to the same object. (Equality, of course, needs to satisfy all the standard axioms.) The second theory is the theory of successor operation (++i) with its refinements: successor — predcessor (++ and --) and addition (++, --, + and -) with the standard axioms. And, of course, pointer is just a model of random access iterator.
... << RSDN@Home 1.1.4 beta 5 rev. 395>> {WinAmp: The Rasmus — In The Shadows}
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>В STL — именно набор концепций. Просто что-то назвать недостаточно, чтобы это что-то стало концепцией. Нужно это что-то еще и точно специфицировать. Без привязки к конкретном описанию "итератор" концепцией не является, а является просто неоднозначным словом. А вот, скажем, ForwardIterator — одна из таких концепций. Реализации — соответственно, в конкретных реализациях STL.
Пашь, McSeem2 павильно сказал. Само название "итератор" подразумевает последовательный доступ (перебор). А итератор произвольного доступа — это глупость.
Как в прочем глупо использовать какие-то навороченные конструкции для произвольного доступа. Для этого достаточно одного оператора/метода и свойства/метода для того чтобы узнать длинну списка.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Костя Ещенко, Вы писали:
КЕ>Во-1х имо выделенное неверно. Ты понимаешь под итератором вообще лишь некий минимальный интерфейс итератора. Думаю возникнет меньше терминологических споров, если называть эту сущность энумератором. А итератор — более широкое понятие.
Итератор — это давно и хорошо известный паттерн проектирования. Называть его можно по разному суть от этого не меняется. А вот в С++ этот термин применен некорректно. Как впрочем и в C# 2.0. Там зачем-то итератором назвали реализацию того что в языке называется энумератором.
КЕ>Во-2х имо логичнее такая иерархия: итератор потока — forward iterator — bidirectional iterator — random access iterator.
Вот это и есть извращение. Ты iteration — это перебор, повторение и т.п. И само понятие перебора не допускает произвольный доступ.
Что да двунаправленных итераторов и т.п. тут не все так просто. Но можно точно сказать, что для самого паттерна и его применения это все не нужно.
КЕ> При этом надо помнить что работать с файлами через итераторы потока не очень эффективно, да и не всегда удобно.
Эффективность тут вообще не причем. И вообще она в основном определяется алгоритмами и их реализацией.
>> Именно так и сделно в дотнете (IEnumerable<T>, ICollection<T>, IList<T>). К сожалению тоже не очень грамотно. Так как в интерфейсы коллекции и списка введены методы модификации, а по мне так они должны размещаться в отдельных интерфейсах.
КЕ>В этом смысле подход STL грамотнее, но для организации итератора писанины надо немало, это мешает больше всего.
По мне так, СТЛ — это просто верх несуразности. По крайней мере с терминологией в этой библиотеке полный абзац.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Костя Ещенко, Вы писали:
КЕ>Здравствуйте, Кодт, Вы писали:
К>>В том-то и дело, что вот такая "аксиоматика" STL-итераторов с головой выдаёт в них указатели.
КЕ>Это плохо?
Естественно. Иначе давай называть телефон патефонном с возможностью разговора на растонянии.
Да и сама концепия довольно непонятна, громоздка и требует кучи лишних действий (неудобна).
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>VladD2,
>> КЕ>И чем же не устраивает возможность гонять назад и т.п.? >> >> Несоотвествованием сути паттерна. Про бритву Окама слышал?
ПК>Сути паттерна GoF Iterator (*) не соответствует то, что ты написал ниже:
А с чего ты взял, что что-то кроме самого итератора должно соотвествовать этому паттерну? Речь шла о том, что то что названо в СТЛ итератором нужно было бы разбить на несколько других понятий. Только и всего.
ПК>Итератор и коллекция — понятия разного порядка...
Очередное докапывание к совершенно посторонним словам. Причем тут итератор и коллекция? Кто-то называет коллекцию итератором?
ПК>: итераторы используются для доступа к коллекции,
Да.
ПК> и вводятся как раз для того, чтоб изолировать доступ к содержимому коллекции от конкретного типа коллекции.
Нет. Итератор обобщает процедуру перебора элементов. А вот создатель СТЛ просто не смог подобрать подходящую терминалогию.
ПК> Соответственно, ставить в один ряд итераторы и коллекции, и говорить о порядке абстракций в этом ряду совершенно бессмысленно.
Бессмысленно называть указатели или еще чего-то там итераторами. А создать иерархию абстракций повзволяющих оболбщенно работать с разничными списками очень даже осмысленно.
ПК> У "списка с произвольным доступом" (что само по себе оксюморон) в случае применения паттерна Iterator будут свои итераторы.
Да, Пашь, у тебя проблемы с терминологией не хуже чем у Степанова.
Как раз список с прозвольным доступом это более чем нормально. Видимо из-за передозировки С++.
In computer science, a list is an abstract concept denoting an ordered collection of fixed-length entities. In practice, any list is either an array or a linked list of some sort.
Список это абстракция. Массивы и коллекции предоставляющие эффективный произвольный доступ тоже являются частными случаями (реализациями) списка.
ПК>Пока что к итераторам (особенно к тем, что с произвольным доступом), насколько я вижу, есть одна претензия по существу — название.
Я бы сказал претензия к неверному использованию термина в СТЛ. Хотя конечно есть претензии и к самой сущности. По мне так не удачная идея. И громоздко, и неудобно.
ПК> Возможно, более удачным было бы использование термина Cursor, чтобы не смущать пользователей ассоциациями: "iterator -> перебор". Но, имхо, по отношению к самой концепции название уже вторично.
Курсор тоже не подходит для "итераторов с произвольным доступом". В этом вопросе я согласен с Кодтом. Логичнее всего было назвать это дело указателелем. Но был бы конфликт со встроенными в язык указателями.
>> Именно так и сделно в дотнете (IEnumerable<T>, ICollection<T>, IList<T>).
ПК>IEnumerable != iterator. Итераторам более-менее соответствует IEnumerator, только с той разницей, что в STL итераторы поддерживают большее количество возможностей.
Я так понял ссылка должна подчеркнуть мое незнание в данном вопросе? Ты лучше сам по ним сходи и почитай описание. Вот то что называется Aggregate и представленно интерфейсом IEnumerable в дотнете.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, McSeem2, Вы писали:
MS>Другое дело — сложившиеся традиции.
Точнее дурные традиции сложившиеся в некоторых кругах.
MS> Для простоты под понятием "список" подразумевается именно "linked list с последовательным доступом" и ничто другое.
Почему-то такое предположение больше делают С-шники. Я как-то не слышал, чтобы обычные люди или математики делали подобные предположения.
MS>Но это хорошая традиция, достойная уважения.
Да, точно. Вот в некоторых кругах есть такие хорошие традиции говорить "ложить" вместо "класть", или "шофера" вместо "шоферы". И это хорошо...
MS>Неуважение к традициям приводит к образованию каких-то совсем уж нелепых сущностей, типа ArrayList. Судя по названию (с учетом традиций) это должен быть связный список массивов, а не массив, в который добавлен IList.
Ненадо придумывать. Традиции о которых ты говоришь — это элементарная безграмотность. Формирование имени класса путем склиивания реализации и абстракции примененная в ArrayList тоже не замечательная идея, но в не хотя бы есть логика. По крайней мере по именам ArrayList и LinkedList можно четко понять какими особенностями обладают эти реализации списка. Наверно более верно было бы назвать эти классы как-то вроде ListImplementationOnArray. Но жить с тикими именами как-то не хочется. Во втором фрэймворке орлы из МС решили разывать реализации обобщенных коллекций путем отбрасывания "I" от имени базового интерфейса. Но это тоже не хороший выход, так как название становится мало гворящим. А сочетание List<T> и LinkedList<T> выглядит вообще странно.
Мне кажется логично было бы развать классы просто DinamicArray и LinkedList. А то что они реализуют некие обстракции проистикало бы просто из их сути. Для меня лично очевидно, что массив реализует интерфейс IList. Но видимо орлы из МС решили, что это может запутать новичков.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, alexeiz, Вы писали:
A>Почему-то ты не можешь понять различие в целях дизайна STL и библиотеки коллекций .NET.
Потому что дизайн базовых коллекций сделанный грамотно прекрасно решает и "задачи СТЛ". Весь смысль обобщений заключается в том, чтобы позволить работать с некоторым классом объектов полиморфно.
A> В STL первоочередной задачей стояло разделение коллекций и алгоритмов. Отсюда и вытекает дизайн STL-ных итераторов, который ты почему-то считаешь убогим. Тем не менее свою задачу STL итераторы выполняют прекрасно. Адгоритмы существуют отдельно, коллекции отдельно, а итераторы позволяют им взаимодействовать через loose coupling.
Слабая связанность и т.п. это уже отдельный вопрос. Здесь же обсуждается совершенно бездарная терминология СТЛ и довольно неудобное использование этих "итераторов".
A>В .NET цели были совершенно другие. Там итераторы (точнее энумераторы) создавались для того, чтобы можно было пробегать по коллекции от начала до конца в одном направлении желательно с применением foreach. Эта цель достигнута. Foreach работает превосходно. К сожалению не для чего другого энумераторы не подходят. Алгоритмы и коллекции жестко связаны.
А, ну, ясно. "Священную корову руками не трогать." Почитай GoF. Думаю тебя удивят некоторые вещи.
A> Но этого достаточно для большинства, которые кстати пришли на .NET c Java или с VB, где положение не лучше.
Я вот пришел с С++. И надо признать, и как-то не разделяют твоего мнения. Как впрочем и многие другие пришедшие с плюсов.
A>На лицо две разные цели и два разных дизайна.
Нет никаких разных целей. Есть желание притянуть что-нить за уши и крайняя предвзятость.
Здравствуйте, Кодт, Вы писали:
К>Моя знать. Однако, std::sort — это быстрая сортировка.
Не совсем. Многие реализации гибридные. А в стандарте вообще алгоритм не указан.
К>Впрочем, возможно, что после некоторой доработки напильником алгоритм быстрой сортировки вполне подойдёт и для списка.
Если только у напильника снять ручку и острием тыкать начать.
К>Тем более, что для списка есть возможность обмена элементов без глубокого копирования. Указатели перебросить, и всё.
1. Не у списка, а у связанного списка.
2. Не пройдет. Или ты скопируешь список в массив и далее применишь исходный алгоритм. Или на жаждом шаке рекурсии тебе прийдется создавать попию подсписка. Вот пример подобной организации на Шарпе:
static IEnumerable<T> Sort2<T>(IEnumerable<T> enumerable)
where T : IComparable<T>
{
// Пытаемся получить медиану для дальнейшего стравнения.
// Так как произвольного доступа к элементам нет, то приходится
// брать первый элемент. Это приведет к плохой производительности
// на отсортированных массивах.
IEnumerator<T> iterator = enumerable.GetEnumerator();
// Если список пуст, то и делать нечего.if (!iterator.MoveNext())
yield break;
T median = iterator.Current; // получили элемент для сравнения
// Фильтруем список отбирая элементы меньшие median-а.
// Для получившегося списка выполняем сортировку (рекурсивно).
// Перебераем получившися (отсортированный) подсписок и возвращаем
// его элементы.foreach (T value in Sort1(Filter(enumerable,
delegate(T item) { return item.CompareTo(median) < 0; })))
yield return value;
// Делам тоже самое но отфильтровываем элеметы большие или равные медиане.foreach (T value in Sort1(Filter(enumerable,
delegate(T item) { return item.CompareTo(median) >= 0; })))
yield return value;
}
// Эта функция создает список в который попадают элементы удовлетворяющие предикату.
// Попросту говоря она отфильтровывает все элементы для которых predicate() вовращает true.static IEnumerable<T> Filter<T>(IEnumerable<T> enumerable, Predicate<T> predicate)
{
foreach (T value in enumerable)
if (predicate(value))
yield return value;
}
Формально это тоже быстрая сортировка (если закрыть глаза на то, что Filter<T> делает два прохода по списку, но это можно устранить). Однако по сравнению с императивной реализацией скорость получится хреновенькая. А то что медиана берется не из середиты еще и ухудшает скоростные характеристики для уже сортированных списков.
Вот, ради любьви к искуству сделал эксперемент сравнивающий скорость классической быстрой сортировки и быстрой сортировки на списках:
//#define USE_ITERATIR_SORTusing System;
using System.Collections.Generic;
class Program
{
const int SecLen = 1000000;
static void Main(string[] args)
{
List<int> result = new List<int>(SecLen);
int start = Environment.TickCount;
#if USE_ITERATIR_SORT
foreach (int i in Sort1(Generator()))
result.Add(i);
#else
result.AddRange(Generator());
result.Sort();
#endif
Console.WriteLine("Time is " + (Environment.TickCount - start));
int sum = 0;
result.ForEach(delegate(int elem) { sum += elem; });
Console.WriteLine(sum);
}
// Генерирует последовательность случайных числе.
// Возвращает итератор который используется для тестов.static IEnumerable<int> Generator()
{
Random random = new Random(123456);
for (int i = 0; i < SecLen; i++)
yield return random.Next();
}
static IEnumerable<T> Sort1<T>(IEnumerable<T> enumerable)
where T : IComparable<T>
{
IEnumerator<T> iterator = enumerable.GetEnumerator();
if (!iterator.MoveNext())
yield break;
T median = iterator.Current;
List<T> left = new List<T>();
List<T> right = new List<T>();
while (iterator.MoveNext())
{
T value = iterator.Current;
if (value.CompareTo(median) < 0)
left.Add(value);
else
right.Add(value);
}
foreach (T value in Sort1(left))
yield return value;
yield return median;
foreach (T value in Sort1(right))
yield return value;
}
static IEnumerable<T> Sort2<T>(IEnumerable<T> enumerable)
where T : IComparable<T>
{
IEnumerator<T> iterator = enumerable.GetEnumerator();
if (!iterator.MoveNext())
yield break;
T median = iterator.Current;
foreach (T value in Sort1(Filter(enumerable,
delegate(T item) { return item.CompareTo(median) < 0; })))
yield return value;
foreach (T value in Sort1(Filter(enumerable,
delegate(T item) { return item.CompareTo(median) >= 0; })))
yield return value;
}
static IEnumerable<T> Filter<T>(IEnumerable<T> enumerable, Predicate<T> predicate)
{
foreach (T value in enumerable)
if (predicate(value))
yield return value;
}
}
В коде два варианта. Один более "быстрый". красивый (совсем функциональный ).
Вот результат "быстрой сортировки на списках" первый вариант:
Time is 4812
-14996129
Тоже самое но второй вариант:
Time is 4907
-14996129
А вот классической:
Time is 187
-14996129
Думаю, все ясно. Хотя надо признать, что для 1 000 000 показатель очень неплохой. Так что для очень многих задач он с успехом пройдет.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Мы отклонились от темы
К>>Моя знать. Однако, std::sort — это быстрая сортировка.
VD>Не совсем. Многие реализации гибридные. А в стандарте вообще алгоритм не указан.
Угу...
К>>Впрочем, возможно, что после некоторой доработки напильником алгоритм быстрой сортировки вполне подойдёт и для списка.
VD>Если только у напильника снять ручку и острием тыкать начать.
К>>Тем более, что для списка есть возможность обмена элементов без глубокого копирования. Указатели перебросить, и всё.
VD>1. Не у списка, а у связанного списка. VD>2. Не пройдет. Или ты скопируешь список в массив и далее применишь исходный алгоритм. Или на жаждом шаке рекурсии тебе прийдется создавать попию подсписка. Вот пример подобной организации на Шарпе:
Почему же? Зачем мне создавать подсписки?
Собственно быстрая сортировка не требует произвольного доступа.
Подсчёт длины интервалов [b,m), [m+1,e) — делается на стадии разбиения и не несёт дополнительных накладных расходов.
Да и известные мне оптимизации — разворот рекурсии, эффективные сортировки коротких массивов, выбор точки разделителя как средней между минимумом и максимумом — не нуждаются в адресной арифметике; вполне можно обойтись ++.
Другое дело, что для двусвязных списков есть более эффективные алгоритмы.
Здравствуйте, c-smile, Вы писали:
CS>Причем здесь индекс и итератор? Весь сыр бор как раз о том CS>что итератор не должен иметь ничего общего с индексом.
Общего не должен, но при реализации индекс там появится с очень большой вероятностью. Мы же ведь не про сфероконей речь ведем?
CS>Загадка: в Java справедливо следующее:
CS>Object a = Enum.next(); CS>Object b = Enum.prev(); CS>assert(a == b); // это true.
CS>Так где находился Enum после next?
Перешел вперед. Вернулся назад. Что же ты еще хотел получить? Хотя по мне так prev совершенно лишний.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VladD2,
>>> КЕ>И чем же не устраивает возможность гонять назад и т.п.?
>>> Несоотвествованием сути паттерна. Про бритву Окама слышал?
> ПК>Сути паттерна GoF Iterator (*) не соответствует то, что ты написал ниже:
> А с чего ты взял, что что-то кроме самого итератора должно соотвествовать этому паттерну?
Я ожидаю от собеседника, что начав словами: "Несоотвествованием сути паттерна. <...> Грамотное деление было бы следующим: <...>" — он продолжит о сути паттерна, а не о том, что в Киеве дядька.
> ПК> Соответственно, ставить в один ряд итераторы и коллекции, и говорить о порядке абстракций в этом ряду совершенно бессмысленно. > > Бессмысленно называть указатели или еще чего-то там итераторами. А создать иерархию абстракций повзволяющих оболбщенно работать с разничными списками очень даже осмысленно.
Это и есть иерархия итераторов в STL. А по поводу названия... На тот момент, когда Степанов вводил свою терминологию (1984-1988, 1993), книжки Design Patterns by GoF (1995) еще не было. Соответственно, говорить о правильности терминологии можно весьма условно. Какая из двух терминологий "правильнее" — исключительно вопрос вкуса. О чем, как известно, не спорят.
> ПК> У "списка с произвольным доступом" (что само по себе оксюморон) в случае применения паттерна Iterator будут свои итераторы. > > Да, Пашь, у тебя проблемы с терминологией не хуже чем у Степанова. > Как раз список с прозвольным доступом это более чем нормально. Видимо из-за передозировки С++.
Восстанавливаем контекст:
Грамотное деление было бы следующим:
Итератор — перечисление.
Коллекция — возможность узнанать количество элементов и возможности получения их списка.
Список с произвольным доступом — произвольный доступ к элементам.
Т.е. список вводится сразу именно как список с произвольным доступом, а не вводится список вообще, т.е. с последовательным доступом, а потом уже, как разновидность, "список с произвольным доступом". Вот это выделение первичного назначения списка как контейнера, обеспечивающего произвольный доступ, и есть абсурд, о котором я упомянул.
> Список это абстракция.
Абстракция, или нет — несущественно. Речь о том, что только часть списков обеспечивает произвольный доступ, соответственно, в базовом интерфейсе списка произвольного доступа быть не может, только в одной из разновидностей.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
VladD2,
> A> Но этого достаточно для большинства, которые кстати пришли на .NET c Java или с VB, где положение не лучше. > > Я вот пришел с С++.
Ты не считаешься, т.к. STL не использовал.
> A>На лицо две разные цели и два разных дизайна. > > Нет никаких разных целей. Есть желание притянуть что-нить за уши и крайняя предвзятость.
VladD2,
> при переборе элементов дерева O(n) получить сложно (хотя в принципе можно, как например в BTree+).
O(n) при переборе элементов любого дерева (если порядок обхода не важен) получается элементарно, если в качестве представления выбрать классический список смежности.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, VladD2, Вы писали:
К>>Э... в двоичном дереве это тоже O(n). Правда, каждый отдельный переход занимает от O(1) до O(log n)... VD>И как же у тебя при переходе с O(log n) получается сумарная O(n)?
Дык просто.
Полный обход любого дерева состоит в том, что по каждому ребру совершается два перехода — вниз и вверх.
Количество рёбер равно количеству узлов — 1.
Итого, полное время обхода — 2n-2 переходов по рёбрам.
Сюда ещё нужно прибавить время на операции NextSibling (следующий ребёнок того же родителя, что и данный узел).
В случае двоичных деревьев — каждая такая операция занимает O(1):
NextSibling(node) = (node->parent->left == node) ? node->parent->right : NULL
В случае, если множество дочерних узлов представлено связным списком, то тоже O(1)
NextSibling(node) = node->next
Если в узле есть массив дочерних узлов размером K, отсортированный каким-то способом, то O(log K) (например, B-деревья).
А если не отсортированный — то O(K).
При этом, для сбалансированного дерева (двоичного или нет — неважно) переход от крайне правого листа левого поддерева к следующему узлу — крайне левому листу правого поддерева — требует подъёма до корня и спуска вниз. Итого, 2*log2(n).
У КЧ- и AVL-деревьев коэффициенты будут отличаться, но это всё равно нечто логарифическое.
Худший случай несбалансированного дерева: путь длиной n-1 рёбер.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, alexeiz, Вы писали:
A>>Почему-то ты не можешь понять различие в целях дизайна STL и библиотеки коллекций .NET.
VD>Потому что дизайн базовых коллекций сделанный грамотно прекрасно решает и "задачи СТЛ". Весь смысль обобщений заключается в том, чтобы позволить работать с некоторым классом объектов полиморфно.
A>> В STL первоочередной задачей стояло разделение коллекций и алгоритмов. Отсюда и вытекает дизайн STL-ных итераторов, который ты почему-то считаешь убогим. Тем не менее свою задачу STL итераторы выполняют прекрасно. Адгоритмы существуют отдельно, коллекции отдельно, а итераторы позволяют им взаимодействовать через loose coupling.
VD>Слабая связанность и т.п. это уже отдельный вопрос. Здесь же обсуждается совершенно бездарная терминология СТЛ и довольно неудобное использование этих "итераторов".
Что-то я не вижу, где обсуждается неудобное использование. Наоборот, по удобству использованию ничего и рядом не стоит кроме простого указателя. А если ты о сложности создания standard conforming итераторов, то это совсем другой вопрос, который не надо путать с использованием.
Кстати, слабая связанность — это не отдельный вопрос, а основная задача дизайна STL, без понимания которой очень трудно понять суть многих вещей в этой библиотеке.
А вот по терминологии у тебя задвиг, это точно. Внушил себе, что итераторы могут быть только одного типа. Не видишь, что набор задач, в которых могут быть применены итераторы, гораздо шире, чем простое перечисление.
A>>В .NET цели были совершенно другие. Там итераторы (точнее энумераторы) создавались для того, чтобы можно было пробегать по коллекции от начала до конца в одном направлении желательно с применением foreach. Эта цель достигнута. Foreach работает превосходно. К сожалению не для чего другого энумераторы не подходят. Алгоритмы и коллекции жестко связаны.
VD>А, ну, ясно. "Священную корову руками не трогать." Почитай GoF. Думаю тебя удивят некоторые вещи.
Спасибо, "учитель"!
A>> Но этого достаточно для большинства, которые кстати пришли на .NET c Java или с VB, где положение не лучше.
VD>Я вот пришел с С++. И надо признать, и как-то не разделяют твоего мнения. Как впрочем и многие другие пришедшие с плюсов.
C++ допускает программирование на разных уровнях. Можно не понимать концепций STL и все равно писать программы на C++.
A>>На лицо две разные цели и два разных дизайна.
VD>Нет никаких разных целей. Есть желание притянуть что-нить за уши и крайняя предвзятость.
Есть цели. У каждой библиотеки есть design goals. Другое дело, если ты не знаком с целями дизайна STL.
VD>Что до алгоритмов, то зайди на http://www.wintellect.com/powercollections/... погляди.
И что? Вот пример: Algorithms.Fill<T>(IList<T>,int,int,T); Типичный случай алгоритма привязанного к коллекции. Что мне нужен произвольный доступ к элементам коллекции, чтобы запольнить её? Нужна возможность добавлять элементы в любое место, удалять, искать элементы? Нет мне нужен только forward iterator. Додумай на досуге, почему std::fill я могу применить практически к чему угодно (реализовать forward iterator, если такого нет, не стоит никакого труда), а для Algorithms.Fill мне подходит только IList подобная коллекция.
Здравствуйте, Кодт, Вы писали:
К>Почему же? Зачем мне создавать подсписки? К>Собственно быстрая сортировка не требует произвольного доступа.
Не батенька. Это у тебя очередной пример использования указателей. Да еще и с явными ошибками (хотя бы ++i два раза за проход вызваются). А все эти (m+1) и обновления значений в итераторах...
К тому же ты попробуй ради хохмы отлать это дело и сравни скорость с классической быстрой сортировкой.
К>Да и известные мне оптимизации — разворот рекурсии,
Это не оптимизация. Те времена прошли. Надеюсь на всегда.
К> эффективные сортировки коротких массивов,
Тоже бабка на двое сказала. Я как-то развлекался с этим делом. И основной выигрыш был в оптимизации и инлайнинге алгоритмов сравнения элементов. А все оптимизации для коротких списков ничего не давали. Тот же qsort из МС ЦРТ рапичкан подобными "оптимизациями". И что? Значительно проигрывает лобовой классике не использующей указателей на воид как средство абстрагирования.
К> выбор точки разделителя как средней между минимумом и максимумом — не нуждаются в адресной арифметике; вполне можно обойтись ++.
Да? И как ты себе это представляшь? Легкий перебор списка с целью вычисления его длинны и еще один ненавязчивый для поиска нужного значения? Или наш итератор все же позволяет произвольный доступ и предоставляет информацию о количестве элементов?
К>Другое дело, что для двусвязных списков есть более эффективные алгоритмы.
Ага. Причем самый эффективный копирование в массив. Ну, если конечно объемы позволяют коллекцию в память поднять. Иначе конечно мердж-сортировка является самым правильным выбором.
Кстати, о связанных саписках. Напдо признать, что с точки зрения скорости приложения они почему-то почти всегда проигрывают другим средствам. Не даром до второго фрэймворка МС даже не ввела такой примитив в состав коллекций. Да и с появлением этого дела как-то не тянет его писпользовать.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Перекуём баги на фичи!
