Архив рубрики: Библиотеки C++

Работа с файлами в C++. Часть 2 – Библиотека fstream.




Класс ofstream

Обратный классу ifstream, который мы рассмотрели ранее, и призван для записи в файл.

Как и в ifstream, для открытия или создания файла используется конструктор или метод open().

Или конструктором:

Параметр ios_base::app указывается, если нужно дописывать в конец уже имеющегося файла. Например когда программа ведет лог своей работы

За проверку на открытость файла отвечает все та же is_open()

Принцип тот же. Так же можно проверить открыт ли файл, использовав в логическом выражении саму файловую переменную:

Оператор <<

Перенаправляет форматированный вывод в файл. Принцип тот же, что и у аналога из iostream.

Предназначен для вывода в текстовые файлы. Управляется операциями форматирования такими как width() или setf(). Их аналоги полностью равны одноименным методам из iostream.

Последовательность вывода переменных так же указывается слева на право: Первой будет выведена переменная, указана ближе всех к fileo, потом следующая за ней.

Оператор endl

Аналогично оператору из iostream производит запись перевода каретки на новую строку в текстовых файлах.

Метод write

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

Этот метод принимает два параметра: Указатель на блок данных и количество байт, который этот блок занимает. В примере строка занимает strlen() байт, целое sizeof() (которое даст 4 на 32-х битных операционках для целого и 8 для вещественного).

Еще раз стоит акцентировать, что в отличии от форматированного вывода оператором <<, метод write() не выводит данные в текстовом представлении.

Метод close

Закрывает файл метод close(). Для файлов, открытых на запись, в отличии от файлов на чтение, закрытие файла – обязательный ритуал. Незакрытый файл может не получить данные. Происходить такой эффект может из-за буфферизации самой операционки, когда данные, сбрасываемые в файл, хранятся на самом деле в памяти и сразу в файл не поступают. Операционная система сама решает, когда пора данные сливать.

Такой “отложенный” слив называется “Коммитом” (от латинского commit). Кстати этим эффектом весьма удачно пользуются системы управления базами данных, где вставляемые записи попадают в хранилище в памяти (называемой транзакцией). И только после специальной команды скопом пишутся в сам файл базы. Метод close() как раз пример такой команды закрывающей транзакцию вместе с файлом.

Стоит на всякий случай упомянуть, что если нужно произвести коммит данных без закрытия самого файла, нужно применить метод flush()

Отложенные на запись данные поступят в файл, но он еще будет открыт для записи. Этот метод не так часто используется, но о нем знать полезно.

Методы форматирования width, precision

Как и в iostream, для красивой разметки данных в файле могут применяться методы форматирования данных для вывода оператором << .

width() указывает ширину в символах, в которое будет укладываться выводимое значение, а precision() количество знаков дробной части вещественного. Простейший пример: вывод таблицей в текстовый файл значений тригонометрической функции:

 

Методы позиционирования seekp, tellp

Для перехода по файлу как и в случае с ifstream существует функция перестановки позиции. Называется она seekp() и получает те же параметры что и описаны выше для seekg().

Для получения текущей позиции в байтах от начала файла используется аналогичная функция tellp().

Видео о работе с файлами в С++:

Рассылка новых уроков по программированию:

Работа с файлами в C++. Часть 1 – Библиотека fstream.




Хедер fstream предоставляет функционал для считывания данных из файла и для записи в файл. В целом он очень похож на хедер iostream, который работает с консолью, поскольку консоль это тоже файл. Поэтому все основные операции такие же, за мелкими отличиями, как в предыдущей теме по iostream.

Наиболее частые операции следующее:

  1. Операторы перенаправления ввода\вывода – << и >>
  2. Методы записи и чтения строк getline() и get() c put()
  3. Потоковая запись и чтение методами write() и read()
  4. Методы открытия\создания и закрытия файлов open() и close()
  5. Методы проверки открыт ли файл is_open() и достигнут ли конец файла eof()
  6. Настройка форматированного вывода для >> с помощью width() и precision()
  7. Операции позиционирования tellg(), tellp() и seekg(), seekp()

