Форум программистов, компьютерный форум CyberForum.ru

Ошибка в стандартной библиотеке шланга? - C++

Восстановить пароль Регистрация
 
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
18.06.2013, 01:01     Ошибка в стандартной библиотеке шланга? #1
Обнаружил интересную вещь: std::sort из стандартной библиотеки компилятора clang сортирует неправильно.
Код, на котором это происходит, прилагается:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
 
void print_vector (const std::vector<int> & vector)
{
    for (int x: vector)
    {
        std::cout << x << ' ';
    }
    std::cout << std::endl;
}
 
int main ()
{
    std::vector<int> v(31);
    std::iota(v.begin(), v.end(), 0);
    print_vector(v);
 
    auto compare = std::less_equal<int>();
 
    std::sort(v.begin(), v.end(), compare);
    print_vector(v);
 
    std::cout << (std::is_sorted(v.begin(), v.end(), compare) ? "sorted" : "unsorted")
              << std::endl;
 
    return 0;
}
Проверял на следующих компиляторах:
Код
Apple LLVM version 4.2 (clang-425.0.28) (based on LLVM 3.2svn)
Target: x86_64-apple-darwin11.4.0
Thread model: posix
Код
clang version 3.2 (tags/RELEASE_32/final)
Target: x86_64-apple-darwin11.4.0
Thread model: posix
При этом в ГЦЦ всё сортируется правильно.

Вопрос:
Это я что-то делаю не так, или у всех такое?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
18.06.2013, 11:52     Ошибка в стандартной библиотеке шланга? #2
volovzi, Плюсую.

Bash
1
2
3
4
./new
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 15 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
unsorted
Используется libc++3.2
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
18.06.2013, 12:01  [ТС]     Ошибка в стандартной библиотеке шланга? #3
Ужос-ужос. Надо заводить баг.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
20.06.2013, 16:25     Ошибка в стандартной библиотеке шланга? #4
volovzi, Почитывал хабр - статья на тему вариадиков, в комментах http://habrahabr.ru/post/183830/ цитируют эту тему. И судя по всему это не является багом.
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
20.06.2013, 16:48  [ТС]     Ошибка в стандартной библиотеке шланга? #5
Заглянул в стандарт — действительно, требуется отношение строгого порядка.
Я считаю, что это недоработка.
Я бы сформулировал требование к алгоритму так:
В результате работы алгоритма для любых двух итераторов i, j из сортируемого диапазона таких, что i < j, должно выполняться соотношение compare(*i, *j) == true.

В противном случае это не сортировка, а какая-то непонятная шняга.
Nick Alte
Эксперт С++
1594 / 986 / 117
Регистрация: 27.09.2009
Сообщений: 1,902
Завершенные тесты: 1
21.06.2013, 18:37     Ошибка в стандартной библиотеке шланга? #6
А ведь элементы-то в массиве все разные. Для них операция <= ничем не отличается от <.
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
21.06.2013, 18:48  [ТС]     Ошибка в стандартной библиотеке шланга? #7
@Nick Alte, кстати да, хорошее замечание.
Действительно, логично было бы предположить, что для данного случая все сравнения элементов дадут один и тот же результат и для "<", и для "≤".

Хм.
Dmitriy_M
1307 / 1188 / 109
Регистрация: 20.03.2009
Сообщений: 4,259
Записей в блоге: 11
21.06.2013, 23:57     Ошибка в стандартной библиотеке шланга? #8
В чем смысл сортировать упорядоченный массив?
Как показал отладочный вывод @ForEveR, массив упорядочен, а проблема в
C++
1
2
std::cout << (std::is_sorted(v.begin(), v.end(), compare) ? "sorted" : "unsorted")
              << std::endl;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.06.2013, 00:03     Ошибка в стандартной библиотеке шланга?
Еще ссылки по теме:

C++ Ошибка в определении стандартной API функции
C++ Продемонстрировать работу стандартной функции
Конфликт стандартной sqrt() и собственной C++
C++ Есть ли критическая секция в стандартной библиотеке?
C++ Использование стандартной библиотеки cstring

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
22.06.2013, 00:03  [ТС]     Ошибка в стандартной библиотеке шланга? #9
@Dmitriy_M, во-первых, этот пример — для краткости кода. Если элементы в массиве изначально будут в обратном порядке, то результат будет тот же. Во-вторых, каким бы ни был изначальный массив, после сортировки он должен быть упорядочен. В-третьих, прочитай, пожалуйста, внимательно отладочный вывод. Там ... 14 16 15 ...
Yandex
Объявления
22.06.2013, 00:03     Ошибка в стандартной библиотеке шланга?
Ответ Создать тему
Опции темы

Текущее время: 03:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru