Re[6]: Про итераторы
От: Павел Кузнецов  
Дата: 28.04.05 19:23
Оценка:
Sergey,

M>
sort(range(container, 10, 20));


> Надо упорядочить массив A так, чтобы выполнялось B[A[i]] < B[A[j]] для любых i < j, i > 0, j < N. Массивы большие — копировать их нельзя. С STL-итераторами и std::sort задача решается , при наличии boost — решается еще и легко, за счет iterator_facade. А вот с operator[] и size() выходит закавыка — выясняется, что операции сравнения и модификации элемента — совершенно разные вещи.


Тут не в итераторах дело, а в функции сравнения. Для поддержки данного use case достаточно изменить сигнатуру sort:
sort(A, my_comparer(B));
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[13]: Про итераторы
От: Павел Кузнецов  
Дата: 28.04.05 19:27
Оценка:
Кодт,

>
> ПК>templ_function( **it );
>

> Это плохая идея: получается, что Accessor имеет семантику указателя, а не только ссылки.
> Лучше ввести дружественную функцию с "человеческим" именем, или метод <...>

Может быть, не знаю. В первоначальном варианте код выглядел так:
templ_function( get(*it) );

С другой стороны, использование разыменования подчеркивает дополнительную косвенность, вводимую акцессором.

Да и вообще, если исходить из минималистических соображений, то вообще никакие дополнительные operator* или get() не нужны, т.к. можно пользоваться явным преобразованием
templ_function( static_cast<T&>(*it) );


> Мне больше нравятся внешние функции


+1

> (Всё вышеперечисленное — это синтаксический сахар, соль и перец по вкусу).


+1
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[11]: Про итераторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.04.05 20:18
Оценка:
Здравствуйте, Павел Кузнецов, Вы писали:

ПК>
ПК>     QMap<int, QWidget *> map;
ПК>     QHash<int, QWidget *> hash;

ПК>     QMapIterator<int, QWidget *> i(map);
ПК>     while (i.hasNext()) {
ПК>         i.next();
ПК>         hash.insert(i.key(), i.value());
ПК>     }
ПК>

ПК>Здесь недостатки итераторов QT становятся уже заметными. С итераторами STL это выглядело бы заметно короче и яснее:
ПК>
ПК>     std::map<int, QWidget*> map;
ПК>     std::hash_map<int, QWidget> hash(map.begin(), map.end());
ПК>


Здорово рассуждаешь! "Короче и яснее"... Просто есть функция (конструктор) рещающая задачу которая иначе решается императивно. Только и всего. Будь функция принимающая обычный итератор, то код был бы еще проше.
QHash<int, QWidget*> hash(QMapIterator<int, QWidget*>(map));

В дотнетной библиотеке наличие конструктора принимающего энумератор или другую структуру в порядке вещей. А так как почти все коллекции к ним приводятся, то код получается вообще минимальным.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[12]: Про итераторы
От: Павел Кузнецов  
Дата: 28.04.05 20:55
Оценка: 18 (3) +1 -1
VladD2,

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


Например, у того же Hashtable конструктора, принимающего IEnumerator или IEnumerable, не обнаружилось. Найден конструктор от IDictionary, что в свете твоего заявления о порядке вещей особенно странно, т.к. энумераторы — общий подход, а создание связей с конкретными интерфейсами ассоциативных контейнеров — частный, не масштабируемый на контейнеры других типов. В частности, как можно сконструировать Hashtable из последовательности пар <key, value>, не прибегая к ручному заполнению в цикле?

Конструкторы ArrayList, Stack и Queue тоже принимают не IEnumerator, и даже не IEnumerable, а ICollection. HybridDictionary, ListDictionary, StringDictionary, NameValueCollection, вообще, не могут быть сконструированы ни из чего подобного

В общем, среди контейнеров конструкторы, принимающие энумератор, не обнаружены... Ессно, это не означает, что такого конструктора не могло быть сделано, просто заставляет задуматься о роли, которую отводили энумераторам при проектировании.

При этом идиология энумераторов .Net от идиологии энумераторов Java очень далека, т.к. в энумераторах Java получение значения совмещено с переходом на следующий/предыдущий элемент, а в .Net эти операции разделены.

Вообще же, энумераторы .Net и итераторы Java, фактически, непригодны для сколько-нибудь сложных алгоритмов, т.к. их даже копировать нельзя.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[13]: Про итераторы
От: GlebZ Россия  
Дата: 29.04.05 09:53
Оценка:
Здравствуйте, Павел Кузнецов, Вы писали:

ПК>VladD2,


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


ПК>Конструкторы ArrayList, Stack и Queue тоже принимают не IEnumerator, и даже не IEnumerable, а ICollection. HybridDictionary, ListDictionary, StringDictionary, NameValueCollection, вообще, не могут быть сконструированы ни из чего подобного

1. У вас немного не то представление об этих интерфейсов. Как IDictionary так и ICollection наследуется от IEnumerable. То есть, получение Enumeratora возможно.
2. К Владу. Возможность получения энумератора еще совсем не обозначает что это наиболее оптимальный путь. Для быстрого копирования нужно знать длину копируемых данных, что в случае стандартного IEnumerator невозможно. IEnumerator вполне может работать с потоками, за что им и спасибо. В то же время, в ICollection такая информация предоставляется.

ПК>В общем, среди контейнеров конструкторы, принимающие энумератор, не обнаружены... Ессно, это не означает, что такого конструктора не могло быть сделано, просто заставляет задуматься о роли, которую отводили энумераторам при проектировании.


ПК>При этом идиология энумераторов .Net от идиологии энумераторов Java очень далека, т.к. в энумераторах Java получение значения совмещено с переходом на следующий/предыдущий элемент, а в .Net эти операции разделены.

И это есть good.
Что касается получения объекта в энумераторе NET, то в этом случае очень удобно делать ленивое получение объекта. Это есть very good.

ПК>Вообще же, энумераторы .Net и итераторы Java, фактически, непригодны для сколько-нибудь сложных алгоритмов, т.к. их даже копировать нельзя.

Вообще-то, достаточно пригодны. Есть точка входа в виде получения енумератора. В данном случае, как раз и копируются все внутренние данные для егойной работы. И в частности, я по крайней мере практиковал вообще полное копирование коллекции (проблемы изменения коллекции во время работы итератора никто нигде не отменял).

С уважением, Gleb.
PS:Я балдею от STL и считаю их итераторы наиболее удобные для работы в C++. Только не надо из них делать панацею которая удобна во всех случаях. Такого никогда и никто не создавал.
... << RSDN@Home 1.1.4 beta 4 rev. 358>>
Re[14]: Про итераторы
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 29.04.05 10:20
Оценка:
Здравствуйте, GlebZ, Вы писали:

GZ>2. К Владу. Возможность получения энумератора еще совсем не обозначает что это наиболее оптимальный путь. Для быстрого копирования нужно знать длину копируемых данных, что в случае стандартного IEnumerator невозможно. IEnumerator вполне может работать с потоками, за что им и спасибо. В то же время, в ICollection такая информация предоставляется.


На самом деле все еще проще. Конструктор ArrayList с параметром примерно такой.
public ArrayList(ICollection col)
{
    _internalBuffer = new object[col.Count];
    col.CopyTo(_internalBuffer, 0);
}


Вот ради этого CopyTo туда и передается ICollection. И итераторы для этого не подходят. Любые, сколь угодно навороченные.

GZ>Что касается получения объекта в энумераторе NET, то в этом случае очень удобно делать ленивое получение объекта. Это есть very good.


Ну об этом ПК писал.
... << RSDN@Home 1.1.4 beta 6a rev. 439>>
AVK Blog
Re[11]: Про итераторы
От: jazzer Россия Skype: enerjazzer
Дата: 29.04.05 10:29
Оценка:
Здравствуйте, AndrewVK, Вы писали:

AVK>P.S. Демагогия идет лесом. Попробуйте сосредоточиться на обсуждении предмета, а не личности собеседника.


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

You will always get what you always got
  If you always do  what you always did
Re[12]: Про итераторы
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 29.04.05 10:38
Оценка:
Здравствуйте, jazzer, Вы писали:

J>Андрей, последний абзац, который ты выкинул при цитировании, как раз был посвящен обсуждению предмета


Ну и что?
... << RSDN@Home 1.1.4 beta 6a rev. 439>>
AVK Blog
Re: Про итераторы
От: jazzer Россия Skype: enerjazzer
Дата: 29.04.05 10:40
Оценка: +1
CS>Есть два подхода к итераторам: "Java" и "STL"

Ну так чего, кто-нибудь приведет код реализации итерации по подпоследовательности средствами итераторов java или .Net?

потому что в STL это делается одним движением мизинца левой ноги:
std::for_each(it1, it2, <всякая фигня>);



А то какая-то бессмысленная священная война о том, как Степанов некорректно применил термин "итератор" из GoF в те времена, когда GoF и в помине не было.
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[14]: Про итераторы
От: Кодт Россия  
Дата: 29.04.05 11:01
Оценка: +1
Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Может быть, не знаю. В первоначальном варианте код выглядел так:

ПК>templ_function( get(*it) );

С точностью до имени функции :)

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


Тогда акцессор должен иметь семантику указателя.

Я уже напился своих слёз, когда однажды завёл класс с семантикой и указателя, и ссылки :(

ПК>Да и вообще, если исходить из минималистических соображений, то вообще никакие дополнительные operator* или get() не нужны, т.к. можно пользоваться явным преобразованием :-)

ПК>templ_function( static_cast<T&>(*it) );

Это не совсем очевидный способ. Откуда-то возникают явные имена типов... которые ещё и должны быть согласованы с акцессором. Функции автоматического выведения типа — симпатичное решение. Тем более, что можно сделать перегрузку их для любого типа акцессора, в том числе для голого T&.
Перекуём баги на фичи!
Re[15]: Про итераторы
От: Кодт Россия  
Дата: 29.04.05 11:06
Оценка:
Здравствуйте, AndrewVK, Вы писали:

AVK>На самом деле все еще проще. Конструктор ArrayList с параметром примерно такой.

AVK>public ArrayList(ICollection col)
AVK>{
AVK>    _internalBuffer = new object[col.Count];
AVK>    col.CopyTo(_internalBuffer, 0);
AVK>}

AVK>Вот ради этого CopyTo туда и передается ICollection. И итераторы для этого не подходят. Любые, сколь угодно навороченные.

А кто мешает сделать прокси-коллекцию? Которая умеет делать CopyTo из энумератора?
Перекуём баги на фичи!
Re[16]: Про итераторы
От: GlebZ Россия  
Дата: 29.04.05 11:16
Оценка:
Здравствуйте, Кодт, Вы писали:

К>А кто мешает сделать прокси-коллекцию? Которая умеет делать CopyTo из энумератора?

Никто. Мало того, я такое делал для копирования из потока в буфер. Но быстрее memmove может быть только Copy из Delphi.

С уважением, Gleb.
... << RSDN@Home 1.1.4 beta 4 rev. 358>>
Re[16]: Про итераторы
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 29.04.05 11:19
Оценка:
Здравствуйте, Кодт, Вы писали:

К>А кто мешает сделать прокси-коллекцию? Которая умеет делать CopyTo из энумератора?


реализация CopyTo для ArrayList и коллекций на его основе это просто memmove. Соотв. твой способ будет значительно медленнее.
... << RSDN@Home 1.1.4 beta 6a rev. 439>>
AVK Blog
Re[2]: Про итераторы
От: Sinclair Россия https://github.com/evilguest/
Дата: 29.04.05 11:40
Оценка: +2
Здравствуйте, jazzer, Вы писали:
J>Ну так чего, кто-нибудь приведет код реализации итерации по подпоследовательности средствами итераторов java или .Net?
Вопрос не понял. Что такое "подпоследовательность"? Промежуток промеж двух итераторов? Не имеет смысла, т.к. в Java или .Net не принято использовать енумератор как указатель.
Для них более естественно состряпать адаптер, который переберет весь нужный поддиапазон.
public class MyArrayBasedCollection
{
  public IEnumerable SubRange(int start, int end)
    {
      for(int i = start, i<end; i++)
          yield return this[i];
    }
}

...
foreach (object o in myabc.SubRange(1, 50))
{
  Console.Write(o);
}

...

public static IEnumerable<T> Limit(IEnumerable<T> source, int limit)
{
  int i;
    foreach(T t in source)
    {
      if (i++ > limit) return;
        yield return t;
    }
}
...
int[] a = new int[50];
foreach(object o in Limit(a, 5));
... << RSDN@Home 1.1.4 beta 5 rev. 395>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[3]: Про итераторы
От: jazzer Россия Skype: enerjazzer
Дата: 29.04.05 12:32
Оценка:
Здравствуйте, Sinclair, Вы писали:

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

J>>Ну так чего, кто-нибудь приведет код реализации итерации по подпоследовательности средствами итераторов java или .Net?
S>Вопрос не понял. Что такое "подпоследовательность"?
Обычная подпоследовательность в математическом смысле. Часть последовательности.
S>Промежуток промеж двух итераторов?
Например. Просто мне каким-то образом известно начало и конец подпоследовательности (в STL это итераторы, в .Net — пусть соответствующие гуру скажут), и я хочу с этой самой подпоследовательностью что-нть сделать. Например, развернуть ее.
S>Не имеет смысла, т.к. в Java или .Net не принято использовать енумератор как указатель.
S>Для них более естественно состряпать адаптер, который переберет весь нужный поддиапазон.

пример понятен: в C# все будет основываться на индексах в главной последовательности, и, соответственно, для итерации по подпоследовательности нужны эти два индекса и сама эта главная последовательность.

Поправьте, если не так.
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[13]: Про итераторы
От: jazzer Россия Skype: enerjazzer
Дата: 29.04.05 12:58
Оценка: +1
Здравствуйте, AndrewVK, Вы писали:

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


J>>Андрей, последний абзац, который ты выкинул при цитировании, как раз был посвящен обсуждению предмета


AVK>Ну и что?


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

You will always get what you always got
  If you always do  what you always did
Re[3]: Про итераторы
От: Павел Кузнецов  
Дата: 29.04.05 15:42
Оценка:
Sinclair,

> Для них более естественно состряпать адаптер, который переберет весь нужный поддиапазон.

>
> public class MyArrayBasedCollection
> {
>   public IEnumerable SubRange(int start, int end)
>     {
>       for(int i = start, i<end; i++)
> ...
>
> public static IEnumerable<T> Limit(IEnumerable<T> source, int limit)
> {
>   int i;
>     foreach(T t in source)
>     {
>       if (i++ > limit) return;
> ...
>


Такой подход либо требует контейнера с произвольным доступом, либо приводит к дополнительному проходу по элементам там, где в случае итераторов он не нужен.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[14]: Про итераторы
От: Павел Кузнецов  
Дата: 29.04.05 15:58
Оценка:
GlebZ,

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


> ПК>Конструкторы ArrayList, Stack и Queue тоже принимают не IEnumerator, и даже не IEnumerable, а ICollection. HybridDictionary, ListDictionary, StringDictionary, NameValueCollection, вообще, не могут быть сконструированы ни из чего подобного


> 1. У вас немного не то представление об этих интерфейсов. Как IDictionary так и ICollection наследуется от IEnumerable. То есть, получение Enumeratora возможно.


Я знаю, что эти интерфейсы наследуются от IEnumerable. Вопрос как раз в том, что именно IEnumerable конструкторы контейнеров не принимают, что говорит о недостаточности возможностей IEnumerable/IEnumerator для этих целей.

> ПК>При этом идиология энумераторов .Net от идиологии энумераторов Java очень далека, т.к. в энумераторах Java получение значения совмещено с переходом на следующий/предыдущий элемент, а в .Net эти операции разделены.


> И это есть good.


Что именно?

> Что касается получения объекта в энумераторе NET, то в этом случае очень удобно делать ленивое получение объекта. Это есть very good.


Да, именно отсутствие такой возможности в итераторах Java мне и не понравилась.

>

> ПК>Вообще же, энумераторы .Net и итераторы Java, фактически, непригодны для сколько-нибудь сложных алгоритмов, т.к. их даже копировать нельзя.

> Вообще-то, достаточно пригодны. Есть точка входа в виде получения енумератора. <...>


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

> В данном случае, как раз и копируются все внутренние данные для егойной работы. И в частности, я по крайней мере практиковал вообще полное копирование коллекции (проблемы изменения коллекции во время работы итератора никто нигде не отменял).


Вопрос не о копировании контейнера, а о копировании итераторов/энумераторов.

> PS: Я балдею от STL и считаю их итераторы наиболее удобные для работы в C++. Только не надо из них делать панацею которая удобна во всех случаях.


Естественно. Речь шла о возможностях, которые предоставляют те или иные абстракции. Возможности энумераторов .Net и итераторов Java, на мой взгляд, очень сильно ограничены. Фактически, сводятся к перебору по контейнеру. О чем спор-то? Какие конкретно возможности, помимо последовательного перебора элементов, дают энумераторы .Net или итераторы Java? Какие алгоритмы можно/имеет смысл реализовать с их помощью? Даже для простого копирования элементов, как выяснилось, в контейнерах .Net предпочитают на них не рассчитывать
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[13]: Про итераторы
От: VladD2 Российская Империя www.nemerle.org
Дата: 29.04.05 16:00
Оценка:
Здравствуйте, Павел Кузнецов, Вы писали:

ПК>VladD2,


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


ПК>Например, у того же Hashtable конструктора, принимающего IEnumerator или IEnumerable, не обнаружилось.


И было бы странно если бы он был. Все же к списку хэш-таблица отношения не имеет.

ПК>Конструкторы ArrayList, Stack и Queue тоже принимают не IEnumerator, и даже не IEnumerable, а ICollection. HybridDictionary, ListDictionary, StringDictionary, NameValueCollection, вообще, не могут быть сконструированы ни из чего подобного


В первой версии для целей копирования использовался ICollection. Во второй для дженерик-коллекций используется именно IEnumerable<T>:
List&lt;T&gt; Constructor
LinkedList&lt;T&gt; Constructor
Queue&lt;T&gt; Constructor
Stack&lt;T&gt; Constructor

И мне кажется это разумным. Да, ICollection и ICollection<T> несколько более быстры при работе с массивами, но нет проблем написать примерно такой код:
public List(IEnumerable<T> collection)
{
    ICollection<T> collection = collection as ICollection<T>;
    if (collection != null)
    {
        int num1 = collection.Count;
        _items = new T[num1];
        collection1.CopyTo(_items, 0);
        _size = num1;
    }
    else
    {
        _size = 0;
        _items = new T[4];
        using (IEnumerator<T> enumerator = collection.GetEnumerator())
            while (enumerator.MoveNext())
                Add(enumerator.Current);
    }
}

Что с успехом и делается в новом фрэймворке. Почему до этого не доперли раньше я не знаю. Видимо ступили.

Для словарей (мапов) этого естественно нет, так как это не размумно (они же не списки).


ПК>При этом идиология энумераторов .Net от идиологии энумераторов Java очень далека, т.к. в энумераторах Java получение значения совмещено с переходом на следующий/предыдущий элемент, а в .Net эти операции разделены.


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

ПК>Вообще же, энумераторы .Net и итераторы Java, фактически, непригодны для сколько-нибудь сложных алгоритмов, т.к. их даже копировать нельзя.


Очень обоснованное и серьезное мнение. Жаль, правда, что ничего с действительностью не имеет.
Что касается копирования, то IEnumerable — это фабрика итераторов. Так что копировать ничего и не нужно. Работа идет обычно именно с этим интерфейсом.

Ну, и не нужно забывать, что итераторы — это хотя и полезная, но не единственная концепция. Как я уже говорил, в дотнете для работы с коллекциями существует иерархия интефейсов и их запрос практически ничего не стоит. Если задачу эффективнее решить с помощью ICollection или IList, а не IEnumerable, то никто не мешает попытаться получить эти интерфейсы и если не получится решить проблему чуть менее эффективно.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Про итераторы
От: c-smile Канада http://terrainformatica.com
Дата: 29.04.05 16:43
Оценка:
Здравствуйте, jazzer, Вы писали:

J>потому что в STL это делается одним движением мизинца левой ноги:

J>
J>std::for_each(it1, it2, <всякая фигня>);
J>


Интересно а что произойдет если it1 и it2 взяты от разных последовательностей?
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.