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

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

DS>>s/MoveNext/popFront
DS>>, то полученный результат ничего не напомнит?

J>С прямым итератором это действительно так.
J>А вот у двунаправленного итератора будет еще и MovePrev — ы? Аналогично для итератора с произвольным доступом.
Я как бы хотел узнать, можно ли исходную конструкцию назвать итератором, и чем она отличается от range. В возможности добавления туда игр и девушек я не сомневался

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

Я вообще как-то плохо понимаю: такое ощущение, что все старательно подходят с молотком к новому шурупу, и делают соответствующие выводы.

Неужели ни кому не нравится вот такая возможность:

vector<double> v1, v2;
deque<double> d;
partial_sort(v1, chain(v2, d));
sort(chain(v1, v2, d));

или вот такая:

vector<double> vd;
vector<string> vs;
deque<int>     vi;
// sort the three in lockstep
sort(zip(vs, vd, vi));

PS. Посмотрел на boost::zip_iterator. Сомневаюсь, что читаемый аналог второго примера влезет в экран.

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

DS>Неужели ни кому не нравится вот такая возможность:
DS>

DS>vector<double> v1, v2;
DS>deque<double> d;
DS>partial_sort(v1, chain(v2, d));
DS>sort(chain(v1, v2, d));
DS>

А зачем это всё нужно?

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

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

DS>>Неужели ни кому не нравится вот такая возможность:
DS>>

DS>>vector<double> v1, v2;
DS>>deque<double> d;
DS>>partial_sort(v1, chain(v2, d));
DS>>sort(chain(v1, v2, d));
DS>>

E>А зачем это всё нужно?

В смысле?
Этот конкретный пример нужен для демонстрации лаконичности ranges.
Частично отсортировать элементы по трем контейнерам? эээ, ну, ммм... Ну собрали три лукошка с грибами. Нужно отобрать лукошко красивых, а остальные -- на посол. Или как-то так. Сходу нормальный пример не придумать, да. Впрочем, я и для boost::mpl годный пример вот так запросто не выдумаю.
range — нужен как альтернативный подход к склейке алгоритмов и контейнеров в STL.

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

E>А зачем это всё нужно?

Александреску:

Range-based design offers much more than a port of iterator-based functions to ranges

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

DS>Частично отсортировать элементы по трем контейнерам? эээ, ну, ммм... Ну собрали три лукошка с грибами. Нужно отобрать лукошко красивых, а остальные -- на посол. Или как-то так. Сходу нормальный пример не придумать, да. Впрочем, я и для boost::mpl годный пример вот так запросто не выдумаю.
IMHO, если бы был конкретный пример было бы на много понятнее так ли это удобно, как тебе кажется...

Вот в том же примере с тремя корзинками с грибамИ, люди как-то обходятся без создания "обощённой корзинки".
Ещё неочевидна эффективность такого подхода, кстати...

DS>range — нужен как альтернативный подход к склейке алгоритмов и контейнеров в STL.

Не понятно зачем это всё-таки надо. IMHO, единственный вменяемый пример -- это параллельные массивы, что в свою очередь очень сомнительная практика

Опять же. А что будет, если я напишу что-то типа

sort(chain(v1, chain( v2, v1 )));

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

E>IMHO, если бы был конкретный пример было бы на много понятнее так ли это удобно, как тебе кажется...
Есть три очереди запросов. Нужно перебросить максимально возможное количество определенных запросов в первую очередь, а не соответствующие — перераспределить по оставшимся. Критерий отбора — использование ресурсов A,B,C. Веса по ресурсам: 0.7, 0.2, 0.1. Запросы могут сообщать об используемых ресурсах.
Да, и мне не кажется. Это мое мнение (мне нравится идея ranges), и я его аргументирую.

E>Вот в том же примере с тремя корзинками с грибамИ, люди как-то обходятся без создания "обощённой корзинки".
"Обобщенный стол" их выручает?
E>Ещё неочевидна эффективность такого подхода, кстати...
Т.е.? Есть способ эффективнее?

E>Не понятно зачем это всё-таки надо. IMHO, единственный вменяемый пример -- это параллельные массивы, что в свою очередь очень сомнительная практика
Динамическое создание структур данных в C++ пока даже не предвидется.

E>Опять же. А что будет, если я напишу что-то типа

sort(chain(v1, chain( v2, v1 )));

Делить на ноль не запретишь... Хотя у chain и достаточно данных, чтобы отловить такую последовательность, но принимать решение о некорректности может только функция sort: если это требуется, например, отправить на ostream, то все как раз именно так и должно быть. Впрочем, 0 тоже можно на ostream.

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

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

E>>IMHO, если бы был конкретный пример было бы на много понятнее так ли это удобно, как тебе кажется...
DS>Есть три очереди запросов. Нужно перебросить максимально возможное количество определенных запросов в первую очередь, а не соответствующие — перераспределить по оставшимся. Критерий отбора — использование ресурсов A,B,C. Веса по ресурсам: 0.7, 0.2, 0.1. Запросы могут сообщать об используемых ресурсах.

