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

VD>Понял. Не уверен. Я как-то с prev не связывался. Но с точки зрения next там именно переход, скажем так, c -1 и далее.

Слушайте, я, кажется, просёк фишку — о чём спор идёт!
Итак, next() и prev() — функции, меняющие состояние. Поэтому сравнивать их с неменяющей функцией (разыменование stl-итератора) — бестолково.
А практика использования двунаправленных итераторов (в первую очередь — указателей на элементы массива) в движении — вот такая:

*p++; // прочесть/записать и перейти дальше
*--p; // отступить и прочесть/записать

И это, как несложно заметить, ровно то же самое, что и next(), prev().
А уж стоит этот итератор "между" элементами или "на" элементе — в данном случае пофиг, как трактовать.

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

VD>И вообще, кроме скоростных характеристик еще есть время доступа. И для деревьев основанных на ссылках оно выше чем для массивов.

Без вопросов!

Если мы как-либо реализуем дерево поверх массива — то проиграем в том, что деревянный порядок обхода может отличаться от обхода массива (получим соответственные промахи кэша; более сложную, чем инкременты, арифметику; и т.п.)

Останется вопрос, что нам важнее:
— скорость произвольного изменения структуры (сплошной массив проигрывает; либо мы попросту изобретаем аллокатор),
— скорость доступа с сохранением структуры (сплошной массив выигрывает)
— скорость обхода в фиксированном порядке (сплошной массив выигрывает)
— скорость обхода в другом порядке (как карта ляжет)

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

К>Если мы как-либо реализуем дерево поверх массива — то проиграем в том, что деревянный порядок обхода может отличаться от обхода массива (получим соответственные промахи кэша; более сложную, чем инкременты, арифметику; и т.п.)

Если делать все грамотно, то все будет с точностью до наоборот. А проиграм мы в модификации. Эмуляция деревьев на массиве всем хороша кроме того, что модификация приводит к необоходимости двигать память. А это приговор на на больших объемах.

К>Останется вопрос, что нам важнее:
К>- скорость произвольного изменения структуры (сплошной массив проигрывает; либо мы попросту изобретаем аллокатор),
К>- скорость доступа с сохранением структуры (сплошной массив выигрывает)
К>- скорость обхода в фиксированном порядке (сплошной массив выигрывает)
К>- скорость обхода в другом порядке (как карта ляжет)

+1

Здравствуйте, Кодт, Вы писали:
...
К>И это, как несложно заметить, ровно то же самое, что и next(), prev().
К>А уж стоит этот итератор "между" элементами или "на" элементе — в данном случае пофиг, как трактовать.

В общем, да.

Здравствуйте, Костя Ещенко, Вы писали:

КЕ>Также в контексте соседнего спора о дотнетных терминах, интересно, что они различают контейнер и список.

Это то как раз разумно. Такие контейнеры как ассоциативные массивы списками строго говоря не являются, но при этом они контейнеры.

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

К>>Если мы как-либо реализуем дерево поверх массива — то проиграем в том, что деревянный порядок обхода может отличаться от обхода массива (получим соответственные промахи кэша; более сложную, чем инкременты, арифметику; и т.п.)

VD>Если делать все грамотно, то все будет с точностью до наоборот. А проиграм мы в модификации. Эмуляция деревьев на массиве всем хороша кроме того, что модификация приводит к необоходимости двигать память. А это приговор на на больших объемах.

От грамотности многое зависит Нужно определиться, какой юзкейс будет наиболее востребован, и заточить задачу под него.
Скажем, если нужен поперечный обход дерева — то наиболее удобна одна проекция на массив (соответствующая двоичному поиску — ну или k-ричному). Пример — сортированные деревья.
Если нужен обход в ширину — то удобнее пирамида (дети узла i имеют номера ki+1,ki+1,...ki+k). Пример — очередь с приоритетами.
Если нужна быстрая вставка с упорядочиванием — то массив может выступить в роли типизированной кучи.

В общем, вариантов море, и все они направлены на уменьшение коэффициента при O().

VladD2,

> К> Итого, полное время обхода — 2n-2 переходов по рёбрам.

> Ну, то есть все же O(2 * n — 2). Я собственно об этом речь и вел.

