VB обогнал C++

> По поводу iterators и for_each смотри сюда: #include <algorithm>. А твой дичайший код, есть явное незнание STL.

Когда в C++ появятся замыкания, тогда и приходи со своим for_each. :)

А по поводу дичайшего кода... Давай лучше вспомним, что C++ не позволяет даже cделать std::vector<int> v = {1, 2, 3}. :-P Кастыль твои плюсы, а STL — вдвойне кастыль.

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

>Что произойдет в этом случае со smart pointer'ами? Правильно, cyclic references -> memory leak. То, что у вас этого не возникало, говорит об одном из двух: либо отсутствовали достаточно сложные задачи, либо человек делал работу машины по разруливанию управления памятью.

Вы просто С++ незнаете, потому и думаете так примитивно, STL это главная часть С++. Незнаете STL, незнаете С++ - все ваши выпады простой пердёж.

Я нашел тест который эти вруны из Clean использовали для бинарного дерева :) боже-мой :) я плакаль :) Там обычным контейнером std::set обойтись можно было.

Для вашей задачи точно-так-же 2 варианта решения:

1. std::multiset где first ИД-узла. 2. boost::multi_index, который кстати уже в ТR1 tr1::multi_index.

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

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

> std::vector<int> v = {1, 2, 3} А зачем это надо вообще ?

> А зачем это надо вообще ?

Ровно затем же, зачем int a[3] = {1, 2, 3}.

> эти вруны из Clean

Эти вруны не из Clean, а из Debian. :)

И std::set там не использовали, видимо, потому, что бенчмарк. Предложи им свой код, если считаешь, что он будет работать быстрее.

> Ровно затем же, зачем int a[3] = {1, 2, 3}.

Тогда непонятно почему бы не использовать int a[3] = {1, 2, 3} Потом потребность в этой ерунде - настолько редкая ситуация, что серьезным аргументом против Си++ не является. По крайней мере для меня

>А по поводу дичайшего кода... Давай лучше вспомним, что C++ не позволяет даже cделать std::vector<int> v = {1, 2, 3}. :-P Кастыль твои плюсы, а STL — вдвойне кастыль.

Повторяю для тупых: если вы незнаете или нелюбидте СТЛ, значит вы незнаете С++, и все Ваши нарекания - чистейший пердёж.

>Как я рад что плюсы и перл дохнут. Жаба пых пых и вб следующие :-Е

Популярность пыхпыха падает, а вот популярность жабы (и вб) - растёт.

>Видели поддерживаемый софт на lisp хотя бы в пол милиона стрчоек?

Т.е. эквивалент, эдак, десяти миллионам строк на Си++? :)

>О результатах компиляции расскажите дня через 2.

$ g++ test.cpp 
test.cpp:7: ошибка: expected primary-expression before ‘:’ token
test.cpp:7: ошибка: pure-specifier on function-definition
test.cpp:7: ошибка: некорректная декларация элемента-функции
test.cpp:13: ошибка: ‘x’ не является элементом ‘K17<0, 0, int>’

gcc версия 4.1.2 20070214 (  (gdc 0.24, using dmd 1.020)) (Gentoo 4.1.2 p1.0.1)

>А любителям чистого Си:

$ time gcc test.c 

real    0m19.826s
user    0m17.533s
sys     0m0.635s

>И std::set там не использовали, видимо, потому, что бенчмарк. Предложи им свой код, если считаешь, что он будет работать быстрее.

В том то и дело что они не хотят, чтоб на С++ работало быстрее. Они неиспользуют стандартную реализацию из STL, и не потому, что о ней незнают, а потому-что называют ее читерской, она понимаешь ли быстрее работает :)

За стандартной реализацией обращаться в #include <bits/stl_tree.h>, однако рекомендую использовать стандартные контейнеры которые пользуются этим деревом.

В подтверждение моих слов выдержка с дубиновского (Debian) сайта:

diff program output N = 10 with this 1KB output file to check your program is correct before contributing.

Each program should

* define a tree node class and methods, a tree node record and procedures, or an algebraic data type and functions, or… * allocate a binary tree to 'stretch' memory, check it exists, and deallocate it * allocate a long-lived binary tree which will live-on while other trees are allocated and deallocated * allocate, walk, and deallocate many bottom-up binary trees o allocate a tree o walk the tree nodes, checksum node items (and maybe deallocate the node) o deallocate the tree * check that the long-lived binary tree still exists

Note: this is an adaptation of a benchmark for testing GC so we are interested in the whole tree being allocated before any nodes are GC'd - which probably excludes lazy evaluation.

Note: the left subtrees are heads of the right subtrees, keeping a depth counter in the accessors to avoid duplication is cheating!

Note: the tree should have tree-nodes all the way down, replacing the bottom nodes by some other value is not acceptable; and the bottom nodes should be at depth 0.

Link забыл: http://shootout.alioth.debian.org/gp4/benchmark.php?test=binarytrees&lang...

> Вы просто С++ незнаете, потому и думаете так примитивно, STL это главная часть С++. Незнаете STL, незнаете С++ - все ваши выпады простой пердёж.

Я знаю русский, он сложнее. "НЕ" с глаголами пишется раздельно.

> 1. std::multiset где first ИД-узла. 2. boost::multi_index, который кстати уже в ТR1 tr1::multi_index.

Как я и говорил, выкидываем smart pointer'ы и храним полный список объектов, чтобы удалять их скопом вручную. Хотя, стойте, для этого достаточно std::list или std::vector... О нет! Мне предлагают вместо smart pointer'ов хранить id и при каждом обращении делать поиск O(log(n)) вместо доступа по указателю O(1). И эти люди будут мне рассказывать о тормозах GC?

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

Когда я читаю и пишу на C++, я тоже думаю, что не испытываю затруднений. Однако, время от времени я пишу на других языках аналоги того, что пишу на C++, для сравнения. И тогда я понимаю, насколько же мне мешают эти уродливые итераторы.

> Наверное я что-то недогоняю в STL.

Зависит от привычки и самого кода. Если использование итераторов ограничивается for( i=v.begin(); i!=v.end(); ++i ), то разницы, конечно, нет. Однако, возьмем простой случай: есть вышеприведенный цикл по вектору, в нем производятся некоторые действия над *i. Произошел небольшой рефакторинг и вместо вектора у нас теперь map и нам надо выполнить этот цикл по значениям (без ключей) из map'ы. Как нам получить итератор по second'ам map'ы, чтобы не трогать тело цикла? (про boost::transform_iterator я в курсе, но ведь boost еще не стандарт).

>Я знаю русский, он сложнее. "НЕ" с глаголами пишется раздельно.

Об опечатках слышать приходилось ? Придераться к правописанию в данном контексте, по меньшей мере неуместно.

>Как я и говорил, выкидываем smart pointer'ы и храним полный список объектов, чтобы удалять их скопом вручную. Хотя, стойте, для этого достаточно std::list или std::vector... О нет! Мне предлагают вместо smart pointer'ов хранить id и при каждом обращении делать поиск O(log(n)) вместо доступа по указателю O(1). И эти люди будут мне рассказывать о тормозах GC?

Гонишь. [ вместо доступа по указателю O(1) ]:

1. Этот указатель тебе сначала найти нужно, иначе вся каша смысла не имеет. Естественно после того как ты нашел новую ветку по указателю будет О(1). Хочешь удалять целыми ветками используй multi_index. Или в конце концов чистый _Rb_tree.

2. В том тесте, который на дубиновском сайте, полный траверсал по дереву.

Пример еще одной реализации на С++, неакцептированый, но обогнавший референс на 80% т.к. плейсмент выделение использует:

NOT ACCEPTED http://shootout.alioth.debian.org/gp4/benchmark.php?test=binarytrees&lang...

std::set - Erasing an element from a set also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

it_first=mSet.lower_bound(key_lower); it_second=mSet.upper_bound(key_upper);

if(it_first!=mSet.end()) { mSet.erase(it_first,it_second); // remove branch. }

>anonymous (*) (21.11.2007 19:39:31) Все то-же самое для мап,мултимап,мултисет и мултииндекс.

Заразился на этом вашем ЛОРе, сначала пишу всякую хрень, потом думаю ...

> Об опечатках слышать приходилось ? Придераться к правописанию в данном контексте, по меньшей мере неуместно.

Об уважении к собеседнику слышать приходилось?

1. Поставь проверяльщик орфографии.

2. Не переходи на личности, оставайся в теме разговора.

> 1. Этот указатель тебе сначала найти нужно, иначе вся каша смысла не имеет. Естественно после того как ты нашел новую ветку по указателю будет О(1). Хочешь удалять целыми ветками используй multi_index. Или в конце концов чистый _Rb_tree.

Они хранятся в массиве/списке/отдельных полях (в зависимости от потребностей) в каждом объекте-узле. Доступ -- O(1) (у списков тоже, для случая полного перебора соседей). Суммарная трудоемкость = O(1)+O(1)=O(1).

При чем тут _Rb_tree, я вообще не вкурил, если речь идет о _произвольном_графе_, а не о дереве (с деревом все просто, как раз).

> 2. В том тесте, который на дубиновском сайте, полный траверсал по дереву.

При чем тут тест? Напомню, мы говорим о smart pointer'ах и о том, что "GC -- это костыль". Кстати, smart pointer -- частный случай этого самого GC, причем один из худших. Интересно проверить производительность того кода, "в котором давно ни одного delete" с эквивалентом на языке с нормальным GC.

>Об уважении к собеседнику слышать приходилось? >2. Не переходи на личности, оставайся в теме разговора. Вот-вот.

>в каждом объекте-узле. Доступ -- O(1)

Обоснуй О(1) для произвольного доступа или для поиска.

Итеративно, траверсал от i к i+-1 - О(1). Все остальное это твоя больная фантазия.

>у списков тоже, для случая полного перебора соседей

Бред больного воображения. Перебор списка занимает леинейнаое время. Я не пойму почему ты вообще отдельные итерации рассматриваешь ? :)

>При чем тут тест?

С него начался разговор о преимуществах GC

>Напомню, мы говорим о smart pointer'ах и о том, что "GC -- это костыль".

Это я утверждаю до сих пор. Всё что нужно это: Выделение на стэке, std::auto_ptr и tr1::shared_ptr, если tr1 поддержка отсутствует, то boost::shared_ptr.

>Кстати, smart pointer -- частный случай этого самого GC, причем один из худших.

Единственный нормальный.Судя по твоим постам у тебя недостаточно квалификации что-бы вообще этот разговор вести.

Всё остальное в твоем посте чистая троллятина, и коментировать оную я не стану.

> Я не пойму почему ты вообще отдельные итерации рассматриваешь ? :)

Объясняю, мне надо перебрать всех соседей, укзазтели в списке. Переход к следующему -- O(1), переход по указателю -- O(1), в сумме, естественно, O(n). Если храним id -- переход к следующему -- O(1), поиск по id в общей map'е -- O(log(n)), в сумме -- O(m*log(n)). Разницу чувствуешь?

> Всё остальное в твоем посте чистая троллятина, и коментировать оную я не стану.

Бе-бе-бе, ну и ладно, я тоже с тобой не играю. Вот. Все равно ты даже разницы в троемкости перехода по указателю и поиска по map'у не видишь.

>Если храним id -- переход к следующему -- O(1), поиск по id в общей map'е -- O(log(n)), в сумме -- O(m*log(n)). Разницу чувствуешь?

Ну нельзя же быть таким бараном ! Повторяю в списке у тебя линейная трудоёмкость на произвольный доступ, поиск и удаление O(N)=N, произвольный доступ к ассоциативному контейнеру и посик в нем (map,set) O(N)=log(N) (эта форма записи во всех иностранных источниках подразумевает логарифм по основанию 10). Удаление ветки из контейнера вышеуказаным способом O(N)=N. Ты с арифметикой дружишь ? Что больше N или log(N) ?

> O(N)=log(N)

П-ц, господа. В дурдоме дом открытых дверей? Или ты, убогонький, не знаком даже с матанализом в объёме первого семестра первого курса? Умри в корчах и на засоряй топик своим бредом.

man Символы Ландау, чучело.

> и посик в нем

И посик, и покак. Смеши меня ещё, клоунок.

Ну чего придралися барашек, прокололся, есть маленько. f(N)=O(N) - для списков. g(N)=O(log(N)) - для контейнеров на сбалансированом дереве. Суть не меняется, тем более что ты понял что имелось в виду, раз матан первого курса до сих пор помнишь. Построй график.

> Ну нельзя же быть таким бараном ! Повторяю в списке у тебя линейная трудоёмкость на произвольный доступ

Для тех, кто в тяжелом штурмовом танке, повторю то примечание, которое было сделано еще в сообщении, с которого начался спор о трудоемкости: "для случая полного перебора элементов списка". Перебираются последовательно, один за другим, никакого произвольного, мать его, доступа. Переход от элемента списка к следующему = O(1).

> f(N)=O(N) - для списков. g(N)=O(log(N))

Ты совсем плюсов обкурился, клоунок? Ты произвольный доступ от последовательного отличить умеешь? Последовательный обход элементов списка - очеведное O(N). Обход дерева в случайном порядке - O(N * log(n)). Уткнись и не пиши сюда больше, ты не нужен, как и твои плюсы, оплот маразма, светоч быдла.

>Ты совсем плюсов обкурился, клоунок?

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

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

>Уткнись и не пиши сюда больше, ты не нужен, как и твои плюсы, оплот маразма, светоч быдла.

Резюмируя: пнх быдлокодер, считать научись, и быстренько книжку купи с матаном 1-го курса, тупица.

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

Ты туп. Тебе два взрослых человека объяснили: один раз обойти список дешевле, чем в случайные моменты искать по дереву. Но ты продолжаешь нести свою несвязную чушь. Вывод: ты зарвавшееся малограмотное чмо. А теперь убирайся, разговор с тобой окончен, гадёныш.

> Ну нельзя же быть таким бараном ! Повторяю в списке у тебя линейная трудоёмкость на произвольный доступ

>Для тех, кто в тяжелом штурмовом танке, повторю то примечание, которое было сделано еще в сообщении, с которого начался спор о трудоемкости: "для случая полного перебора элементов списка". Перебираются последовательно, один за другим, никакого произвольного, мать его, доступа. Переход от элемента списка к следующему = O(1).

ты тупой ? чего ты сложность одной операции считрашь ? Повторяю для тупых: сложность поиска и доступа к произвольному элементу односвязного списка: f(N)=O(N). Доступ к произвольному элементу N, осуществляется только итеративно. Итерирование к следующему элементу имеет константную сложность, удаление и добавление текущего элемента - константная сложность. Это только для двусвязного списка. Для односвязного, сложность возрастает, т.к. он только top->down

так понятно, баран???

> Вывод: ты зарвавшееся малограмотное чмо.

пнх гаденышь.

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

Повторяю для неграмотных придурков, для сбалансированого бинарного дерева сложность: O(log N)

Для тех кто придерживается другого мнения, направление движения прямо одно -> в школу.

Вот этот барашек к примеру: >Обход дерева в случайном порядке - O(N * log(n))

> Обход дерева в случайном порядке - O(N * log(N))

Ты будешь с этим спорить, клоунок? Ну давай, спорь, люблю юродивых. А лучше не спорь, а сразу сдохни, осмыслив.

> ты тупой ?

свободен

Умиляют меня фанаты цпп. Потом ещё будут доказывать, что в цпп есть ооп. Что делать, если люди smalltalk ни разу не видели. Страуструп вот утверждает, что видел - видать, издали, в подзорную трубу, иначе такого поделия он бы не родил. Заявлять, что "приделав к сям классы, мы получим универсальный язык" - автоматически выставлять себя дурачком-идиотиком на всеобщее посмешище. Я уж молчу о том, что прежде чем клепать недоязычки, следует ознакомиться хотя бы с лиспами, со смолтоком, с лямбда-исчислением, с работами Хиндли-Милнера, с теорией GC... Куда там. Страуструпик-птушничек родил своего мутанта "C with classes", а быдлокодерчики-птушнички подхватили и радостно понесли. Воистину задротский язык. Можно годами надрачиваться преодолевать его убогость, впитывать его маразматическую терминологию, разматывать километры шизофренического бреда, который выдаёт компилятор, обнаружив ошибку в шаблонах, и чувствовать себя просветлённым гуру. Не в пример всяким смолтокам с лиспами, которые настолько красивы и элегантны, что на любом этапе твоего знакомства с языком ни на секунду не дают тебе забыть, что ты туп и убог, как и все человеки. Сказано: ни один мудрый не считает себя мудрым, и ни один глупец не считает себя глупцом. И ни один дрочунок-быдлокодер никогда не признает себя дрочунком-быдлокодерчиком, а свой недоязычок - блевотной ошибкой человечества. Тем лучше для всех, чем больше быдлокодеров, тем ценнее хакеры. Аминь, дрочите дальше.

VSL'ю плюс один

Фу таким быть, противненький