Это не все возможности, которые предоставляет библиотека fstream. Рассматривать все сейчас мы не будем, поскольку их круг применения достаточно узок. Познакомимся с вышеперечисленными. Начнем с класса чтения.

Класс ifstream

Предоставляет возможности для чтения файлов. Открыть файл можно двумя способами: вызвав метод open() или указав путь к нему в конструкторе. Вам необходимо подготовить текстовый файл, перед тем, как начать набирать код. На диске d создайте папку с именем 1 и в ней создайте файл с расширением txt – “файл.txt”.

Открытие файла в конструкторе выглядит так:

Так мы просим открыть файл txt с именем файл.txt, который лежит в папке с названием 1, а папка находится на диске d.

Использование метода open() удобно, если программист не хочет сразу привязываться к файлу. Вдруг нужно свойство класса или глобальную переменную, ну а открывать файл уже потом. Если же нужно открыть файл внутри некой функции, поработать с ним и закрыть, то можно прописать путь к файлу прямо в конструкторе. В общем зависит от ситуации.

Открыв файл, желательно прописать проверку: открылся ли он? Так как есть ряд причин, по которым файл может не открыться, а мы этого не увидим. Например, файла с указанным именем нет в прописанной папке или путь указан неверно. Можно пойти двумя путями: проверить переменную файла в логическом выражении (применив оператор “!”, к примеру) или использовать метод is_open() :

Так все отработает нормально и файл откроется:

библиотека fstream, работа с файлами в с++, программирование для начинающихТеперь попробуйте вписать название папки не 1, а 2 ifstream file ("d:\\<span style="color: #ff0000;"><strong>2</strong>\\файл.txt”); и снова запустите программу. Так как папки с указанным именем мы не создавали, то и файл, естественно, не может быть открыт:

библиотека fstream, работа с файлами в с++, программирование для начинающих

Второй вариант проверки с использованием метода is_open() :

Метод is_open() вернет 1, если файл найден и успешно открыт. Иначе вернет 0 и сработает код прописанный в блоке else.

Если файл не открыт – желательно обработать ошибку. Как правило, если вся работа программы связана с файлом пишут некое сообщение в консоль, и ставят выход из программы. При серьезных ошибках принято возвращать некий код выполнения (число), который будет характеризовать ту или иную ошибку. Коды для каждого вида ошибок автор программы может придумывать свои. Один из способов обработки ошибок в программе мы рассматривали в статье Исключения в С++.

Если файл успешно открыт, из него можно производить чтение.

Оператор считывания >>

Так же как и в iostream считывание можно организовать оператором >>, который указывает в какую переменную будет произведено считывание:

Считает вещественное, целое и строку. Считывание строки закончится, если появится пробел или конец строки. Стоит отметить, что оператор >> применяется к текстовым файлам. Считывание из бинарного файла производить лучше всего с помощью метода read().

Кстати этот оператор достаточно удобен, если стоит задача разделить файл на слова:

Методы getline() и get()

Считывание целой строки до перевода каретки производится так же как и в iostream методом getline(). Причем рекомендуется использовать его переопределеную версию в виде функции, если считывается строка типа string:

Если же читать нужно в массив символов char[], то либо get() либо getline() именно как методы:

Принцип в общем тот же, что и в аналогах из iostream: Указывается в параметрах буфер (переменная, куда будет производиться чтение), или точнее указатель на блок памяти (если переменная объявлена статически: char buffer[255] к примеру, то пишется в параметры &buffer), указывается максимальное количество считываемого (в примере это n), дабы не произошло переполнение и выход за пределы буфера и по необходимости символ-разделитель, до которого будет считка (в примере это пробел). Надеюсь я не больно наступлю на хобот фанатикам Си, если сажу что эти две функции на 99% взаимозаменяемы, и на 95% могут быть заменены методом read().

Метод read()

Похож на предыдущий пример?

Собственно тут тот же результат – считается указанное количество символов. Исключение только в том, что нельзя указать разделитель. read() применяется для неформатированного ввода. Призван в первую очередь читать бинарные файлы. Поскольку текстовый файл – частный случай бинарного, этот метод вполне применим и к текстовому файлу.

Метод close()

Закрывает файл. Даже добавить нечего. Единственная пожалуй ремарка – от того, что файл, открытый для чтения, не будет закрыт этим методом как правило хуже не станет. Очень редки ситуации, когда открытый для чтения файл портится, если завершить программу не закрывая файл. Связана эта порча прежде всего с нестандартными устройствами типа стримеров на магнитной ленте или каких нибудь потоковых хитрых промышленных контроллерах, но по феншую стоит запомнить – открытый файл должен быть закрыт. Это считается хорошим тоном.

Метод eof()

Проверяет не достигнут ли конец файла. Т.е. можно ли из него продолжать чтение. Выше пример с считкой слов оператором >> как раз использует такую проверку.

Метод seekg()

Производит установку текущей позиции в нужную, указываемую числом. В этот метод так же передается способ позиционирования:

  • ios_base::end – Отсчитать новую позицию с конца файла
  • ios_base::beg – Отсчитать новую позицию с начала файла (абсолютное позиционирование)
  • ios_base::cur – Перескочить на n байт начиная от текущей позиции в файле (по умолчанию)

Метод tellg()

Иногда нужно получать информацию о том, сколько уже прочитано. В этом поможет метод tellg():

Он возвращает значение типа int, которое показывает сколько уже пройдено в байтах. Его можно использовать в паре с методом seekg(), чтоб получать размер файла:

В качестве примера работы методов бинарного чтения можно разобрать такой класс:

Подобные обертки-классы удобно использовать, если встречается задача читать из бинарного файла целые структуры.

Видео о работе с файлами в С++:

Рассылка новых уроков по программированию:

sqrt() — функция библиотеки cmath




sqrt( value );

Функция sqrt() библиотеки cmath (math.h) принимает параметр value и возвращает его квадратный корень.

Если параметр ( в нашем случае – value) отрицательный, возникает ошибка.

Результат выполнения показан в онлайн компиляторе ideone

пример работы функции sqrt c++

Рассылка новых уроков по программированию:

pow() — функция библиотеки cmath




pow(a, b);

Функция pow() библиотеки cmath принимает два параметра: a, b. Первое число a (базовое) возводится в степень b.

Возвращает значение ab .

Результат выполнения 23 , 53, 52 :

pow () - функция библиотеки cmath

 

Рассылка новых уроков по программированию:

fma () – функция библиотеки cmath




fma(a, b, c);

Функция fma() библиотеки cmath принимает три параметра: a, b – значения для умножения, c – значение для добавления.

Возвращает значение a * b + c.

Результат выполнения ( 2 * 2 + 3):

fma () - функция библиотеки cmath

Рассылка новых уроков по программированию:

Указатели в контейнерах. STL (часть 16)




указатели в контейнерах, STL, программирование для начинающих

Контейнеры STL существенно снижают сложность написания кода, работающего с динамическими структурами данных и, самое главное, повышают его безошибочность. Но в некоторых случаях, при работе с крупными элементами данных в контейнерах, эта техника может порождать неизбежную потерю производительности. Это связано с тем, что начиная с операции помещения элемента в контейнер, и все последующие перемещения элементов могут требовать копирования элементов.

Примечание: Степень выраженности таких эффектов зависит и от типа контейнера, и от рассматриваемых операций. Например, операции взаимного обмена 2-х элементов в ходе сортировки потребует 3-х копирований для контейнера типа vector и не потребует дополнительных копирований для контейнера list. Но операции начального помещения элемента в контейнер (push_back(), insert() и др.) всегда выполняются копированием.

Это может стать проблемой для приложения, когда операции на контейнерах критичны по времени выполнения (или кажутся вам таковыми). Есть и ещё более сложные случаи, когда для класса объектов контейнера не определена операция копирования, или когда объекты представляют собой сами ссылочные объекты, полное копирование для которых необходимо выполнять рекурсивными процедурами следования по всем ссылкам (то, что в языке Python и других называют глубоким копированием).

Всё работает благополучно, как и ранее — сортируем набор записей по произвольным полям и в любом порядке:

16-1

(Обратите внимание, что завершать это приложение нужно по Ctrl+D — End Of File … в Widows, наверное, по Ctrl+Z.)

Но! … Специально были оставлены отладочные «следы» срабатываний конструкторов и деструкторов записей, и записи конструируются 8 раз, а деструктор срабатывает только 4, для локального массива в точке выхода из блока. Локальный массив для нас вообще не представляет интереса. Он введен для упрощения примера только как набор инициализирующих значений. А вот для записей, помещаемых в контейнер, уничтожение записей не происходит, и мы получаем откровенную утечку памяти. Но хуже того, после того как мы удаляем элемент из контейнера (не предпринимая дополнительных действий), мы и не сможем удалить запись, вызвав для неё delete. Это потому, что после вызова erase() мы потеряли к записи единственный путь доступа через итератор (в коде показан цикл с erase(), так наглядней, что эквивалентно clear(), эффект которого, будет тем же самым).

Вывод, который может быть сделан из примера, выглядит так:

  • помещая в контейнеры не объекты, а указатели на них, можно заметно снизить вычислительные затраты на манипуляции с ними (но всегда ли принципиален этот выигрыш при нынешних вычислительных мощностях?).

  • замена объектов на указатели в контейнерах делает код во много раз более опасным в смысле скрытых тонких ошибок, причём такого серьёзного уровня, которые могут дальше приводить к краху приложения.

Здесь некоторую помощь могут оказать умные указатели из последних стандартов C++ (shared_ptr или weak_ptr, но не unique_ptr и не старый добрый и проблемный auto_ptr), нам для этого в предыдущем коде достаточно сменить 4 строчки:

В Windows для shared_ptr необходим #include <memory> , а в других системах не обязательно.

И поведение приложения существенно изменится:

16-2

Но не следует безоглядно обольщаться, так как и умные указатели, снимая одни, порождают другие потенциальные заботы (такие как циклические ссылки и др. о которых достаточно много написано).

Рассылка новых уроков по программированию:

Адаптеры. STL (часть 15)




stack, programming for beginners

Отдельной категорией библиотеки стандартных шаблонов являются адаптеры. Адаптеры — это не новые понятия или реализации, а адаптация уже существующих понятий библиотеки под конкретные, часто использующиеся цели. Часто такая адаптация делается посредством ограничения функциональности базового понятия под запросы адаптера. В библиотеке представлены адаптеры контейнеров, итераторов и функций.

Проще всего показать, как появляются адаптеры на примере адаптеров контейнеров: stack (стек), queue (очередь), priority_queue (очередь с приоритетами). Уже из их перечисления понятно, что:

  • Это очень широко и часто используемые структуры данных;

  • Для них не нужны какие-то отдельные реализации. Для обеспечения их функциональности можно использовать (адаптировать) в качестве базового любой из стандартных контейнеров STL, который обеспечивает операции типа push_back, pop_back или pop_front (в зависимости от типа адаптера);

  • «Лишние» операции из арсенала базового контейнера для адаптера нужно исключить (чтобы не создавать искушения … например, операцию индексации, если vector используется для адаптации стека);

И, вместо громоздких шаблонных синтаксических определений (заголовочные файлы <stack>, <queue> и т. п.), обратимся к примерам…

Начнём со стека: стек характерен тем, что получить доступ к его элементам можно лишь с одного конца, называемого вершиной стека. Это коллекция данных, функционирующая по принципу LIFO (Last In — First Out). Вот такой простенький пример раскрывает нам практически всю функциональность стека:

Проанализируем код и сделаем некоторые выводы:

  • Первое определение stack<string> (мы его дальше не используем) объявляет переменную стек, элементами которого являются строки. Обращаем внимание на то, что объекты string сами по себе являются контейнерами STL. Таким образом, стек может содержать элементы любой глубины вложенности контейнеров (что свойственно и любым другим контейнерам STL).

  • Такое определение ( stack<string> ) вы сможете увидеть, как описание стека в подавляющем большинстве примеров. Многие авторы и не подозревают, что может быть по-другому. Но мы воспользуемся другим определением: stack< string, vector<string> > — это стек строк (во многом эквивалентный предыдущему), но построенный на базовом классе vector<string>. В качестве базовых могут использоваться, например, vector, list и deque, или даже ваш собственный контейнерный класс, расширяющий базовые. По умолчанию (так как в 1-м определении) используется база deque. Иногда спрашивают: почему нельзя написать (определить так в реализации stack): stack< vector<string> > (убрав дублирование string)? Потому что (и это вполне возможно) это будет описание совсем другого типа: стек векторов строк (см. выше замечание о структурной вложенности контейнеров).

  • Дальше следует инициализация начального состояния из вектора строк. Отметьте, что такой трюк допустим только в стандарте C++11.

  • Дальше мы видим практически все операции (методы), требуемые от стека: push() – заталкивание объекта в стек, top() – получение ссылки на элемент в вершине стека, pop() – выбрасывание верхнего элемента, size() – текущий размер стека, empty() – проверка на пустоту.

  • Как легко понять, адаптер stack потерял присущие базовому контейнеру методы (at(), [ ] и др.), но приобрёл (переопределением) свои собственные (push(), pop()).

Теперь посмотрим что из этого получилось:

stack, programming for beginners

Разобравшись со стеком теперь элементарно просто перенести аналогии на очередь. В противоположность стеку – это коллекция данных, функционирующая по принципу FIFO (First In — First Out). (Это такая «труба», в один конец которой что-то втекает, а из другого конца затем вытекает.)

Специально оставим для очереди пример практически неизменным, внеся правки, требуемые семантикой языка:

От нас потребовали изменить:

  • Очередь не может быть построена на базовом контейнере vector у которого нет метода pop_front(), но может строиться на list, deque, или любом другом контейнере, реализующем базовый набор методов (front(), push_back(), pop_front()), по умолчанию используется deque.

  • У адаптера queue нет метода top(), а есть метод аналогичного смысла front().

И в итоге получаем (сравните с результатами для стека!):

stack, programming for beginners

Рассылка новых уроков по программированию:

Обобщённые численные алгоритмы. STL (часть 14)




Обобщённые численные алгоритмы STL c++Следующую, очень нужную и очень мощную группу алгоритмов STL представляют обобщённые численные алгоритмы (заголовочный файл <numeric>). Это не какие-то особые вычислительные методы, как можно подумать исходя из названия. Это алгоритмы, позволяющие применять общеизвестные библиотечные или свои собственные вычислительные функции ко всей совокупности элементов контейнера. А поскольку так, то и вызываются они подобно всем другим алгоритмам STL. Используются такие обобщённые алгоритмы, главным образом в математических вычислениях применительно к контейнерам, содержащим числовые элементы. Но это совсем не обязательно. И если вас не интересуют численные вычисления (например из области цифровой обработки сигналов), то вы можете просто безболезненно пропустить эту часть изложения…

Перечислим представленные STL обобщённые численные алгоритмы: iota (создание монотонно возрастающей последовательности), accumulate (накопление), inner_product (скалярное произведение), partial_sum (частичная сумма), adjacent_difference (смежная разность).

Иллюстрацию работы лучше всего провести на самом используемом и интуитивно понятном алгоритме accumulate. Этот алгоритм редуцирует (уменьшает размерность) контейнера с накоплением значений. В частности, для простых числовых значений он сворачивает vector<> или list<> до одиночного скалярного результирующего значения.

Алгоритм accumulate (как, впрочем, и большинство других) имеет 2 синтаксические формы:

В 1-й форме (она менее интересная) алгоритм суммирует значения элементов контейнера. Не забываем при этом, что для типа string, например, операция ‘+‘ означает конкатенацию, склеивание). Во 2-й форме алгоритм накапливает результат бинарной операции (функции 2-х переменных), применяемой к накапливаемому значению (аккумулятору) и поочерёдно к каждому элементу контейнера.