Влад, это несерьезно. O(2 * n — 2) === O(n). На всякий случай: O(100) === O(1), O(2 * 100 + 10000) === O(1), etc.

VladD2,

> ПК> O(n) при переборе элементов любого дерева (если порядок обхода не важен) получается элементарно, если в качестве представления выбрать классический список смежности.

> Я незнаю, что ты имешь в виду под "список смежности".

http://www.google.com/search?q=adjacency+list
http://www.yandex.ru/yandsearch?text=%F1%EF%E8%F1%EE%EA+%F1%EC%E5%E6%ED%EE%F1%F2%E8

> Но в любом случае это дополнительные расширения.

Это не расширения. Это один из нескольких классических вариантов представления графов. Просто замечательно подходит для представления деревьев. И совершенно автоматически дает время обхода всех вершин O(n).

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

К>А практика использования двунаправленных итераторов (в первую очередь — указателей на элементы массива) в движении — вот такая:
К>

К>*p++; // прочесть/записать и перейти дальше
К>*--p; // отступить и прочесть/записать
К>

К>И это, как несложно заметить, ровно то же самое, что и next(), prev().

Да уж, нагородили... А ноги здесь растут из архитектуры PDP-11, в которой были очень удобные методы адресации — автоинкрементная косвенная и автодекрементная косвенная:

MOV (R0)+,(R1)+
Или
MOV -(R0),-(R1)

То есть, одна инструкция процессора обеспечивала копирование значения и инкрементацию/декрементацию указателей.
И именно отсюда растут ноги Сишных операторов ++ и --. При этом, на PDP-11, наиболее естественными методами итерации были именно *p++ и *--p, то есть, пост-инкремент и пре-декремент. Запись do while(*dst++ = *src++); транслировалась в две инструкции:

L1: MOV (R0)+, (R1)+
    BNE L1

А вот пре-инкремент и пост-декремент были несколько неестественными и требовали большего числа команд. А потом всех задавил Intel, в котором нет таких метов адресации и элегантность трансляции ушла в небытие.
А уже потом-потом-потом жависты выдали эту концепию как великое откровение и супер-удобство.
Все что можно было изобрести, уже изобретено... Что-то в этом есть.

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

КЕ>>Также в контексте соседнего спора о дотнетных терминах, интересно, что они различают контейнер и список.

VD>Это то как раз разумно. Такие контейнеры как ассоциативные массивы списками строго говоря не являются, но при этом они контейнеры.

Наверное было непонятно к чему я это сказал.

> In object-oriented programming, an iterator is an object allowing one to sequence through all of the elements or parts contained in some other object, typically a container or list.

Поскольку в цитате АВК сказано container or list, то ясно что речь идет о списке не как о контейнере. Никакой другой реализации спика-не-контейнера кроме связанного списка я не знаю. Так что в этой цитате из википедии термин list имеет значение linked list. Только и всего.

Кодт,

> Итак, next() и prev() — функции, меняющие состояние. Поэтому сравнивать их с неменяющей функцией (разыменование stl-итератора) — бестолково.
> А практика использования двунаправленных итераторов (в первую очередь — указателей на элементы массива) в движении — вот такая:
>

> *p++; // прочесть/записать и перейти дальше
> *--p; // отступить и прочесть/записать
>

> И это, как несложно заметить, ровно то же самое, что и next(), prev().

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

Потеря производительности может легко происходить в случае, если, например, происходит итерация по файлу записей, каждая из которых является сериализованным объектом. В этом случае, даже если нам нужен только 128-й объект, все 127 предыдущих объектов придется создать.

Работать с такими энумераторами может оказаться сложнее, например, если упомянутые объекты читаются нетривиально, скажем, с помощью плагинов. Допустим, что если плагина для чтения какого-то объекта нет, то должно генерироваться исключение. В этом случае, если при вызове next() было выброшено исключение, далеко не очевидно, произошел ли фактический инкремент, или же энумератор по-прежнему указывает на запись, которую мы читать не умеем. В последнем случае, как пропустить злополучную запись — неясно.