Не понял при чём тут ресурсы и веса. Типа есть три лиги, первая, вторая и третья. При этом число мест в каждой фиксировано. И надо типа перебросить самых лучших в первую лигу из второй и третьей? Такая задача?
Не понятно, зачем тут что-то с чем-то сливать, я не понимаю.
Например, было бы логично потребовать, чтобы те, кого переброска не затронула, сохранили бы свою лигу... На слитой последовательности, IMHO, сделать это не так-то и просто.
С другой стороны, если мы можем отсортировать каждую лигу, то решение тривиально: N-путевым слияением итерируем отсортированные три лиги и наводим порядок...

E>>Вот в том же примере с тремя корзинками с грибамИ, люди как-то обходятся без создания "обощённой корзинки".
DS>"Обобщенный стол" их выручает?

Да нет, вполне хорошо работает и такой подход, что достаем самое плохое из лучших, а их худших самое хорошее, и меняем..

E>>Ещё неочевидна эффективность такого подхода, кстати...
DS>Т.е.? Есть способ эффективнее?
Ну я так понимаю, что все эти объединённые диапазоны при доступе к каждому элементу будут злобно очень ветвиться, в то время, как алгоритм
1) отсортировать все три корзины
2) итерировать лучшую с конца, а остальные с начала пока есть кандидаты на обмен...

DS>Динамическое создание структур данных в C++ пока даже не предвидется.
Не совсем понятно зачем нужны динамически созданные структуры. Код-то пишется ещё ДО КОМПИЛЯЦИИ?

DS>Делить на ноль не запретишь... Хотя у chain и достаточно данных, чтобы отловить такую последовательность, но принимать решение о некорректности может только функция sort: если это требуется, например, отправить на ostream, то все как раз именно так и должно быть. Впрочем, 0 тоже можно на ostream.

Ну это к тому, что легко граблей напрогать, а как проверить напрогали ли граблей -- не ясно

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

E>>А зачем это всё нужно?
DS>Александреску:
DS>

DS>Range-based design offers much more than a port of iterator-based functions to ranges

Ну типа ещё и пирожки печёт что ли?
Какие конкретно задачи будут лучше решаться-то? Есть какие-то неумозрительные примеры?

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

E>Не понял при чём тут ресурсы и веса.
Критерий сотрировки как бы. Но это так, чтобы не скучно было. Концептуально — не при чем.

E>Типа есть три лиги, первая, вторая и третья. При этом число мест в каждой фиксировано. И надо типа перебросить самых лучших в первую лигу из второй и третьей? Такая задача?
Да, лучших по определенному критерию.

E>Не понятно, зачем тут что-то с чем-то сливать, я не понимаю.
У нас всего 60 игроков. Надо в первую лигу запихнуть 20 лучших. В таком виде задача реализуется за один вызов partial_sort. Значит, нам осталось только собрать вместе 60 игроков, что мы и делаем, указывая в качестве второго range chain(liga2,liga3);
E>Например, было бы логично потребовать, чтобы те, кого переброска не затронула, сохранили бы свою лигу... На слитой последовательности, IMHO, сделать это не так-то и просто.
насколько я знаю, partial_sort не занимается лишними перестановками.
E>С другой стороны, если мы можем отсортировать каждую лигу, то решение тривиально: N-путевым слияением итерируем отсортированные три лиги и наводим порядок...
3 сортировки + 1 самописный алгоритм вместо вызова одной функции разбиения? Тогда давайте говорить за эффективность,
количество кода, скорость написания и отладки.

Вот примерный вариант c использованием ranges:

#include <...>
using namespace std;

void MoveBests( vector<player>& liga1, 
                deque<player>& liga2, 
                deque<player>& liga3,
                boost::finction< bool ( const player& , const player& ) > crit )
{ 
     partial_sort( liga1, chain( liga2, liga3 ), crit );
}

И, кстати, судя по частоте употребления слова "слияние", вы под ним что-то нехорошее подразумеваете. Что-то вроде копирования контейнеров. Этого нет. Под слиянеим понимается объединение двух ranges в один новый range.

E>Да нет, вполне хорошо работает и такой подход, что достаем самое плохое из лучших, а их худших самое хорошее, и меняем..
По-подробнее пожалуйста. Потому как задачи (лиги,лукошки) эквивалентны, а ваши решения -- нет.
E>Ну я так понимаю, что все эти объединённые диапазоны при доступе к каждому элементу будут злобно очень ветвиться, в то время, как алгоритм
E>1) отсортировать все три корзины
E>2) итерировать лучшую с конца, а остальные с начала пока есть кандидаты на обмен...
Не думаю, что что-то может сильно ветвиться в partial_sort, уж больно стандартный алгоритм. Время работы O(sz1*log(sz2+sz3)).

DS>>Динамическое создание структур данных в C++ пока даже не предвидется.
E>Не совсем понятно зачем нужны динамически созданные структуры. Код-то пишется ещё ДО КОМПИЛЯЦИИ?
С установки может прийти от 1 до 15 потоков данных в double. Задача принять все активные потоки, и отсортировать данные по первому потоку.
Вариант 0. Динамически создать strct rec { doble r[n]; }; vector<rec> data;
n — имеется ввиду количество потоков данных. C++ этого не позволяет, так что остается либо разбазаривать память (в случае, если работают меньше 15 потоков):
Вариант 1. struct rec { double r[15]; }; vector<rec> data;
Либо поменять теплое и мягкое местами:
Вариант 2. struct data { vector<vector<double> > data; };
а это
E>> это параллельные массивы, что в свою очередь очень сомнительная практика
практика, может, и сомнительная. но пример я придумал.
E>Ну это к тому, что легко граблей напрогать, а как проверить напрогали ли граблей -- не ясно
lint и его производные дожны помочь. Но вот мне что-то подсказывает, что промахнуться мимо end все же проще.

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

E>Ну типа ещё и пирожки печёт что ли?
E>Какие конкретно задачи будут лучше решаться-то? Есть какие-то неумозрительные примеры?

Напишите ваше решение на итераторах для задачи про лиги. Решение для range я привел выше

Автор: Erop
Дата: 07.08.09

.

решение тут

Автор: Dmi3S
Дата: 07.08.09

. промахнулся.

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

DS>У нас всего 60 игроков. Надо в первую лигу запихнуть 20 лучших. В таком виде задача реализуется за один вызов partial_sort. Значит, нам осталось только собрать вместе 60 игроков, что мы и делаем, указывая в качестве второго range chain(liga2,liga3);

Есть такой известный алгоритм, которые позволяет итерировать несколько упорядоченных последовательностей так, словно это одна упорядоченная последовательность. Мне он известен под названием "N-путевое слияние"...

E>>Например, было бы логично потребовать, чтобы те, кого переброска не затронула, сохранили бы свою лигу... На слитой последовательности, IMHO, сделать это не так-то и просто.
DS>насколько я знаю, partial_sort не занимается лишними перестановками.
Да? А откуда partial_sort узнает, что перестановка между второй и третьей двадцатками "лишние"?
Как видишь, твой подход только запутывает...

DS>3 сортировки + 1 самописный алгоритм вместо вызова одной функции разбиения? Тогда давайте говорить за эффективность,
DS>количество кода, скорость написания и отладки.
3 сортировки вместо одной поверх объединённых регионов -- скорее всего будут шибко быстрее.
Самописный алгоритм нифига не самописный. Да и не сложный, к тому же..


DS>И, кстати, судя по частоте употребления слова "слияние", вы под ним что-то нехорошее подразумеваете. Что-то вроде копирования контейнеров. Этого нет. Под слиянеим понимается объединение двух ranges в один новый range.
Если ты хочешь обсудить меня, а не идеи о выгодности интервалов, то я так понимаю, что про интервалы уже всё ясно?

DS>По-подробнее пожалуйста. Потому как задачи (лиги,лукошки) эквивалентны, а ваши решения -- нет.
Да ладно, не эквивалентны. Пишем примерно такой цикл:

пока( худший из ещё не поменяных лучших хуже лучшего их ещё непоменяных худших ) 
    поменять (худшего из ещё непоменяных лучших и лучшего из ещё непоменяных худших )

Просто в корзинках лучшый и худший ищется "методом взгляда", а в лигах путём итерации первой лиги от худших к лучшим, а второй и третьей от лучших к худшим, методом двухпутевого слияния...

DS>Не думаю, что что-то может сильно ветвиться в partial_sort, уж больно стандартный алгоритм. Время работы O(sz1*log(sz2+sz3)).

Ветвиться будет не там, в внутри объединённого диапазона...
Если partial_sort будет работать поверх объединённого интервала, как поверх интервала массива, или интервала списка, например, то будет много ненужных переходов между контейнерами => всяких лишних ненужных проверок на выходы за границы...
А если partial_sort будет как-то специализирован на тему объединённых диапазонов, то это просто обозначает, что задачу о трёх лигах решат авторы библиотеки, а не ты.

DS>С установки может прийти от 1 до 15 потоков данных в double. Задача принять все активные потоки, и отсортировать данные по первому потоку.
Нереальная задача. И как это ёксель-то написать смогли?

DS>Вариант 0. Динамически создать strct rec { doble r[n]; }; vector<rec> data;
DS>n — имеется ввиду количество потоков данных. C++ этого не позволяет, так что остается либо разбазаривать память (в случае, если работают меньше 15 потоков):
E>>> это параллельные массивы, что в свою очередь очень сомнительная практика
DS>практика, может, и сомнительная. но пример я придумал.

Глупый пример. Давным-давно придуманы эффективные реализации 2-хмерных массивов для С++, которые, в том числе, позволяют легко переставлять как строки, так и столбцы. Вот их и надо использовать...

Кстати, как планируется решать эту задачу на диапазонах?

DS>lint и его производные дожны помочь. Но вот мне что-то подсказывает, что промахнуться мимо end все же проще.
Ну ты же рекламируешь не то, что мимо "end не промахнёшься", с этим как раз более или менее всё понятно. А то, что есть всякие рульные новые фичи, которых у итераторов просто нет?

Я же спросил "зачем надо писать partial_sort( chein( v1, v2 ) )?"...

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

DS>Напишите ваше решение на итераторах для задачи про лиги. Решение для range я привел выше

Автор: Erop
Дата: 07.08.09

.

Ну ты правда не знаешь, как оно пишется? Если не знаешь, могу написать. Даже не на итераторах, а просто на трёх массивах double, например Ещё можно написать и такую мульку, которая позволяет получать элементы двух отсортированных последовательностей в порядке общего возрастания...

Но лучше ты расскажи, как так таки решить задачу при лиги на диапазонах?

Итак
есть три лиги, надо достойных собрать в первую, вытолкнув недостойных во вторую и третью, но при этом не допустить переходов между второй и третьей...

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

E>Есть такой известный алгоритм, которые позволяет итерировать несколько упорядоченных последовательностей так, словно это одна упорядоченная последовательность. Мне он известен под названием "N-путевое слияние"...

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

E>Да? А откуда partial_sort узнает, что перестановка между второй и третьей двадцатками "лишние"?
partial_sort переставляет между двумя range. Первый range это liga1. Второй range это liga2+liga3. Есть мнениние что, во втором для partial_sort range взаимных перестановок не будет.
E>Как видишь, твой подход только запутывает...
Это не мой подход. Не надо мне ничего приписывать.

E>3 сортировки вместо одной поверх объединённых регионов -- скорее всего будут шибко быстрее.
Давайте без скорей всего, а с оценками в О-нотации. Для своего алгоритма я оценку привел.
E>Самописный алгоритм нифига не самописный. Да и не сложный, к тому же..
Хорошо. Если он есть в std или boost — можете его вызвать. Если нет — пишите.

E>Если ты хочешь обсудить меня, а не идеи о выгодности интервалов, то я так понимаю, что про интервалы уже всё ясно?
Как вас, так и "идеи о выгодности" я обсуждать не собираюсь.

E>Да ладно, не эквивалентны. Пишем примерно такой цикл:

пока( худший из ещё не поменяных лучших хуже лучшего их ещё непоменяных худших ) 
E>    поменять (худшего из ещё непоменяных лучших и лучшего из ещё непоменяных худших )

Три корзинки по 20 грибов. Собрать в одной лучшие из всех 60. На таком примитивном уровне обсуждения, задачи все еще не эквивалентны?

E>Просто в корзинках лучшый и худший ищется "методом взгляда",
"Метод взгляда" на полную корзинку не действует. Рентген сломался.
Кстати, как определять очередных лучших и худших среди грибов без рентгена? Случайно, не предварительной ли сортировкой?

E>а в лигах путём итерации первой лиги от худших к лучшим, а второй и третьей от лучших к худшим, методом двухпутевого слияния...
Пожалуйста, не XZ, а код в студию. С оценкой времени выполнения.

E>Ветвиться будет не там, в внутри объединённого диапазона...
Блджад, вы до сих пор не прочитали даже презентацию?! Мдя. И что мы тут обсуждаем? Выдуманные вами интервалы и итераторы?

E>Если partial_sort будет работать поверх объединённого интервала, как поверх интервала массива, или интервала списка, например, то будет много ненужных переходов между контейнерами => всяких лишних ненужных проверок на выходы за границы...
Это ваши фантазии.
E>А если partial_sort будет как-то специализирован на тему объединённых диапазонов, то это просто обозначает, что задачу о трёх лигах решат авторы библиотеки, а не ты.
Это значит, что задача о грибах была придумана под конкретное решение -- вызов partial_sort.

DS>>С установки может прийти от 1 до 15 потоков данных в double. Задача принять все активные потоки, и отсортировать данные по первому потоку.
E>Нереальная задача. И как это ёксель-то написать смогли?
Видимо, читали документацию.

E>Глупый пример. Давным-давно придуманы эффективные реализации 2-хмерных массивов для С++, которые, в том числе, позволяют легко переставлять как строки, так и столбцы. Вот их и надо использовать...
Там было волшебное слово. Сортировка. Впрочем, с чтением у вас не очень, что и показывает следующий вопрос:
E>Кстати, как планируется решать эту задачу на диапазонах?

E>Ну ты же рекламируешь не то, что мимо "end не промахнёшься", с этим как раз более или менее всё понятно. А то, что есть всякие рульные новые фичи, которых у итераторов просто нет?
Блджад. Я ни чего не рекламирую. Я высказываю свою точку зрения. Подкрепляю аргументами. Пытаюсь придумать какие то примеры. А потом выясняется, что из двух собеседников один даже не в курсе, о чем говорим. Глазги берег.

E>Я же спросил "зачем надо писать partial_sort( chein( v1, v2 ) )?"...
Блджад, так писать _нельзя_. По определению partial_sort.

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

DS>>>s/MoveNext/popFront
DS>>>, то полученный результат ничего не напомнит?

J>>С прямым итератором это действительно так.
J>>А вот у двунаправленного итератора будет еще и MovePrev — ы? Аналогично для итератора с произвольным доступом.
DS>Я как бы хотел узнать, можно ли исходную конструкцию назвать итератором, и чем она отличается от range. В возможности добавления туда игр и девушек я не сомневался
Так я и ответил (курсивом).
Но диапазоны же мыслятся как замена всех итераторов, а не только прямых.

J>>Концепция "диапазоны можут только уменьшаться" выглядит довольно сильно ограничивающей, когда мы переходим к итерациям.
DS>Да, с использованием списков итерирование фактически невозможно. Это же начальные условия.
Ну так и смысл тогда убивать итераторы?

DS>Я вообще как-то плохо понимаю: такое ощущение, что все старательно подходят с молотком к новому шурупу, и делают соответствующие выводы.
Потому что изобретатель шурупа настаивает, что молотки больше не нужны.
А ему говорят, что молотки еще много где пригодятся.

DS>Неужели ни кому не нравится вот такая возможность:
да нравится, нравится, разве я про нее хоть слово против сказал? Наоборот же, все время говорю, что когда мы делаем что-то в терминах диапазонов, то и в коде это должно так же выражаться.
Другое дело, что мы не всё делаем в терминах диапазонов, и от этого не денешься никуда.

DS>PS. Посмотрел на boost::zip_iterator. Сомневаюсь, что читаемый аналог второго примера влезет в экран.
Ну это как раз не проблема:

vector<double> vd;
vector<string> vs;
deque<int>     vi;
// sort the three in lockstep
sort(
  make_zip_iterator( make_tuple(vs.begin(), vd.begin(), vi.begin()) ),
  make_zip_iterator( make_tuple(vs.end(),   vd.end(),   vi.end()  ) )
);

Все вполне читаемо и всюду влезает.
Сам понимаешь, что написать версию make_zip_iterator с переменным числом параметров (просто скопировав интерфейс make_tuple), а потом упаковать пару make_zip_iterator в make_zip_range не проблема — тогда все вообще превратится в одну строчку.

Но конкретно этот пример компилироваться не будет, по другим причинам (это проблема со всеми итераторами, которые возвращают ad-hoc-прокси) — они по стандарту должны возвращать ссылку, а не что-либо еще, что фактически убивает возможность прокси-итераторов (похоже, о них просто не думали, когда писали требования в стандарте). Но это проблема конкретной спецификации, ее несколько раз пытались поменять уже, в т.ч. из буста. Это известная проблема, можешь почитать, например, здесь: http://lists.boost.org/Archives/boost/2004/07/68758.php, там же предложен пример, как это обойти.


З.Ы. Просто Александреску занимается экстремизмом: "Смерть итераторам, всё на диапазонах!", а ты как будто подозреваешь в аналогичном экстремизме нас "Смерть диапазонам, всё на итераторах!", хотя мы все на самом деле говорим: "Диапазоны будут отличным дополнением к итераторам".

You will always get what you always got
  If you always do  what you always did

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

DS>>Да, с использованием списков итерирование фактически невозможно. Это же начальные условия.
J>Ну так и смысл тогда убивать итераторы?
Избавиться от итерирования. Это имхо и было отправной точкой, судя по первым слайдам.

J>Потому что изобретатель шурупа настаивает, что молотки больше не нужны.
J>А ему говорят, что молотки еще много где пригодятся.
Я, конечно, не могу высказывать что-то от имени изобретателя, но кажется, что предложение было несколько иного рода. Предлагалось заменить гвозди с молотками на шурупы с отвертками. Врочем, это исключительно предположение. Да и материалов по теме пока мало. Только доки по D, да презентация.

DS>>Неужели ни кому не нравится вот такая возможность:
J>да нравится, нравится, разве я про нее хоть слово против сказал?
Не то чтобы против, но вот это заставило напрячь извилины

DS>>Что нового привносит данная концепция?
J>Имхо — ничего, если принимать во внимание существование Boost.Range.

J>Наоборот же, все время говорю, что когда мы делаем что-то в терминах диапазонов, то и в коде это должно так же выражаться.
Александреску именно это и сказал. Про STL.
J>Другое дело, что мы не всё делаем в терминах диапазонов, и от этого не денешься никуда.
А вот про это он промолчал


DS>>PS. Посмотрел на boost::zip_iterator. Сомневаюсь, что читаемый аналог второго примера влезет в экран.

J>Ну это как раз не проблема:
J>

J>vector<double> vd;
J>vector<string> vs;
J>deque<int>     vi;
J>// sort the three in lockstep
J>sort(
J>  make_zip_iterator( make_tuple(vs.begin(), vd.begin(), vi.begin()) ),
J>  make_zip_iterator( make_tuple(vs.end(),   vd.end(),   vi.end()  ) )
J>);
J>

J>Все вполне читаемо и всюду влезает.
А корректная ли функция сравнения будет использована? Судя по презентации, сравниваются между собой только строки. Я, когда говорил об экране, намекал как раз на нехилое определение этой фунции.

J>Но конкретно этот пример компилироваться не будет, по другим причинам (это проблема со всеми итераторами, которые возвращают ad-hoc-прокси) — они по стандарту должны возвращать ссылку, а не что-либо еще, что фактически убивает возможность прокси-итераторов (похоже, о них просто не думали, когда писали требования в стандарте). Но это проблема конкретной спецификации, ее несколько раз пытались поменять уже, в т.ч. из буста. Это известная проблема, можешь почитать, например, здесь: http://lists.boost.org/Archives/boost/2004/07/68758.php, там же предложен пример, как это обойти.

И это уже 5 лет тянется? Мдя... Ну да ладно, мы пока о концепциях: в плане реализации, ranges вообще только в другом языке существуют.

J>З.Ы. Просто Александреску занимается экстремизмом: "Смерть итераторам, всё на диапазонах!",
Да, и это изрядно веселит . Очень каардинальная смена парадигмы для весомой части C++.

J> а ты как будто подозреваешь в аналогичном экстремизме нас "Смерть диапазонам, всё на итераторах!", хотя мы все на самом деле говорим: "Диапазоны будут отличным дополнением к итераторам".
Нет, ни кого не подозреваю. Я пытаюсь найти что-то новое, что можно легко сделать на диапазонах, и не очень комфортабельно на итераторах.

PS. Для ясности повторюсь. Мне просто понравилась идея и подход Александреску . Она (идея) пока что не кажется жизнеспособной, но от этого красивой быть не перестает.

DS>А корректная ли функция сравнения будет использована? Судя по презентации, сравниваются между собой только строки. Я, когда говорил об экране, намекал как раз на нехилое определение этой фунции.
Перечитал еще раз слайды. Ни где нет упоминания о том, каким именно способом сортируются zip-ы. Так что, думаю, мне показалось при первом чтении, что будет именно так.

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

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

DS>>>Да, с использованием списков итерирование фактически невозможно. Это же начальные условия.
J>>Ну так и смысл тогда убивать итераторы?
DS>Избавиться от итерирования. Это имхо и было отправной точкой, судя по первым слайдам.
Ну да, только он же и сам в конце презентации при обсуждении говорит, что его концепция не будет работать, если мы шли-шли по диапазону вперед, а потом вдруг решили повернуть назад.
Так что он и сам все прекрасно понимает.

J>>Потому что изобретатель шурупа настаивает, что молотки больше не нужны.
J>>А ему говорят, что молотки еще много где пригодятся.
DS>Я, конечно, не могу высказывать что-то от имени изобретателя, но кажется, что предложение было несколько иного рода. Предлагалось заменить гвозди с молотками на шурупы с отвертками. Врочем, это исключительно предположение. Да и материалов по теме пока мало. Только доки по D, да презентация.

Мне кажется, что он хочет сказать следующее: весь STL можно переформулировать на диапазонах.
Вроде как, в основном с этим тезисом согласны.
Не знаю, воспринимать ли его тезис как "и все остальное, не только СТЛ, можно тоже на них же сделать и забить на итераторы окончательно". Если это действительно то, что он хотел сказать, то это экстремизм. Если нет — то я не спорю тогда.

DS>>>Неужели ни кому не нравится вот такая возможность:
J>>да нравится, нравится, разве я про нее хоть слово против сказал?
DS>Не то чтобы против, но вот это заставило напрячь извилины
DS>

DS>>>Что нового привносит данная концепция?
J>>Имхо — ничего, если принимать во внимание существование Boost.Range.

Ну да. То, что он называет диапазонами, во многих других местах называется view.
И ничего тут принципиально нового нету.
Вот, например:
http://www.boost.org/libs/mpl/doc/refmanual/views.html
http://www.boost.org/libs/fusion/doc/html/fusion/view.html
Все это появилось до Александреску.
И я думаю, каждый уже успел написать свой собственный filtered_view и substring.

J>>Другое дело, что мы не всё делаем в терминах диапазонов, и от этого не денешься никуда.
DS>А вот про это он промолчал
ну, это он на слайдах промолчал, а на видео ему кучу вопросов поназадавали на эту тему, и он практически со всем согласился.

DS>>>PS. Посмотрел на boost::zip_iterator. Сомневаюсь, что читаемый аналог второго примера влезет в экран.

J>>Ну это как раз не проблема:
J>>

J>>vector<double> vd;
J>>vector<string> vs;
J>>deque<int>     vi;
J>>// sort the three in lockstep
J>>sort(
J>>  make_zip_iterator( make_tuple(vs.begin(), vd.begin(), vi.begin()) ),
J>>  make_zip_iterator( make_tuple(vs.end(),   vd.end(),   vi.end()  ) )
J>>);
J>>

J>>Все вполне читаемо и всюду влезает.
DS>А корректная ли функция сравнения будет использована? Судя по презентации, сравниваются между собой только строки.
Я не знаю, что там у него в D.
Boost.Tuple сравниваются лексикографически (т.е. сначала первый элемент, если одинаковые, то второй, и т.д.)

DS>Я, когда говорил об экране, намекал как раз на нехилое определение этой фунции.
С чего ему быть нехилым? Как раз наоборот (не компилировал, пишу в браузере):

struct less_by_first_element
{
  template <class T>
  bool operator()(const T& lhs, const T& rhs) const {
    return std::less( lhs.get<0>(), rhs.get<0>() );
  }
};

DS>И это уже 5 лет тянется? Мдя... Ну да ладно, мы пока о концепциях: в плане реализации, ranges вообще только в другом языке существуют.
Ну да.
бустовцы уже представляли это дело комитету, примерно в таком виде:
http://www.boost.org/libs/iterator/doc/new-iter-concepts.html

DS>Нет, ни кого не подозреваю. Я пытаюсь найти что-то новое, что можно легко сделать на диапазонах, и не очень комфортабельно на итераторах.
Ну, все операции над диапазонами, где итераторы не являются основной вещью, а являются просто средством построить один диапазон из другого, в принципе, в итераторах не нуждаются, это просто деталь реализации. И зачастую есть способы сделать многие преобразования непосредственно, не переходя явно на уровень итераторов и обратно.

DS>PS. Для ясности повторюсь. Мне просто понравилась идея и подход Александреску . Она (идея) пока что не кажется жизнеспособной, но от этого красивой быть не перестает.
Ну это да, хотя радикально нового я не вижу, все это очень давно уже обсуждается.
Вот, например, Boost.RangeEx (еще не в официальной поставке):
http://lists.boost.org/Archives/boost/2009/02/148682.php
можно будет писать нечто вроде

container | boost::adaptors::filtered(_1==0) | | boost::adaptors::reversed

You will always get what you always got
  If you always do  what you always did

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

DS>Давайте перед употреблением названий и терминов их хотя бы понимать.
Давай будем взаимовежливы? Либо снизь тон, и общайся, так, что с тобой будет приятно болтать о преимуществах диапазонов, либо я не буду с тобой вести беседу...
В частности, я буду пользоваться той терминологией, к которой привык, но ты можешь пользоваться той, к которой привык ты. Это не повод для взаимных наездов, главное разъяснить термины, чтобы не было взаимного недопонимания...

E>>Да? А откуда partial_sort узнает, что перестановка между второй и третьей двадцатками "лишние"?
DS>partial_sort переставляет между двумя range. Первый range это liga1. Второй range это liga2+liga3. Есть мнениние что, во втором для partial_sort range взаимных перестановок не будет.
Да? А на чём оно основано? Мы про аналог вот этого partial_sort

Rearranges the elements in the range [first,last), in such a way that the subrange [first,middle) contains the smallest elements of the entire range sorted in ascending order, and the subrange [middle,end) contains the remaining elements without any specific order.

говорим? AFAIK, выделенная фраза обозначает, что никаких гарантий рорядка в "хвосте" последовательности std::partial_sort НЕ ДАЁТ!
Если мне не изменяет память, то в STL есть ещё stable_partition и stable_sort, которые сохраняют порядок, но они делают не то. Кроме того они ещё и дороже...

E>>Как видишь, твой подход только запутывает...
DS>Это не мой подход. Не надо мне ничего приписывать.
Извини, "подход, который тебе нравится в этой задаче только запутывает" -- так хорошо?

E>>3 сортировки вместо одной поверх объединённых регионов -- скорее всего будут шибко быстрее.
DS>Давайте без скорей всего, а с оценками в О-нотации. Для своего алгоритма я оценку привел.
Да? Интересно какую?
AFAIK, у partial_sort асимптотическая сложность О( N ln N ), а у трёх sort -- то же O( N ln N ), а у N-путевого слияния сложность вообще линейная... Так что асимптота у них одинаковая. Вопрос в величине коэффициента и в том, насколько асимптота начинает работать при N = 20

E>>Самописный алгоритм нифига не самописный. Да и не сложный, к тому же..
DS>Хорошо. Если он есть в std или boost — можете его вызвать. Если нет — пишите.
А если он есть в тех библиотеках, которыми ПОЛЬЗУЮСЬ я?

E>>Да ладно, не эквивалентны. Пишем примерно такой цикл:

пока( худший из ещё не поменяных лучших хуже лучшего их ещё непоменяных худших ) 
E>>    поменять (худшего из ещё непоменяных лучших и лучшего из ещё непоменяных худших )

DS>Три корзинки по 20 грибов. Собрать в одной лучшие из всех 60. На таком примитивном уровне обсуждения, задачи все еще не эквивалентны?
Эквивалентны. Я же написал тебе одинаковое решение для обеих?
E>>Просто в корзинках лучшый и худший ищется "методом взгляда",
DS>"Метод взгляда" на полную корзинку не действует. Рентген сломался.
Тогда корзинка не может обеспечить random_access, и к обсуждаемой задаче прямого отношения не имеет
Ты правда, что ли, для того, чтобы найти "лучший из 20 грибов" их сортируешь? Надеюсь используешь алгоритм с ассимптотой O( N log N ), а не пузырёк какой-нибудь

E>>а в лигах путём итерации первой лиги от худших к лучшим, а второй и третьей от лучших к худшим, методом двухпутевого слияния...
DS>Пожалуйста, не XZ, а код в студию. С оценкой времени выполнения.

Сначала снизь тон... Ты же мне не платишь, что бы код требовать? Я понимаю, если не понятно, что нужно написать, но тут-то тебе наверное всё понятно?

E>>Ветвиться будет не там, в внутри объединённого диапазона...
DS>Блджад, вы до сих пор не прочитали даже презентацию?! Мдя. И что мы тут обсуждаем? Выдуманные вами интервалы и итераторы?

А я обсуждаю С ТОБОЙ, ТВОИ заверения, о том, что диапазоны рулят и дают мегавозможности. Собственно мне интересно ЗАЧЕМ ОНИ НУЖНЫ? Это же твоё мнение, что это надо и полезно? Ну вот и продемонстрируй, пожалуйста, чем это так полезно и хорошо и ЗАЧЕМ ЭТО НАДО?
Я видел слайды, там ничего содержательного про реализацию не видел. документ в PDF у меня не открывается. Если тебе кажется, что там есть что-то содержательное -- процитируй, пожалуйста...
Я не спорю с тем, что для всяких мест, где мы передаём ПАРУ итераторов, естественнее было бы передавать диапазон.
Но, обрати внимание, что в приведённом тобой, в качестве примера partial_sort в качестве аргумента передаётся ТРОЙКА итераторов. Так что, IMHO, как раз partial_sort выражать в терминах диапазонов довольно противоестественно

DS>Это ваши фантазии.
Ну поясни, как это будет работать-то?
Если вся мощь диапазонов сводится к тому, что можно сделать функцию chain, то на итераторах тоже можно. Просто будет две функции: chain_begin( TIterator1 begin1, TIterator1 end1, TIterator2 begin2 ) и chain_end( TIterator1 end1, TIterator2 begin2, TIterator2 end2 )...

Но, так как partial_sort требует random_access, то будет куча обращений вида *(chain_begin + shift), соответсвенно, в каждом таком обращении надо будет ветвиться для выбора между диапазонами...

DS>Это значит, что задача о грибах была придумана под конкретное решение -- вызов partial_sort.
Ну это полностью лишает твой пример доказательной силы.
1) Задача явно не очень актуальная и распространённая
2) На самом деле твой алгоритм её не решает, так как не обеспечивает непереход между второй и третьей лигами

DS>>>С установки может прийти от 1 до 15 потоков данных в double. Задача принять все активные потоки, и отсортировать данные по первому потоку.
E>>Нереальная задача. И как это ёксель-то написать смогли?
DS>Видимо, читали документацию.
К чему? К ненаписанному D?

E>>Глупый пример. Давным-давно придуманы эффективные реализации 2-хмерных массивов для С++, которые, в том числе, позволяют легко переставлять как строки, так и столбцы. Вот их и надо использовать...
DS>Там было волшебное слово. Сортировка.
Да, и что?
1) в ёкселе есть сортировка по любой комбинации столбцов
2) Реализация матрицы, в которой быстро вставляются/удаляются/сортируются, как строки, так и столбцы -- тема давно проработанная. Например, тут была статья...

DS>Впрочем, с чтением у вас не очень,
Э-э-э, вот от "подколок" такого типа и хотелось бы уйти. Я могу быть вообще маразматиком и моральным уродом с отрицательным IQ. Даже в этом случае, это никак не продемонстрирует достоинств подхода с диапазонвми.
Если ты хочешь обсуждать С++ -- давай обсуждать С++. А если ты хочешь обсудить меня, то я про себя и так всё знаю, в ты меня, скорее всего, совсем не знаешь, так что я лучше себя с женой и детьми обсужу, ты в этой области некомпетентен, IMHO...

DS>что и показывает следующий вопрос:
E>>Кстати, как планируется решать эту задачу на диапазонах?
Да? Ну так и как реализовать-то?
Вот у меня есть динамически определяемое число последовательностей. Ну, например std::vector<std::vector<double> >.
И как мне при помощи диапазонов отсортировать эту таблицу по третьей колонке, например?..

E>>Ну ты же рекламируешь не то, что мимо "end не промахнёшься", с этим как раз более или менее всё понятно. А то, что есть всякие рульные новые фичи, которых у итераторов просто нет?
DS>Пытаюсь придумать какие то примеры.
К сожалению, пока что, примеры не убеждают в полезности подхода. Во всяком случае меня...

E>>Я же спросил "зачем надо писать partial_sort( chain( v1, v2 ) )?"...
DS>Блджад, так писать _нельзя_. По определению partial_sort.
Ну я думаю, что ты понял, что я имел в виду.
Тем более, что вопрос я тебе уже выше по ветке задавал...
На всяк. случай:

Зачем нужно уметь писать: partial_sort(d, chain(v1, v2))?