> По поводу 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.
Тогда непонятно почему бы не использовать int a[3] = {1, 2, 3} Потом потребность в этой ерунде - настолько редкая ситуация, что серьезным аргументом против Си++ не является. По крайней мере для меня
>А по поводу дичайшего кода... Давай лучше вспомним, что C++ не позволяет даже cделать std::vector<int> v = {1, 2, 3}. :-P Кастыль твои плюсы, а STL — вдвойне кастыль.
Повторяю для тупых: если вы незнаете или нелюбидте СТЛ, значит вы незнаете С++, и все Ваши нарекания - чистейший пердёж.
>И 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.
> Вы просто С++ незнаете, потому и думаете так примитивно, 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% т.к. плейсмент выделение использует:
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.
> Об опечатках слышать приходилось ? Придераться к правописанию в данном контексте, по меньшей мере неуместно.
Об уважении к собеседнику слышать приходилось?
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) ?
П-ц, господа. В дурдоме дом открытых дверей? Или ты, убогонький, не знаком даже с матанализом в объёме первого семестра первого курса? Умри в корчах и на засоряй топик своим бредом.
Ну чего придралися барашек, прокололся, есть маленько.
f(N)=O(N) - для списков.
g(N)=O(log(N)) - для контейнеров на сбалансированом дереве.
Суть не меняется, тем более что ты понял что имелось в виду, раз матан первого курса до сих пор помнишь. Построй график.
> Ну нельзя же быть таким бараном ! Повторяю в списке у тебя линейная трудоёмкость на произвольный доступ
Для тех, кто в тяжелом штурмовом танке, повторю то примечание, которое было сделано еще в сообщении, с которого начался спор о трудоемкости: "для случая полного перебора элементов списка". Перебираются последовательно, один за другим, никакого произвольного, мать его, доступа. Переход от элемента списка к следующему = O(1).
Ты совсем плюсов обкурился, клоунок? Ты произвольный доступ от последовательного отличить умеешь? Последовательный обход элементов списка - очеведное O(N). Обход дерева в случайном порядке - O(N * log(n)). Уткнись и не пиши сюда больше, ты не нужен, как и твои плюсы, оплот маразма, светоч быдла.
> Это похоже ты обкурился баран, списков с произвольным доступом не бывает, только последовательный, на то они и списки. Односвязный, двусвязный.
Ты туп. Тебе два взрослых человека объяснили: один раз обойти список дешевле, чем в случайные моменты искать по дереву. Но ты продолжаешь нести свою несвязную чушь. Вывод: ты зарвавшееся малограмотное чмо. А теперь убирайся, разговор с тобой окончен, гадёныш.
> Ну нельзя же быть таким бараном ! Повторяю в списке у тебя линейная трудоёмкость на произвольный доступ
>Для тех, кто в тяжелом штурмовом танке, повторю то примечание, которое было сделано еще в сообщении, с которого начался спор о трудоемкости: "для случая полного перебора элементов списка". Перебираются последовательно, один за другим, никакого произвольного, мать его, доступа. Переход от элемента списка к следующему = O(1).
ты тупой ? чего ты сложность одной операции считрашь ? Повторяю для тупых: сложность поиска и доступа к произвольному элементу односвязного списка: f(N)=O(N). Доступ к произвольному элементу N, осуществляется только итеративно. Итерирование к следующему элементу имеет константную сложность, удаление и добавление текущего элемента - константная сложность. Это только для двусвязного списка. Для односвязного, сложность возрастает, т.к. он только top->down
Умиляют меня фанаты цпп. Потом ещё будут доказывать, что в цпп есть ооп. Что делать, если люди smalltalk ни разу не видели. Страуструп вот утверждает, что видел - видать, издали, в подзорную трубу, иначе такого поделия он бы не родил. Заявлять, что "приделав к сям классы, мы получим универсальный язык" - автоматически выставлять себя дурачком-идиотиком на всеобщее посмешище. Я уж молчу о том, что прежде чем клепать недоязычки, следует ознакомиться хотя бы с лиспами, со смолтоком, с лямбда-исчислением, с работами Хиндли-Милнера, с теорией GC... Куда там. Страуструпик-птушничек родил своего мутанта "C with classes", а быдлокодерчики-птушнички подхватили и радостно понесли. Воистину задротский язык. Можно годами надрачиваться преодолевать его убогость, впитывать его маразматическую терминологию, разматывать километры шизофренического бреда, который выдаёт компилятор, обнаружив ошибку в шаблонах, и чувствовать себя просветлённым гуру. Не в пример всяким смолтокам с лиспами, которые настолько красивы и элегантны, что на любом этапе твоего знакомства с языком ни на секунду не дают тебе забыть, что ты туп и убог, как и все человеки. Сказано: ни один мудрый не считает себя мудрым, и ни один глупец не считает себя глупцом. И ни один дрочунок-быдлокодер никогда не признает себя дрочунком-быдлокодерчиком, а свой недоязычок - блевотной ошибкой человечества. Тем лучше для всех, чем больше быдлокодеров, тем ценнее хакеры. Аминь, дрочите дальше.