Мы тут с Лешей Чернораенко пообсуждали итераторы, и сошлись на том, что более перспективным является разделение навигации и доступа к элементу не только по разным операциям, но и по разным объектам. В этом случае операция итератора доступа к элементу (operator * в случае итераторов STL) возвращала бы аксессор, прокси-объект, предназначенный для "настоящего" доступа к элементу, на который указывает итератор. Такой подход позволяет избежать создания объекта в случае, если итератор разыменовывается только чтобы ему присвоить новое значение.

*it = create_expensive_object();

Альтернативой, естественно, могут служить именованные операции set/get; или, для C++, введение в язык разных операций разыменования, разделяя случаи использования в качестве l-value и r-value. Но в случае выделения аксессоров в отдельный класс появляется более тонкий контроль над тем, что можно делать клиенту: если ему вернули аксессор, то перемещаться по множеству объектов он уже не может, только получать/менять объект, который он получил. При этом, в отличие от возвращения ссылки, объект изначально существовать не обязан.

Костя,

>

>> In object-oriented programming, an iterator is an object allowing one to sequence through all of the elements or parts contained in some other object, typically a container or list.

> Поскольку в цитате АВК сказано container or list, то ясно что речь идет о списке не как о контейнере. Никакой другой реализации спика-не-контейнера кроме связанного списка я не знаю.

А почему linked list не является контейнером?.. Имхо, фрагмент "a container or list" в цитате выше, вообще, имеет мало смысла: было бы достаточно просто "a container".

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Костя,

>>

>>> In object-oriented programming, an iterator is an object allowing one to sequence through all of the elements or parts contained in some other object, typically a container or list.

>> Поскольку в цитате АВК сказано container or list, то ясно что речь идет о списке не как о контейнере. Никакой другой реализации спика-не-контейнера кроме связанного списка я не знаю.

ПК>А почему linked list не является контейнером?..

Linked list может являться просто россыпью отдельных узлов без общего объекта-фасада. Либо под списком-но-не-контейнером это и имелось ввиду, либо непонятно что авторы хотели сказать.

ПК>Имхо, фрагмент "a container or list" в цитате выше, вообще, имеет мало смысла: было бы достаточно просто "a container".

Если бы было просто "a container" я бы ничего и не сказал. Это была мелочная подколка Википедии — типа если термин list не означает linked list, как это выяснилось, то и определение итераторов из Википедии тоже не без греха.

Hello, McSeem2!
You wrote on Sun, 24 Apr 2005 15:38:16 GMT:

M> Если же надо отсортировать в диапазоне, делаем это через
M> простейший-простейший адаптор:

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

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

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

M> Вот что сказал Tony Juricic (один из активных пользователей моего
M> mail-листа):

M> You won't get argument from me here. While I don't mean to say there are
M> not many very useful classes in BOOST, the sheer amount of dirt you have
M> to pull in, just to use it, is making BOOST less and less of a library I
M> would consider for doing anything.

M> It is IMO becoming a display of the failure of compilers and language
M> extensions, on the other extreme but in its practical nonsense
M> complementary to latest MS additions to 'managed C++'.

Ну, лишнего в бусте может и много, но вот полезного тоже не мало.

With best regards, Sergey.

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Альтернативой, естественно, могут служить именованные операции set/get;

Или просто свойство.

ПК>Но в случае выделения аксессоров в отдельный класс появляется более тонкий контроль над тем, что можно делать клиенту: если ему вернули аксессор, то перемещаться по множеству объектов он уже не может, только получать/менять объект, который он получил. При этом, в отличие от возвращения ссылки, объект изначально существовать не обязан.

Но при этом заметно увеличится оверхед и усложнится структура кода.

AndrewVK,

> ПК> Но в случае выделения аксессоров в отдельный класс появляется более тонкий контроль над тем, что можно делать клиенту: если ему вернули аксессор, то перемещаться по множеству объектов он уже не может, только получать/менять объект, который он получил. При этом, в отличие от возвращения ссылки, объект изначально существовать не обязан.

> Но при этом заметно увеличится оверхед и усложнится структура кода.

Это почему? Такие вещи в том же C++ подставляются (inline) "на ура". Структура кода тоже не усложняется. Точнее, в подавляющем большинстве случаев клиентский код будет выглядеть в точности так же, как и в случае возврата прямой ссылки.

