История двух стандартных библиотек Си
Сегодня мне пришел баг-репорт от пользователя Debian, который скормил какую-то ерунду в утилиту scdoc и получил SIGSEGV . Исследование проблемы позволило мне провести отличное сравнение между musl libc и glibc . Для начала посмотрим на стектрейс:
В исходниках на данной строчке написано вот что:
Подсказка: p — это корректный, ненулевой указатель. Переменные last и next имеют тип uint32_t . Сегфолт случается на втором вызове функции isalnum . И, самое важное: воспроизводится только при использовании glibc, но не musl libc. Если вам пришлось перечитать код несколько раз, вы не одиноки: тут попросту нечему вызывать сегфолт.
Поскольку было известно, что все дело в библиотеке glibc, я достал ее исходники и стал искать реализацию isalnum , готовясь столкнуться с какой-нибудь дурацкой фигней. Но прежде чем я дойду до дурацкой фигни, которой там, уж поверьте, навалом, давайте сначала быстренько поглядим на хороший вариант. Вот так функция isalnum реализована в musl libc:
Как и ожидалось, для любого значения c функция отработает без сегфолта, потому что с какого хрена вообще isalnum должна кидать сегфолт?
Ладно, теперь сравним это с реализацией glibc. Как только вы откроете заголовок, вас будет встречать типичная GNU’шная галиматья, но пропустим ее и попытаемся найти isalnum .
Первый результат такой:
Похоже на деталь реализации, двигаемся дальше.
Но что такое __exctype ? Возвращаемся на несколько строчек вверх…
Ладно, по всей видимости это только прототип. Непонятно правда, зачем тут нужен макрос. Ищем дальше…
Так, вот это уже похоже на что-то полезное. Что такое __isctype_f ? Мотаем вверх…
Ну начинается… Ладно, вместе как-нибудь разберемся. Видимо, __isctype_f — это инлайн-функция… стоп, это все находится внутри блока else препроцессорной инструкции #ifndef __cplusplus. Тупик. Где же isalnum , мать ее, на самом деле определена? Ищем дальше… Может вот оно?
Эй, это же «деталь реализации», которую мы видели раньше. Помните?
Попробуем по-быстрому расковырять этот макрос:
Ну что за фигня? Ладно, двигаем дальше и считаем, что это просто магическая константа. Другой макрос называется __isctype , который похож на недавно виденный нами __isctype_f . Посмотрим еще разок на ветку #ifndef __cplusplus :
Ну, по крайней мере мы нашли разыменовывание указателя, которое могло бы объяснить сегфолт. А что такое __ctype_b_loc ?
Как круто с твоей стороны, glibc! Я просто обожаю иметь дело с локалями. Так или иначе, к моему упавшему приложению подключен gdb, и держа в уме всю полученную информацию я пишу вот это убожество:
Сегфолт найден. В комменте была про это строчка: «ISO C требует, чтобы функции ctype работали со значениями типа `unsigned char’ и EOF». Если найти это в спецификации, увидим:
Теперь становится очевидно, как исправить проблему. Мой косяк. Оказывается, я не могу скормить в isalnum произвольный символ UCS-32 для проверки на его вхождение в диапазоны 0x30-0x39, 0x41-0x5A и 0x61-0x7A.
Но тут я возьму на себя смелость предположить: а может быть, функция isalnum вообще не должна кидать сегфолт, вне зависимости от того, что ей передадут? Может быть, даже если спецификация это разрешает, это не означает, что так надо делать? Может быть, ну просто в качестве безумной идеи, поведение этой функции не должно содержать пять макросов, проверять использование компилятора C++, зависеть от порядка байтов вашей архитектуры, таблицы поиска, данных о локали потока и разыменовывать два указателя?
Стандартная библиотека языка Си
Стандартной библиотекой языка Си (также известная как libc, crt) называется часть стандарта ANSI C, посвященная заголовочным файлам и библиотечным подпрограммам. Является описанием реализации общих операций, таких как обработка ввода/вывода и строк, в языке программирования Си. Стандартная библиотека языка Си — это описание программного интерфейса, а не настоящая библиотека, пригодная для использования в процессе компиляции.
Содержание
Структура
Имя и характеристики каждой функции указываются в файле, именуемым заголовочным файлом, но текущая реализация функций описана отдельно в библиотечном файле. Наименование и возможности заголовочных файлов становятся общими, но организация библиотек по-прежнему остается разнотипной. Стандартная библиотека обычно поставляется вместе с компилятором. Так как компиляторы языка Си часто обеспечивают расширенную функциональность, не определенную стандартом ANSI C, стандартная библиотека одного компилятора несовместима со стандартными библиотеками других компиляторов.
Мнения о структуре
Большая часть стандартной библиотеки языка Си производит впечатление удачно спроектированной. Некоторые отдельные части, дававшие преимущество в прошлом, могут провоцировать ошибки. Функции строкового ввода gets() (и применение scanf() для считывания вводимых строк) являются источником множества переполнений буфера, поэтому большинство руководств по программированию советуют избегать подобных приемов. Функция strcpy() также весьма печально знаменита. Ещё одной неоднозначной функцией является strtok() — функция, разработанная как простейший лексический анализатор, но имеющая множество «подводных камней» и потому весьма трудная в использовании.
Выбор применения типа size_t вместо int для числа элементов, указанных для fread() и fwrite() является несовместимым с разработанной общей семантикой для size_t (для представления количества байтов). [источник не указан 506 дней]
stdio достаточно ограничен (слишком высокий уровень для использования во многих ситуациях) и стандарт не позволяет пользователю самостоятельно переназначать или расширять его свойства. В итоге, для множества приложений разрабатываются собственные библиотеки-обертки вокруг механизмов более низкого уровня и функций, реализуемых ОС, таких как POSIX. Например, stdio не работают с сигналами или асинхронными непакетными режимами ввода-вывода, которые широко используются в сетевых серверах. В итоге, только серверы, использующие модель целого процесса для клиента, могут полностью полагаться на функции stdio для обслуживания их на POSIX-совместимых системах в пакетном режиме ввода-вывода.
Определенных функций стандартной библиотеки нужно избегать при разработке многопоточных приложений. Примитивы контроля потоков предназначались для оставшейся части ОС и игнорируют общие стандарты, как например, библиотеку потоков POSIX, ожидая, что программисты языка Си, самостоятельно об этом позаботятся работая с повторным использованием и синхронизацией. Ни язык Си, ни его стандартная библиотека никак не проверяют подобные системноспецифичные результаты.
История
Язык программирования Си до стандартизации не обеспечивал встроенной функциональности, как, например, операции ввода-вывода (в отличие от таких традиционных языков, как Кобол и Фортран). Позже, в сообществе программистов, работавших с языком Си, зародились идеи, которые реализовались в то, что мы сейчас называем Стандартной библиотекой языка Си, для поддержки этой функциональности. Большинство этих идей в итоге объединились в определении стандарта языка программирования Си.
И Unix, и Си были созданы в AT&T’s Bell Laboratories в конце 1960-х — начале 1970-х. В 1970-е язык программирования Си начал пользоваться невероятной популярностью. Множество университетов и организаций начали создание собственных вариантов языка, более подходящих для собственных нужд. С началом 1980-х проблемы совместимости между различными реализациями языка Си стали слишком очевидными. В 1983 году Американский национальный институт стандартов (ANSI) сформировал комитет для принятия стандарта языка Си, известный как «ANSI Си». Эта работа вылилась в создание так называемого стандарта C89 в 1989. Часть итогового стандарта была набором библиотек, названная Стандартная библиотека ANSI Си.
Последующие версии стандарта языка Си добавляли некоторые новые и наиболее полезные заголовочные файлы в библиотеку. Поддержка этих новых расширений зависела от реализации.
Заголовочные файлы <iso646.h>, <wchar.h> и <wctype.h> были добавлены в Приложении 1 (сокращенно NA1) — дополнении к Стандарту языка Си, ратифицированному в 1995.
Заголовочные файлы <complex.h>, <fenv.h>, <inttypes.h>, <stdbool.h>, <stdint.h> и <tgmath.h> были добавлены в C99, версии Стандарта языка Си, опубликованном в 1999.
Стандарт ANSI
Стандартная библиотека ANSI Си состоит из 24 заголовочных файлов, каждый из которых можно подключать к программному проекту при помощи одной директивы. Каждый заголовочный файл содержит объявления одной или более функций, определения типов данных и макросы. Содержание этих заголовочных файлов перечисляется ниже.
В сравнении с некоторыми другими языками (например Java) стандартная библиотека крайне мала. Библиотека обеспечивает поддержку основного набора математических функций, обработку строк, конвертацию типов, файловый и консольный ввод-вывод. Она не содержит стандартный набор «контейнерных типов» как стандартная библиотека шаблонов языка C++, компоненты для работы с графическим пользовательским интерфейсом (GUI), сетью и прочей разнообразной функциональности, которую Java поддерживает по стандарту. Главным преимуществом маленькой стандартной библиотеки является упрощение работы с окружением ANSI Си по сравнению с другими языками, а следовательно и упрощение портирования программ на языке Си на новые платформы.
Множество прочих библиотек было разработано для поддержки схожей функциональности, обеспечиваемой другими языками в их стандартных библиотеках. Например, в проекте разработки окружения рабочего стола GNOME был разработан набор графических инструментов GTK+ и GLib — библиотека контейнерных структур данных, как впрочем и множество других известных примеров. Разнообразие доступных библиотек означает, что некоторые инструменты верхнего уровня, со временем подтвердили свою полезность. Значительным минусом является то, что они часто не слишком успешно взаимодействуют друг с другом, поэтому программистам зачастую привычнее работать с различными наборами библиотек, а их наборы могут быть доступны на различных специфических платформах.
Библиотечные заголовочные файлы ANSI Си
| <assert.h> | Содержит макрос утверждений, используемый для обнаружения логических и некоторых других типов ошибок в отлаживаемой версии программы. |
| <complex.h> | Набор функций для работы с комплексными числами. (Появилось в C99) |
| <ctype.h> | Содержит функции, используемые для классификации символов по их типам или для конвертации между верхним и нижним регистрами независимо от используемой кодировки (обычно ASCII или одно из её расширений, хотя есть и реализации, использующие EBCDIC). |
| <errno.h> | Для проверки кодов ошибок, возвращаемых библиотечными функциями. |
| <fenv.h> | Для управления средой, использующей числа с плавающей запятой. (Появилось в C99) |
| <float.h> | Содержит заранее определенные константы, описывающие специфику реализации свойств библиотеки для работы с числами с плавающей запятой, как, например, минимальная разница между двумя различными числами с плавающей точкой (_EPSILON), максимальное число цифр точности (_DIG) и область допустимых чисел (_MIN, _MAX). |
| <inttypes.h> | Для точной конвертации целых типов. (Появилось в C99) |
| <iso646.h> | Для программирования в кодировке ISO 646. (Появилось в NA1) |
| <limits.h> | Содержит заранее заданные константы, определяющие специфику реализации свойств целых типов, как, например, область допустимых значений (_MIN, _MAX). |
| <locale.h> | Для setlocale() и связанных констант. Используется для выбора соответствующего языка. |
| <math.h> | Для вычисления основных математических функций |
| <setjmp.h> | Объявляет макросы setjmp и longjmp, используемые для нелокальных переходов |
| <signal.h> | Для управления обработкой сигналов |
| <stdarg.h> | Для доступа к различному числу аргументов, переданных функциям. |
| <stdbool.h> | Для булевых типов данных. (Появилось в C99) |
| <stdint.h> | Для определения различных типов целых чисел. (Появилось в C99) |
| <stddef.h> | Для определения нескольких стандартных типов и макросов. |
| <stdio.h> | Реализует основные возможности ввода и вывода в языке Си. Этот файл содержит весьма важную функцию printf . |
| <stdlib.h> | Для выполнения множества операций, включая конвертацию, генерацию псевдослучайных чисел, выделение памяти, контроль процессов, окружения, сигналов, поиска и сортировки. |
| <string.h> | Для работы с различными видами строк. |
| <tgmath.h> | Для типовых математических функций. (Появилось в C99) |
| <time.h> | Для конвертации между различными форматами времени и даты. |
| <wchar.h> | Для обработки «широких» потоков и нескольких видов строк при помощи «широких» символов (поддержка набора языков). (Появилось в NA1) |
| <wctype.h> | Для классификации «широких» символов. (Появилось в NA1) |
Стандартная библиотека Си в других языках
Некоторые языки обеспечивают функциональность стандартной библиотеки Си при помощи своих собственных библиотек. Библиотека может быть адаптирована для структур языка, но семантика операций остается схожей. Язык программирования C++, например, содержит функциональность стандартной библиотеки ANSI Си в пространстве имен std (например, std::printf , std::atoi , std::feof и т. д.), в заголовочных файлах со схожими именами как в Си (« cstdio », « cmath », « cstdlib » и т. д.). К другим языкам, в которых применяются схожие подходы относятся, например, D и Python. В последнем, к примеру, встроенный объект file определен как «реализованный при помощи пакета stdio языка Си»[1], так что доступные операции (открытие, чтение, запись и т. д.), как ожидается, должны иметь поведение как у соответствующих функий языка Си.
Общая поддержка библиотек
Пока не стандартизировано, но программы на языке Си могут зависеть от библиотек подпрограмм, которые содержат код, используемый компилятором во время работы. Код, инициализирующий процесс для операционной системы, например, перед вызовом main() , реализован в библиотеке времени исполнения языка Си (C Run-Time Library, CRT) для данной версии компилятора. Код библиотеки CRT может помочь с реализацией других особенностей языка, как например, обработка неперехваченных исключений или реализация работы с числами с плавающей точкой.
Стандартная библиотека языка Си только регламентирует наличие вышеупомянутых подпрограмм и их поведение. Так как реализация компилятора может зависеть от наличия этих дополнительных функций, то все зависит от того, какие подпрограммы собраны в Стандартную библиотеку языка Си, таким образом любая программа, разработанная с их помощью, будет нуждаться в них.
Хотя часто путают их со Стандартной библиотекой языка Си из-за их комплектации, библиотека CRT не является стандартизированной частью языка и зависит от особенностей поставки программного продукта.
Встроенные функции компилятора
Некоторые компиляторы (например, GCC [1] ) поддерживают внутренние версии множества функций Стандартной библиотеки языка Си; то есть, реализации функций записываются в компилируемый объектный модуль, а программа вызывает внутренние версии вместо функций общей библиотеки Си. Это уменьшает накладные расходы при вызове функции, особенно если вызов функции заменяется встроенными вариантами, и разрешается использование других форм оптимизации (если компилятор поддерживает управление характеристиками внутренних вариантов), но может приводить к проблемами при отладке (например, внутренние версии не могут быть заменены инструментальными версиями для проверки).
Стандартная библиотека POSIX
POSIX (и SUS) определяют число подпрограмм, которые могут быть доступны помимо определенных в Стандартной библиотеке языка Си; они часто реализуют аналогичную функциональность со Стандартной библиотекой с различной степенью схожести. Например, glibc реализует такие функции как fork в libc.so, но перед вызовом библиотеки потоков объединяются в glibc, хотя это заявлено как отдельная библиотека с собственным флагом линковщика. Зачастую, такая POSIX-совместимая функциональность рассматривается как часть библиотеки; соответствующая библиотека Си, таким образом, может быть идентифицирована как ANSI или ISO библиотека языка Си.
Реализации
Существует множество реализаций, поставляемых как с различными операционными системами, так и с компиляторами языка Си. На BSD системах, к примеру, системная библиотека встроена в операционную систему и поддерживается общим репозиторием исходников. На большинстве систем библиотека может быть найдена под именем « libc ».
Хотя существует очень много реализаций, вот небольшой список самых популярных библиотек:
Си++/Стандартная библиотека
Контейнеры — это template-шаблоны классов, поддерживающих стандартные системы организации данных, таких как массив, односвязный и двусвязный списки и т.п. По сути это оболочка над контейнером, для которого перегружены операторы: ++, *, — и может быть другие.
Соответственно итератор — это класс, предназначенный для перебора элементов контейнера.
Функторы и предикаты используются в библиотеке алгоритмов STL
Функтор — объект класса в котором перегружен оператор (). Количество аргументов определяется задачей, для которой нужен функтор.
Предикат — функция, возвращающая bool, также это может быть функтор оператор () которого возвращает bool. Унарный предикат — предикат принимающий 1 аргумент, к примеру !a. Бинарный предикат — предикат, принимающий 2 аргумента, примеры: a>b, a<b и др.
Контейнеры [ править ]
Виды. Последовательные и ассоциативные. Адаптеры (. что это?).
- vector. Обертка вокруг массива, выделяемого по new. Поддерживает проверку границы (если использовать v.at(i), а не v[i]), а также автоматическую реаллокацию при добавлении в хвост и вставке/удалении в середину.
Очень быстрый operator[], линейный по времени (из-за умной реаллокации) push_back(), но медленная вставка в середину, кроме того, любая вставка инвалидует все итераторы (STL, построенная в отладочном режиме, сама отлавливает ошибки использования инвалидованных итераторов). Совместим с массивом языка Си — std::vector::operator T* вернет указатель на массив Си, который можно передавать, например, в вызовы операционной системы.
Саттер и Александреску в своей книге пишут: «если вы не уверены, какой именно контейнер вам нужен — смело используйте vector».
- deque. Двунаправленная очередь, реализованная как коллекция страниц стандартного размера.
Очень быстрая вставка/удаление и с головы, и с хвоста, кроме того, эти операции не инвалидуют итераторы. operator[] чуть медленнее, чем у vector, но тем не менее использование deque «только с хвоста» (семантика аналогична vector, класс называется stack) оправдано и имеет свои особенности — operator[] медленнее, зато не инвалидуются итераторы (кроме вставки/удаления в середину) и куда лучше общий паттерн аллокации и фрагментации памяти (важно при большом количестве объектов).
- queue. deque, используемая в режиме «добавление только в голову, удаления только с хвоста».
- list. Список.
Не имеет operator[], и его итераторы не являются random-access. Паттерн аллокации памяти — по блочку на объект. Преимущества: не инвалидует итераторы никогда, и очень быстрые вставки/удаление в середину.
Красно-черное дерево из объектов с операцией поиска по ключу, и тип ключа, и тип объекта — типовые параметры. Хранится в отсортированном виде, алгоритм sort для него ничего не делает.
set из пар объектов, ключ — тип первого объекта. Ассоциативный массив (как в Perl), у которого в квадратных скобках может стоять любой тип, а не только целое число.
Аллокаторы [ править ]
Все контейнеры STL используют т.н. аллокаторы для размещения объектов в памяти. Аллокатор можно указать как типовой параметр, по умолчанию используется std::allocator.
Аллокатор делает следующее:
- определяет (как AlType::pointer) класс «обобщенного указателя» на объект. Этот указатель
должен иметь все операции, определенные для указателя языка Си, а также operator T* (возвращает указатель Си) и operator * (возвращает ссылку). Для операций должны поддерживаться гарантии языка Си (типа *(a + i) тождественно a[i] и так далее). Как именно реализован этот указатель — личное дело аллокатора.
- определяет методы allocate() — выделяет блочок памяти для хранения N объектов типа T,
возвращает обобщенный указатель на его начало, с гарантией, что прибавления к этому указателю дадут указатели на последующие объекты, free() — undo для allocate(), construct() — создает объект по адресу, на который ссылается обобщенный указатель, и free() — undo для construct().
- std::allocator::pointer есть обычный указатель языка Си, методы реализованы примерно так:
- возможно писать свои реализации аллокаторов, при этом с ними будут работать все контейнеры, и общий внутренний код контейнеров, ответственный за «раздвижение» контейнера при вставке в середину и т.д.
Итераторы [ править ]
Обобщение указателя. Классы итераторов.
Позволяют писать код для работы с контейнером (например, алгоритмы STL — см. ниже), не зависящий от типа контейнера.
В любом контейнере объявлен (через typedef) тип его итератора — Cont::iterator
У любого контейнера есть метод Cont::iterator begin(), возвращающий итератор на первый (в порядке обхода) элемент.
У любого итератора перегружена операция ++, означает шаг на следующий элемент.
У любого контейнера есть метод end(), возвращающий лже-итератор (не ссылается на валидную память!), который есть результат ++ над итератором, ссылающимся на последний (в порядке обхода) элемент.
Итераторы можно сравнивать на равенство.
У итератора есть operator T*, возвращает указатель на объект, на который ссылается итератор, и operator *, который преобразует итератор к ссылке на этот же объект.
Правильный код для обхода контейнера:
Заметим, что это позволяет писать код, работающий с диапазонами итераторов, а не с контейнерами как таковыми, что повышает легкость замены в программе одного итератора на другой — vector на list и т.д.
Алгоритмы STL (см. ниже) реализованы именно так.
После внесения изменений в контейнер некоторые (или все) итераторы на него могут прийти в невалидное состояние. Какие именно — зависит от типа контейнера и типа изменения (в хвост/голову/середину). Обращение к инвалидованному итератору есть грубая ошибка, в релизной версии обычно вызывающая крах программы. Отладочные версии STL умеют проверять на такие ошибки.
Итераторы бывают однонаправленные, двунаправленные (есть operator--), и с произвольным доступом (есть [] и прибавления/вычитания целых чисел, семантика строго как у указателя Си). Каков данный итератор в этом смысле — зависит от контейнера, vector и deque имеют итераторы с произвольным доступом, а list — нет.
Алгоритмы [ править ]
Алгоритмы над контейнерами позволяют, независимо от типа контейнера, работать с его данными с помощью итератора контейнера. Ниже приведены некоторые примеры из библиотеки алгоритмов STL, для её подключения нужно указать #include <algorithm>. Каждый алгоритм в это библиотеке описывает целевую задачу и поэтому очень мал, поэтому советую не лениться и смотреть определение неизвестных классов и функций.
for_each [ править ]
Код этой функции очень прост (хотя и по началу непонятен, т.к. записан в библиотеке ужасным образом в плане эстетизма записи кода):
_F — итератор на элемент контейнера, с которого нужно начинать
_L — итератор на элемент контейнера, которым нужно заканчивать
_Op — функция от одного аргумента или функтор, у которого перегружена операция () для одного аргумента. Тип аргумента должен соответствовать типу данных, содержащихся в контейнере.
Как видим, функция for_each всего-то-навсего для каждого элемента в контейнере вызывает функцию или оператор функтора. Также видно, что возвращаемое значение не играет роли. И все. Пример использования:
В данной задаче (увеличение каждого элемента на 1) можно обойтись и простой функцией:
но в более сложных задачах может пригодится объект.
transform [ править ]
Тут проще посмотреть на определение:
transform помещает в новый контейнер (_X — итератор на его начало) значения, которые вернет наша функция (_U) или функтор от аргумента из исходного контейнера. Если указать источник равный приемнику, то будут соответственно изменены значения исходного контейнера. Пример использования:
back_inserter — функция, которая возвращает объект (back_insert_iterator), который в свою очередь определяет оператор * (возвращает *this) и оператор = , в котором вызывает push_back для нашего контейнера mass2. Понятно в чем фишка? Это как раз нам и нужно, т.к. mass2 у нас пуст, а в функции transfrom как раз выполняется присваивание.
count_if [ править ]
Подсчитывает количество элементов в указанном диапазоне контейнера, для которых выполняется унарный предикат (третий аргумент). К примеру, если у нас массив mass2=[0,1,2,3,4], то:
Ниже будет показан пример как этого же результата можно добится используя адаптеры вместо функции.
partition [ править ]
Переставляет элементы контейнера так, что сначала идут элементы, меньшие, чем данный, а потом — большие.
Линейное время исполнения. Не выделяет дополнительную память. (уточнить требования к bidir и random у итераторов! кажется, обязателен BidIt).
stable_partition [ править ]
То же, что partition, но с гарантией, что не будут меняться местами элементы, «равные» друг другу.
Выделяет временную дополнительную память для всего множества.
nth_element [ править ]
«Недосортировка». Переставляет элементы так, что в позиции N окажется тот элемент, который оказался бы там при полной сортировке. При этом не дается никаких гарантий на остальные элементы (уточнить! кажется, предыдущие гарантированно все меньше, а последующие — все больше).
«Половина» qsort с рекурсией только по одной половинке, а не по обеим.
Не нужна дополнительная память (хвостовая рекурсия заменена циклом, даже стек не потребляется). Время исполнения линейное.
partial_sort [ править ]
Находит N наименьших элементов, и располагает их в порядке возрастания в начале контейнера. Никаких гарантий на остальные элементы.
«Половина» от heap sort.
partial_sort всего контейнера есть полный heap sort.
Время N * log N (без деградации на неудачных данных), память не нужна.
sort [ править ]
В зависимости от параметра «порог» — либо qsort (по умолчанию), либо heap sort, либо сначала quick или heap, а затем insertion sort для мелких отрезков.
Требования по памяти и времени — см. классические описания алгоритмов.
stable_sort [ править ]
То же, что sort, но гарантирует не-перестановку равных элементов.
Merge sort. Память нужна сразу и на все сортируемое множество, о времени выполнения — см. классическо описание алгоритма (обычно медленнее qsort, но не деградирует на неудачных входных данных).
Адаптеры [ править ]
Для работы нам потребуется добавить #include <functional>
В примере, где мы показывали работу с count_if не очень-то удобно создавать функцию (отвлекает как никак )). Поэтому рассмотрим следующий код, выполняющий ту же самую работу:
Страшно? Ну ничего, сейчас всё объясню. greater — класс в котором перегружен оператор (), в котором происходит сравнение 2-х аргументов (т.е. return (_X > _Y)). Т.е. это настоящий бинарный предикат. А теперь давайте представим, как было бы хорошо, если бы на место первого аргумента (_X) подставлялся элемент из массива, а во второй какое-нибудь заданное нами число (2). bind2nd как раз это и делает. При его конструировании мы указываем бинарный предикат и значение, которое сохраняется и подставляется в greater<int>::operator() при вызове bind2nd::operator(). Тем самым мы превращаем наш бинарный предикат в унарный. Что и требуется для функции count_if.
Для тех кто не понял bind2nd и есть адаптер. Существует также bind1st, который заменяет не второй аргумент, а первый. Поэкспериментируйте.