На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Qraizer, Hsilgos
Страницы: (5) 1 [2] 3 4 ... Последняя » все  ( Перейти к последнему сообщению )  
> Срочно нужна помощь. , Задачка на c++
    Ну раз уж пошли флудить, дайте и я добавлю :rolleyes:
    ExpandedWrap disabled
      #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;
      }
      ExpandedWrap disabled
        [](const auto &a, const auto &b) -> bool {
        if (!a && b) return true;
        return false;
        }

      Смысл весь массив сортировать если надо только нули вперёд вытянуть?
      Или как вариант:
      ExpandedWrap disabled
        [](const auto &a, const auto &b) -> bool {
        return abs(a)<abs(b);
        }
        Цитата OpenGL @
        очевидно

        Не очевидно.
        Вот пример сортировки всех нулей:
        ExpandedWrap disabled
              #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" - твое решение лучшее :)
          Точно, забыл я про stable_partition :(
            Цитата 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.
              Цитата OpenGL @
              В частности, из этого следует, что cmp(x, x) должно равняться false для любого x.

              Задавая лямбду сортировки - мы задаем свое (любое!) условие сравнения. Почему мы не можем задать, что "левый" нуль всегда меньше "правого"? Возможно это как-то повлияет на количество излишних свопов, но логику не нарушит. Что и демонстрируют примеры.
                Цитата JoeUser @
                Задавая лямбду сортировки - мы задаем свое (любое!) условие сравнения. Почему мы не можем задать, что "левый" нуль всегда меньше "правого"?

                Не можем. То, что у тебя работает в конкретном компиляторе, говорит только о том, что это работает в нём и на твоих примерах, а не о том, что сортировка обязана работать и при таком компараторе.
                  Цитата OpenGL @
                  Не можем. То, что у тебя работает в конкретном компиляторе, говорит только о том, что это работает в нём и на твоих примерах, а не о том, что сортировка обязана работать и при таком компараторе.

                  Да ешкин кот! Я могу в компораторе при сравнении указать что меньшее число является большим большего? Могу! И получится обратная сортировка. В документации "а" и "b" - это не целочисленные типы, это просто типы, которые я как хочу так и сравниваю. Повторюсь - максимум я потеряю на излишних свопах, когда одно значение в одном вызове будет меньше (в равных условиях), а во втором вызове оно больше.
                    JoeUser, OpenGL говорит о том, что в компараторе если comp(a,b)==false, то comp(b,a)==true
                    У тебя это нарушается и появляется случай когда comp(a,b)==comp(b,a) что может привести к UB, и получится "ой" когда в твоей STL поменяют алгоритм сортировки :)
                      Ты ссылку вообще читал? Если у тебя компаратор не обеспечивает strict weak ordering, то алгоритмы летят к чертям - их работоспособность не гарантируется. Например:
                      ExpandedWrap disabled
                        #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;
                            }
                        }

                      Вывод:
                      ExpandedWrap disabled
                        0 9
                        0 8
                        0 7
                        0 6
                        0 5
                        0 4
                        0 3
                        0 2
                        0 1
                        0 0

                      На wandbox.
                      Офигенно stable она работает, не так ли? :D
                        Цитата negram @
                        что может привести к UB

                        Не будет UB. Для чего нужен компаратор? Чтобы понять когда обменять значения. Что если обменять равные значения? Будет лишний своп. Но это не UB - это оверхед.

                        Добавлено
                        Цитата OpenGL @
                        Офигенно stable она работает, не так ли?

                        Работает так как ты "заказал", закидывать в начало - пары, у которых первое значение "нуль". Это все. Другой порядок ты не определил. Как заказал - так и получил.
                          Цитата JoeUser @
                          Работает так как ты "заказал", закидывать в начало - пары, у которых первое значение "нуль". Это все. Другой порядок ты не определил. Как заказал - так и получил.

                          "Закидывать в начало нули" это означает, что сначала должны идти нули в том же порядке, в котором шли, а потом остальные - с аналогичным условием. Ты здесь это видишь?
                          Ну и для кучи можешь ещё std::is_sorted вызвать на только что отсортированном векторе из примера выше - тоже весело будет.

                          Добавлено
                          О, а вот и пример того, как ломается уже просто std::sort:
                          ExpandedWrap disabled
                            #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:
                          ExpandedWrap disabled
                            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 :)
                            Цитата negram @
                            Ну раз уж пошли флудить

                            Ты как творчество называешь?! :)

                            Цитата OpenGL @
                            if (a.first == 0) return true;
                            return a.first < b.first;


                            В общем, я решу ваш спор:

                            ExpandedWrap disabled
                                  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 в ваш код, без регистрации и смс :D
                              Цитата OpenGL @
                              "Закидывать в начало нули" это означает, что сначала должны идти нули в том же порядке, в котором шли

                              С какого это фига?
                              Ты по первым элементам сравниваешь - по первым тебе и отсортировало.
                                Цитата cppasm @
                                Ты по первым элементам сравниваешь - по первым тебе и отсортировало.

                                Суть в том, что если элементы равны, сортировка считается - избыточным действием. Лично я согласен с этим утверждениям)
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0825 ]   [ 17 queries used ]   [ Generated: 29.03.24, 02:31 GMT ]