Возможный интерфейс аксессора:

template< class T >
class Accessor
{
public:
   operator T&();

   Accessor<T>& operator =(T const&);

   T& operator*();

   . . .
};

если все функции-члены Accessor<> inline, то за абстракцию мы (обычно) ничего не платим, если устройство Accessor<> простое, то компилятор в состоянии полностью элиминировать наличие подобного proxy. В случаях же, когда Accessor<> делает что-нибудь более сложное (скажем, продолжая прошлый пример, загрузка объекта из файла), собственно, для чего он и вводится, то на фоне этих операций издержки на создание промежуточного объекта будут ничтожными.

Код клиента остается таким же, как если бы *it возвращал бы ссылку на объект:

T  obj = *it;       // по-прежнему работает
T& obj = *it;       // и это по-прежнему работает
*it = create_obj(); // по-прежнему работает, (потенциально) более эффективно,
                     // чем ранее, т.к. может избежать создания ненужного объекта

Есть одно место, где потенциально "сломается" код клиента — вызов шаблона функции с выводом аргумента шаблона по *it. В этом случае все легко "чинится" использованием функции Accessor<>::operator *, принудительно "разыменовывающей" accessor:

templ_function( **it );

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

К>Слушайте, я, кажется, просёк фишку — о чём спор идёт!
К>Итак, next() и prev() — функции, меняющие состояние. Поэтому сравнивать их с неменяющей функцией (разыменование stl-итератора) — бестолково.
К>А практика использования двунаправленных итераторов (в первую очередь — указателей на элементы массива) в движении — вот такая:
К>

К>*p++; // прочесть/записать и перейти дальше
К>*--p; // отступить и прочесть/записать
К>

К>И это, как несложно заметить, ровно то же самое, что и next(), prev().
К>А уж стоит этот итератор "между" элементами или "на" элементе — в данном случае пофиг, как трактовать.

Вопрос был: Почему авторы QT (и не только они) считают что Java вариант исполнения итератора удобнее?

c-smile,

> Вопрос был: Почему авторы QT (и не только они) считают что Java вариант исполнения итератора удобнее?

Может, потому что они используют итераторы только для простых нужд (только последовательный перебор элементов контейнера), а более сложные моменты пишут "ручками", а не используют готовые шаблоны алгоритмов? На это наталкивает множество примеров из статьи об итераторах QT.

     while (i.hasNext())
         cout << i.next().ascii() << endl;

вместо использования std::copy + boost::bind.

     while (i.hasNext()) {
         if (i.next() % 2 != 0)
             i.remove();
     }

вместо использования std::remove_if. Данный случай в "ручном" исполнении уже заметно менее эффективен, например, для вектора.

     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());

При последовательном переборе может оказаться чуть более удобным то, что достаточно одного энумератора, а не двух итераторов. В чуть более сложном случае перебора с возвратами, имхо, энумераторы быстро перестают быть удобными из-за того, что приходиться бороться с повтором значений в момент смены направления (next и prev, вызванные последовательно, дают одно и то же значение). A если в язык будет добавлена поддержка лямбда-функций, имхо, итераторы в стиле STL станут более удобными во всех случаях, и в простом, и в сложных. А если еще ввести перегруженные алгоритмы, работающие с диапазонами...

P.S. Можно заметить, что QT мосты не сжигает, и итераторы в стиле STL по-прежнему в наличии.

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

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

Почему закавыка? Заводим фасад массива (ссылающийся на массив данных и массив индексов)...
Заодно, он будет выдавать правильные итераторы и правильные аксессоры.

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Есть одно место, где потенциально "сломается" код клиента — вызов шаблона функции с выводом аргумента шаблона по *it. В этом случае все легко "чинится" использованием функции Accessor<>::operator *, принудительно "разыменовывающей" accessor:

ПК>templ_function( **it );

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

templ_function(undress(*it)); // раздевает ссылку
templ_function(*undress(it)); // раздевает указатель
templ_function((*it).get());
templ_function(*(it.get()));

Мне больше нравятся внешние функции — они не требуют от умных указателей/ссылок семантики класса с членами.

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