Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[44.201.131.213] |
|
Страницы: (5) 1 [2] 3 4 ... Последняя » все ( Перейти к последнему сообщению ) |
Сообщ.
#16
,
|
|
|
Ну раз уж пошли флудить, дайте и я добавлю
#include <algorithm> #include <iostream> #include <vector> #include <cstdlib> int main() { std::vector<int> v(30); std::generate(v.begin(), v.end(), [](){ return (std::rand() % 10); }); std::stable_partition(v.begin(), v.end(), [](int i){return i == 0;}); std::copy(std::begin(v), std::end(v), std::ostream_iterator<int>(std::cout, " ")); return 0; } |
Сообщ.
#17
,
|
|
|
[](const auto &a, const auto &b) -> bool { if (!a && b) return true; return false; } Смысл весь массив сортировать если надо только нули вперёд вытянуть? Или как вариант: [](const auto &a, const auto &b) -> bool { return abs(a)<abs(b); } |
Сообщ.
#18
,
|
|
|
Не очевидно. Вот пример сортировки всех нулей: #include <algorithm> #include <iostream> #include <iterator> #include <vector> #include <cstdlib> int main() { int c = 0; std::vector<int> v(10,0); std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::sort(v.begin(), v.end(), [&](const auto &a, const auto &b) -> bool { c = c + ((a == 0 || a < b) ? 1:0); if (a == 0) return true; return a < b; }); std::cout << std::endl; std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; std::cout << "c:" << c << std::endl; return 0; } Лямбда со значением true отработала ровно 9 раз. В чем проблема? Добавлено При векторе std::vector<int> v = {0,1,0,1,0,1,0,1,0,1} лямбда со значением true отработала 4 раза. Добавлено Можно конечно городить портянку сравнений на всевозможные варианты a и б - а смысл? Добавлено Цитата negram @ Ну раз уж пошли флудить, дайте и я добавлю Согласно "Т3" - твое решение лучшее |
Сообщ.
#19
,
|
|
|
Точно, забыл я про stable_partition
|
Сообщ.
#20
,
|
|
|
Цитата JoeUser @ Не очевидно. Цитата из стандарта: Цитата Compare is a function object type (20.8). The return value of the function call operation applied to an object of type Compare, when contextually converted to bool (4), yields true if the first argument of the call is less than the second, and false otherwise. В частности, из этого следует, что cmp(x, x) должно равняться false для любого x. |
Сообщ.
#21
,
|
|
|
Цитата OpenGL @ В частности, из этого следует, что cmp(x, x) должно равняться false для любого x. Задавая лямбду сортировки - мы задаем свое (любое!) условие сравнения. Почему мы не можем задать, что "левый" нуль всегда меньше "правого"? Возможно это как-то повлияет на количество излишних свопов, но логику не нарушит. Что и демонстрируют примеры. |
Сообщ.
#22
,
|
|
|
Цитата JoeUser @ Задавая лямбду сортировки - мы задаем свое (любое!) условие сравнения. Почему мы не можем задать, что "левый" нуль всегда меньше "правого"? Не можем. То, что у тебя работает в конкретном компиляторе, говорит только о том, что это работает в нём и на твоих примерах, а не о том, что сортировка обязана работать и при таком компараторе. |
Сообщ.
#23
,
|
|
|
Цитата OpenGL @ Не можем. То, что у тебя работает в конкретном компиляторе, говорит только о том, что это работает в нём и на твоих примерах, а не о том, что сортировка обязана работать и при таком компараторе. Да ешкин кот! Я могу в компораторе при сравнении указать что меньшее число является большим большего? Могу! И получится обратная сортировка. В документации "а" и "b" - это не целочисленные типы, это просто типы, которые я как хочу так и сравниваю. Повторюсь - максимум я потеряю на излишних свопах, когда одно значение в одном вызове будет меньше (в равных условиях), а во втором вызове оно больше. |
Сообщ.
#24
,
|
|
|
JoeUser, OpenGL говорит о том, что в компараторе если comp(a,b)==false, то comp(b,a)==true
У тебя это нарушается и появляется случай когда comp(a,b)==comp(b,a) что может привести к UB, и получится "ой" когда в твоей STL поменяют алгоритм сортировки |
Сообщ.
#25
,
|
|
|
Ты ссылку вообще читал? Если у тебя компаратор не обеспечивает strict weak ordering, то алгоритмы летят к чертям - их работоспособность не гарантируется. Например:
#include <iostream> #include <vector> #include <algorithm> int main () { std::vector<std::pair<int, int>> v; for(int i = 0; i < 10; ++i) { v.push_back(std::make_pair(0, i)); } std::stable_sort(v.begin(), v.end(), [](const auto &a, const auto &b) -> bool { if (a.first == 0) return true; return a.first < b.first; }); for(auto &x: v) { std::cout << x.first << " " << x.second << std::endl; } } Вывод: 0 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 0 0 На wandbox. Офигенно stable она работает, не так ли? |
Сообщ.
#26
,
|
|
|
Цитата negram @ что может привести к UB Не будет UB. Для чего нужен компаратор? Чтобы понять когда обменять значения. Что если обменять равные значения? Будет лишний своп. Но это не UB - это оверхед. Добавлено Цитата OpenGL @ Офигенно stable она работает, не так ли? Работает так как ты "заказал", закидывать в начало - пары, у которых первое значение "нуль". Это все. Другой порядок ты не определил. Как заказал - так и получил. |
Сообщ.
#27
,
|
|
|
Цитата JoeUser @ Работает так как ты "заказал", закидывать в начало - пары, у которых первое значение "нуль". Это все. Другой порядок ты не определил. Как заказал - так и получил. "Закидывать в начало нули" это означает, что сначала должны идти нули в том же порядке, в котором шли, а потом остальные - с аналогичным условием. Ты здесь это видишь? Ну и для кучи можешь ещё std::is_sorted вызвать на только что отсортированном векторе из примера выше - тоже весело будет. Добавлено О, а вот и пример того, как ломается уже просто std::sort: #include <iostream> #include <vector> #include <algorithm> int main () { std::vector<std::pair<int, int>> v; for(int i = 0; i < 10; ++i) { v.push_back(std::make_pair(rand() % 3 - 1, i)); } auto cmp = [](const auto &a, const auto &b) -> bool { if (a.first == 0) return true; return a.first < b.first; }; std::sort(v.begin(), v.end(), cmp); for(auto &x: v) { std::cout << x.first << " " << x.second << std::endl; } } Вывод на wandbox: 0 9 -1 7 0 6 0 5 0 3 -1 2 -1 8 0 1 0 0 1 4 Добавлено Цитата negram @ OpenGL говорит о том, что в компараторе если comp(a,b)==false, то comp(b,a)==true Только наоборот - если (a, b) == true, то (b, a) обязано быть false |
Сообщ.
#28
,
|
|
|
Цитата negram @ Ну раз уж пошли флудить Ты как творчество называешь?! Цитата OpenGL @ if (a.first == 0) return true; return a.first < b.first; В общем, я решу ваш спор: std::stable_sort(v.begin(), v.end(), [](const auto &a, const auto &b) -> bool { if (a.first == b.first) return false; if (a.first == 0) return true; return a.first < b.first; }); Всё, и никто не уйдёт обиженным. Бесплатно вставлю любой if в ваш код, без регистрации и смс |
Сообщ.
#29
,
|
|
|
Цитата OpenGL @ "Закидывать в начало нули" это означает, что сначала должны идти нули в том же порядке, в котором шли С какого это фига? Ты по первым элементам сравниваешь - по первым тебе и отсортировало. |
Сообщ.
#30
,
|
|
|
Цитата cppasm @ Ты по первым элементам сравниваешь - по первым тебе и отсортировало. Суть в том, что если элементы равны, сортировка считается - избыточным действием. Лично я согласен с этим утверждениям) |