Блог пользователя IWANTTOSUBMIT

GCC versus &WHAT_A_MAD_TYPE1111
Автор IWANTTOSUBMIT, 14 лет назад, По-русски

Доброго времени суток. :)

Возможно Вам покажется, что я - один из суперменов или идиотов, но всё же хочется задать такой вопрос:

Почему в GCC может не компилироваться сей код?

#include <vector>
#include <algorithm>

using namespace std;


typedef pair < pair < double, double > , pair < int , int > > WHAT_A_MAD_TYPE1111;
typedef WHAT_A_MAD_TYPE1111 my;

bool my_compare ( my & A, my & B )
{
   return true;
}

int main()
{
   vector < my > sorted;
   sort( sorted.begin(), sorted.end(), my_compare );
   return 0;
}

В 2005 студии же компилируется нормально.


Компилятор сообщает нам следующее:

Can't compile program.cpp:
In file included from c:\compiler\mingw\bin\../lib/gcc/mingw32/4.4.1/include/c++/algorithm:62,
from program.cpp:2:
c:\compiler\mingw\bin\../lib/gcc/mingw32/4.4.1/include/c++/bits/stl_algo.h: In function 'const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&, _Compare) [with _Tp = std::pair<std::pair<double, double>, std::pair<int, int> >, _Compare = bool (*)(my&, my&)]':
c:\compiler\mingw\bin\../lib/gcc/mingw32/4.4.1/include/c++/bits/stl_algo.h:2301: instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<double, double>, std::pair<int, int> >*, std::vector<std::pair<std::pair<double, double>, std::pair<int, int> >, std::allocator<std::pair<std::pair<double, double>, std::pair<int, int> > > > >, _Size = int, _Compare = bool (*)(my&, my&)]'
c:\compiler\mingw\bin\../lib/gcc/mingw32/4.4.1/include/c++/bits/stl_algo.h:5258: instantiated from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<std::pair<double, double>, std::pair<int, int> >*, std::vector<std::pair<std::pair<double, double>, std::pair<int, int> >, std::allocator<std::pair<std::pair<double, double>, std::pair<int, int> > > > >, _Compare = bool (*)(my&, my&)]'
program.cpp:16: instantiated from here
c:\compiler\mingw\bin\../lib/gcc/mingw32/4.4.1/include/c++/bits/stl_algo.h:124: error: invalid initialization of reference of type 'my&' from expression of type 'const std::pair<std::pair<double, double>, std::pair<int, int> >'
c:\compiler\mingw\bin\../lib/gcc/mingw32/4.4.1/include/c++/bits/stl_algo.h:125: error: invalid initialization of reference of type 'my&' from expression of type 'const std::pair<std::pair<double, double>, std::pair<int, int> >'
c:\compiler\mingw\bin\../lib/gcc/mingw32/4.4.1/include/c++/bits/stl_algo.h:127: error: invalid initialization of reference of type 'my&' from expression of type 'const std::pair<std::pair<double, double>, std::pair<int, int> >'
c:\compiler\mingw\bin\../lib/gcc/mingw32/4.4.1/include/c++/bits/stl_algo.h:131: error: invalid initialization of reference of type 'my&' from expression of type 'const std::pair<std::pair<double, double>, std::pair<int, int> >'
c:\compiler\mingw\bin\../lib/gcc/mingw32/4.4.1/include/c++/bits/stl_algo.h:133: error: invalid initialization of reference of type 'my&' from expression of type 'const std::pair<std::pair<double, double>, std::pair<int, int> >'


Заранее спасибо.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

14 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
Я убрал амперсанды из компаратора и у меня лично в MinGW32 и на codepad всё компилируется.

П.С. за верность работы алгоритма не ручаюсь.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Короче, отведённое на копирование время... и время работы программы печально возрастёт.

    Буду рад, если ошибаюсь.


    Тем не мене MSVS 2005 = compile OK

    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      http://cplusplus.com/reference/algorithm/sort/
      Написано, что компаратор должен принимать два параметра того же типа, что и элементы массива.
      В среднем будет ~O(nlogn) операций сравнения и записи в память, т.е. асимптотика не должна ухудшиться.
      По-честному std::sort работает в худшем случае за квадрат и этот худший случай довольно легко придумать, потому заботиться о времени копирования довольно бессмысленно :).
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        std::sort - очень хорошо написанная сортировка. И она работает за nlogn всегда. Причем очень хороший nlogn. 

        В частности на тему худшего случая : насколько я знаю если сортировка слишком глубоко заходит в рекурсию, то запускается heapsort. И еще вроде если сталось очень мало элементов, то запускается сортировка вставками, которая хоть и квадратичная, но на маленьких массивах( где-то <=20 по-моему) работает быстрее.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Во-первых, в ссылке выше написано, что худший случай - O(N2)
          Во-вторых, самолично ловил в задаче просто на сортировку 105 элементов без любых других действий ТЛ именно с std::sort.
          Ещё, говорят, что скорость зависит от компилятора, но я не вдавался в подробности.
          → Ответить
          • 14 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
            В MinGW, по крайней мере, std::sort работает так (и точно также вроде, в gcc под linux):
            1. n <= 3: разбираем 6 случаев ручками
            2. qsort.
            3. Если qsort ушел слишком глубоко - запускаем HeapSort.
            In the worst case, up to N2, depending on specific sorting algorithm used by library implementation.
            Если вы сдавали на VC++ - то не очень удивлён. Если на GCC - удивлён очень сильно. Обогнать std::sort пытался "чистым" qsort/mergesort, у меня не получилось. Даже в самом лучшем случае.
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              > Если вы сдавали на VC++ - то не очень удивлён

              С каких пор компилятор в студии стал хуже чем GCC О.О
              Разумеется, в студии сортировка гарантированно за N*log(N)
              → Ответить
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Религиозные предпочтения. :) Зачеркну, пожалуй, неправильно это.
                А еще я где-то слышал, что по совместимости со стандартами компиляторы располагаются так: Borland C++, GCC, VC++

                → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Объединю 2 ответа в одном сообщении:
            1. Один раз получил ТЛ, как было написано выше, теперь стараюсь избегать. К сожалению, на сервере, где проверялось, не было написано, какой компилятор используется (изначально тоже думал, что MCVC тупит, но не проверял), по крайней мере, хочется, чтобы код был компиляторонезависимым.
            2. 10^5 интов.
            → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Всё просто. Замените
      bool my_compare ( my & A, my & B )
      на
      bool my_compare (const my & A, const my & B )
      ведь нехорошо же, когда компаратор изменает данные? :)
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        +1

        Да, совсем нехорошо...

        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Еще не хорошо, что компаратор всегда возвращает тру
          Получается что может быть что  A < B и в тоже время B < A. Это вообще должно выбрасывать исключение при сортировке..
          → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я чтоб лишний раз не рисковать
кладу в set и обратно вытаскиваю уже в отсортированном виде. Точно за nlong будет.

for(set<int>::iterator it=s.begin();it!=s.end();it++)
{
   //и тут с (*it) работаешь
}

лишь бы память позволяло...
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    N Log N то будет, да вот константа у сортировки гораздо меньше чем у set (на некоторых тасках, в которых очевидно напрашивалось решение на set ловило ТЛ, а после некоторой обдумки и перехода к сортироке и, например, дихотомии, получало АС (правда у set не был перегружен allocator и прочее).
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну это уж вовсе изврат... :)
    Надо ещё не забывать про stable_sort().
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А почему stable_sort() может работать за N*log N*log N, а не просто N*log N? И как проверяет хватает ли памет?
      → Ответить