Непонятно? Это мощная техника, и сейчас всё станет понятно из примера…

В математической статистике находят применение несколько видов среднего значения для числовой последовательности:

  • Среднее арифметическое:

    sa1

  • Среднее геометрическое:

    sg2

  • Среднее гармоническое:

    sr3

  • Среднее квадратическое:

    sq4

Не станем углубляться в смысл каждого из вариантов. Мы сделаем приложение, которое подсчитывает эти средние и ещё некоторые характеристики (дисперсию, средне квадратичное отклонение) для вводимой числовой последовательности. Входную последовательность вводим либо с терминала, либо перенаправлением из предварительно подготовленного файла данных:

Как легко видеть, каждая из записанных выше сложных математических формул вычисляется всего лишь в одну строку, используя технику обобщённых алгоритмов:

Обобщённые численные алгоритмы stl в c++

Здесь мы можем наблюдать известное соотношение, которое подтверждает корректность наших вычислений. Заключается оно в том, что для любой последовательности чисел среднее арифметическое больше или равно среднего геометрического, которое, в свою очередь, больше или равно среднего гармонического. Причём равенство в этих утверждениях достигается только если все члены числовой последовательности равны между собой:

Обобщённые численные алгоритмы stl в c++

Возвратимся к изучению кода. Первый вызов алгоритма accumulate( b, e, 0. ) демонстрирует 1-ю форму использования: значения контейнера суммируются с начальным значением 0.0.

Предупреждение!: Запись точки в константе начального значения, указывающая, что это вещественное значение — принципиально важна. Без этого код будет компилироваться даже без предупреждений, но выполняться с совершенно неверными и крайне сложно толкуемыми результатами! Это связано с тем, что алгоритмы определены как template, и тип 3-го параметра определит для какого типа данных будут задействованы внутренние операции при накоплении.

Все остальные (4 штуки) вызовы accumulate() используют 2-ю форму вызова – передают 4-м параметром функцию накопления. Как видно из примеров, она принимает параметрами текущее накопленное значение и очередной элемент контейнера. А возвращает результат накапливающей операции. Для наглядности, все накапливающие функции записаны в примере в простом и ясном виде. На практике, чтобы избежать зависимости от типа обрабатываемых данных, их также обычно записывают, как шаблонные функции. Тогда это может выглядеть так:

Наконец, обратите внимание, если не обратили до сих пор, что при накоплении сумм мы используем начальное значение 0 (3-й параметр accumulate() ), а при накоплении произведений, естественно, 1, с соответствующим типом данных.

Рассылка новых уроков по программированию:

Сортировка структур. STL Часть 13




сортировка структур с++, stl для начинающихПоказанные в предыдущей части разнообразные сортировки — гибкий и красивый механизм на все случаи жизни. Вот только на практике сортировать в чистом виде последовательности почти никогда не приходится. Это всё из области учебно-показательных задач. На практике куда чаще стоит задача сортировать достаточно объёмные структуры данных (объёмные даже не по своему размеру, а по числу своих полей). И сортировать (или пересортировывать) их предстоит по значениям самых разных полей этих самых структур. Но и здесь на помощь приходят алгоритмы STL, особенно при использовании их совместно с функторами.

Посмотрим типовую модельную задачу, которую мы уже видели раньше — описание учебной группы или факультета:

Программа запрашивает номер поля data, по которому будет вестись сортировка (на самом деле — сравнение). Если этот номер вводится, как положительное число, то сортировка по этому полю идёт в порядке возрастания. Если же номер вводится со знаком минус — то порядок сортировки меняется на обратный:

сортировка структур с++, stl для начинающихсортировка структур с++, stl для начинающих

Обратите внимание, что алгоритму сортировки совершенно безразлично что сортировать: если это числовые данные, то по величине, а если строчные, то в лексографическом порядке.

Рассылка новых уроков по программированию:

Сортировка. STL (часть 12)




сортировка в с++, stlСовершенно особую группу алгоритмов составляют сортировки — сортировать в практике приходится самые разнообразные объекты и по самым разнообразным критериям. Анализ алгоритмов сортировки хорошо и обстоятельно изучен, как ни один другой раздел вычислительной математики. Основным вопросом любого алгоритма сортировки является его вычислительная сложность — число операций сравнения-обмена, требуемых для сортировки последовательности длины N, так называемое O( N ).

Неприятным обстоятельством является то, что для разных алгоритмов различаются средняя сложность (на большинстве тестовых последовательностей) и максимальная сложность (на наихудшей для метода тестовой последовательности). Для нескольких десятков алгоритмов сортировки, предлагаемых в процессе обучения программированию, показано, что подавляющее большинство из них (интуитивно понятных) является худшими и в смысле средней и в смысле максимальной сложности. Как пример, популярная у студентов пузырьковая сортировка является наихудшей из всех вообще известных.

Эффективными (по сложности) из всего множества методов являются только несколько методов быстрых рекурсивных сортировок. Они то и представлены в реализациях алгоритмов STL. Стандарты не настаивают на жёстком ограничении на внутренних механизмах их реализации, поэтому могут быть варианты в зависимости от используемой библиотеки.

Теперь, обладая некоторыми знаниями об алгоритмах, функторах и общем состоянием дел с сортировками, мы готовы рассмотреть варианты реализации всего этого в своём коде. Для начала мы разнообразными способами сортируем числовые последовательности. Пример великоват, но он предназначен не только, и не сколько, для иллюстрации, как для последующего самостоятельного экспериментирования:

Перед компиляцией программы, в MVS нажмите Alt+F7 и внесите Аргументы команды ?30 +3:сортировка в с++

Некоторая громоздкость примера связана с тем, что мы в одном коде объединяем и все предоставленные STL алгоритмы сортировки, и разнообразные тестовые сортируемые последовательности, например:

  • Несколько случайных (?) последовательностей длины 30, сортируемых с использованием (3) функтора сравнения, и детализированным (+) выводом входной и выходной последовательности:

    сортировка в с++

  • Инверсная (обратная, убывающая) последовательность, сортируемая (6) «в куче» с использованием бинарного дерева (аргументы команды -30 +6 ):сортировка в с++

  • Длинная (1000000) последовательность, в тех же, что и предыдущий случай, условиях, но с выводом только диагностики корректности результата (аргументы команды -1000000 6 ):

    сортировка в с++

Библиотека STL предоставляет 3 группы алгоритмов сортировки:

  • sort() – наиболее быстрая сортировка в среднем ( O( N * log( N ) ), но которая может «проваливаться» в худшем случае до O( N * N ) (а это очень плохой показатель);

  • sort_heap() – сортировка в «в куче», с использованием бинарного дерева, сложность которой всегда не хуже O( N + N * log( N ) ) (это хуже sort() в среднем, но лучше в наихудшем случае);

  • stable_sort() – «устойчивая» сортировка слиянием, устойчивость которой означает, что она сохраняет относительный порядок равных элементов после сортировки. Это иногда очень важно. Сложность этого алгоритма не намного уступает sort();

Используйте тот алгоритм, который наиболее соответствует ограничениям вашей задачи.

Рассылка новых уроков по программированию: