Алгоритмы сортировки и упорядочения

Четырнадцать алгоритмов сортировки и упорядочения предлагают различные способы упорядочения элементов контейнера. Разбиение (partition) – это разделение элементов контейнера на две группы: удовлетворяющие и не удовлетворяющие некоторому условию. Так, можно разбить контейнер по признаку четности/нечетности чисел или в зависимости от того, начинается слово с заглавной или со строчной буквы. Устойчивый (stable) алгоритм сохраняет относительный порядок элементов с одинаковыми значениями или удовлетворяющих одному и тому же условию. Например, если дана последовательность:

{ "pshew", "honey", "Tigger", "Pooh" }

то устойчивое разбиение по наличию/отсутствию заглавной буквы в начале слова генерирует последовательность, в которой относительный порядок слов в каждой категории сохранен:

{ "Tigger", "Pooh", "pshew", "honey" }

При использовании неустойчивой версии алгоритма сохранение порядка не гарантируется. (Отметим, что алгоритмы сортировки нельзя применять к списку и ассоциативным контейнерам, таким, как множество (set) или отображение (map).)

stable_partition()

Алгоритмы удаления и подстановки

Пятнадцать алгоритмов удаления и подстановки предоставляют различные способы замены или исключения одного элемента или целого диапазона. unique() удаляет одинаковые соседние элементы. iter_swap() обменивает значения элементов, адресованных парой итераторов, но не модифицирует сами итераторы.

unique_copy()

Алгоритмы перестановки

Рассмотрим последовательность из трех символов: {a,b,c}. Для нее существует шесть различных перестановок: abc, acb, bac, bca, cab и cba, лексикографически упорядоченных на основе оператора “меньше”. Таким образом, abc – это первая перестановка, потому что каждый элемент меньше последующего. Следующая перестановка – acb, поскольку в начале все еще находится a – наименьший элемент последовательности. Соответственно перестановки, начинающиеся с b, предшествуют тем, которые начинаются с с. Из bac и bca меньшей является bac, так как последовательность ac лексикографически меньше, чем ca. Если дана перестановка bca, то можно сказать, что предшествующей для нее будет bac, а последующей – cab. Для перестановки abc нет предшествующей, а для cba – последующей.

next_permutation(), prev_permutation()

Численные алгоритмы

Следующие четыре алгоритма реализуют численные операции с контейнером. Для их использования необходимо включить заголовочный файл <numeric>.

accumulate(), partial_sum(), inner_product(), adjacent_difference()

Алгоритмы генерирования и модификации

Шесть алгоритмов генерирования и модификации либо создают и заполняют новую последовательность, либо изменяют значения в существующей.

fill(), fill_n(), for_each(), generate(),generate_n(), transform()

Алгоритмы сравнения

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

min(), min_element(), mismatch()

Алгоритмы работы с множествами

Четыре алгоритма этой категории реализуют теоретико-множественные операции над любым контейнерным типом. При объединении создается отсортированная последовательность элементов, принадлежащих хотя бы одному контейнеру, при пересечении – обоим контейнерам, а при взятии разности – принадлежащих первому контейнеру, но не принадлежащих второму. Наконец, симметрическая разность – это отсортированная последовательность элементов, принадлежащих одному из контейнеров, но не обоим.

set_symmetric_difference()

Алгоритмы работы с хипом

Хип (heap) – это разновидность двоичного дерева, представленного в массиве. Стандартная библиотека предоставляет такую реализацию хипа, в которой значение ключа в любом узле больше либо равно значению ключа в любом потомке этого узла.

make_heap(), pop_heap(), push_heap(), sort_heap()

Когда нельзя использовать обобщенные алгоритмы

Ассоциативные контейнеры (отображения и множества) поддерживают определенный порядок элементов для быстрого поиска и извлечения. Поэтому к ним не разрешается применять обобщенные алгоритмы, меняющие порядок, такие, как sort() и partition(). Если в ассоциативном контейнере требуется переставить элементы, то необходимо сначала скопировать их в последовательный контейнер, например в вектор или список.

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

vector<string>::iterator vec_iter = vec.begin() + 7;

Такая форма вполне допустима и инициализирует vec_iter адресом восьмого элемента вектора, но запись

list<string>::iterator list_iter = slist.begin() + 7;

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

Поскольку список не поддерживает произвольного доступа, то алгоритмы merge(), remove(), reverse(), sort() и unique() лучше к таким контейнерам не применять, хотя ни один из них явно не требует наличия соответствующего итератора. Вместо этого для списка определены специализированные версии названных операций в виде функций-членов, а также операция splice():

· list::merge() объединяет два отсортированных списка

· list::remove() удаляет элементы с заданным значением

· list::remove_if()удаляет элементы, удовлетворяющие некоторому условию

· list::reverse() переставляет элементы списка в обратном порядке

· list::sort() сортирует элементы списка

· list::splice() перемещает элементы из одного списка в другой

· list::unique() оставляет один элемент из каждой цепочки одинаковых смежных элементов

Операция list_merge()

void list::merge( list rhs, Compare comp );

Элементы двух упорядоченных списков объединяются либо на основе оператора “меньше”, определенного для типа элементов в контейнере, либо на основе указанной пользователем операции сравнения. (Заметьте, что элементы списка rhs перемещаются в список, для которого вызвана функция-член merge(); по завершении операции список rhs будет пуст.) Например:

ilist1.merge( ilist2 );

После выполнения операции merge() список ilist2 пуст, а ilist1 содержит первые 15 чисел Фибоначчи в порядке возрастания.

Операция list::remove()

void list::remove( const elemType &value );

Операция remove() удаляет все элементы с заданным значением:

ilist1.remove( 1 );

Операция list::remove_if()

void list::remove_if( Predicate pred );

Операция remove_if() удаляет все элементы, для которых выполняется указанное условие, т.е. предикат pred возвращает true. Например:

ilist1.remove_if( Even() );

удаляет все четные числа из списка, определенного при рассмотрении merge().

Операция list::reverse()

void list::reverse();

Операция reverse() изменяет порядок следования элементов списка на противоположный:

ilist1.reverse();

Операция list::sort()

void list::sort( Compare comp );

По умолчанию sort() упорядочивает элементы списка по возрастанию с помощью оператора “меньше”, определенного в классе элементов контейнера. Вместо этого можно явно передать в качестве аргумента оператор сравнения. Так,

list1.sort();

упорядочивает list1 по возрастанию, а

list1.sort( greater<int>() );

упорядочивает list1 по убыванию, используя оператор “больше”.

Операция list::splice()

iterator first, iterator last );

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

list< int > ilist2( array, array + 2 ); // содержит 0, 1

то следующее обращение к splice() перемещает первый элемент ilist1 в ilist2. Теперь ilist2 содержит элементы 0, 1 и 0, тогда как в ilist1 элемента 0 больше нет.

ilis2.splice( ilist2.end(), ilist1, ilist1.begin() );

В следующем примере применения splice() передаются два итератора, ограничивающие диапазон перемещаемых элементов:

ilist2.splice( ilist2.begin(), ilist1, first, last );

В данном случае элементы 2, 3, 5 и 8 удаляются из ilist1 и вставляются в начало ilist2. Теперь ilist1 содержит пять элементов 1, 1, 13, 21 и 34. Для их перемещения в ilist2 можно воспользоваться третьей вариацией операции splice():

ilist2.splice( pos, ilist1 );

Итак, список ilist1 пуст. Последние пять элементов перемещены в позицию списка ilist2, предшествующую той, которую занимает элемент 5.

Операция list::unique()

void list::unique( BinaryPredicate pred );

Операция unique() удаляет соседние дубликаты. По умолчанию при сравнении используется оператор равенства, определенный для типа элементов контейнера. Например, если даны значения {0,2,4,6,4,2,0}, то после применения unique() список останется таким же, поскольку в соседних позициях дубликатов нет. Но если мы сначала отсортируем список, что даст {0,0,2,2,4,4,6}, а потом применим unique(), то получим четыре различных значения {0,2,4,6}.

ilist.unique();

Вторая форма unique() принимает альтернативный оператор сравнения. Например,

ilist.unique( EvenPair() );

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

Эти операции, являющиеся членами класса, следует предпочесть соответствующим обобщенным алгоритмам при работе со списками. Остальные обобщенные алгоритмы, такие, как find(), transform(), for_each() и т.д., работают со списками так же эффективно, как и с другими контейнерами (еще раз напомним, что подробно все алгоритмы рассматриваются в Приложении).

Упражнение 12.8

Измените программу из раздела 12.2, используя список вместо вектора.

Часть IV

Объектное программирование

В части 4 мы сосредоточимся на объектном программировании, т.е. на применении классов C++ для определения новых типов, манипулировать которыми так же просто, как и встроенными. Создавая новые типы для описания предметной области, C++ помогает программисту писать более легкие для понимания приложения. Классы позволяют отделить детали, касающиеся реализации нового типа, от определения интерфейса и операций, предоставляемых пользователю. При этом уделяется меньше внимания мелочам, из-за чего программирование становится таким утомительным занятием. Значимые для приложения типы можно реализовать всего один раз, после чего использовать повторно. Средства, обеспечивающие инкапсуляцию данных и функций, необходимых для реализации типа, помогают значительно упростить последующее сопровождение и развитие приложения.

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

В главе 14 изучаются предоставляемые C++ средства инициализации и уничтожения объектов класса, а также присваивания им значений путем применения таких специальных функций-членов класса, как конструкторы, деструкторы и копирующие конструкторы. Мы рассмотрим вопрос о почленной инициализации и копировании, когда объект класса инициализируется или ему присваивается значение другого объекта того же класса.

В главе 15 мы расскажем о перегрузке операторов, которая позволяет использовать операнды типа класса со встроенными операторами, описанными в главе 4. Таким образом, работа с объектами типа класса может быть сделана столь же понятной, как и работа со встроенными типами. В начале главы 15 представлены общие концепции и соображения, касающиеся проектирования перегрузки операторов, а затем рассмотрены конкретные операторы, такие, как присваивание, взятие индекса, вызов, а также специфичные для классов операторы new и delete. Иногда необходимо объявить перегруженный оператор, как друга класса, наделив его специальными правами доступа, в данной главе объясняется, зачем это нужно. Здесь же представлен еще один специальный вид функций-членов – конвертеры, которые позволяют программисту определить стандартные преобразования. Конвертеры неявно применяются компилятором, когда объекты класса используются в качестве фактических аргументов функции или операндов встроенного либо перегруженного оператора. Завершается глава изложением правил разрешения перегрузки функций с учетом аргументов типа класса, функций-членов и перегруженных операторов.

Тема главы 16 – шаблоны классов. Шаблон – это предписание для создания класса, в котором один или несколько типов параметризованы. Например, vector может быть параметризован типом элементов, хранящихся в нем, а buffer – типом элементов в буфере или его размером. В этой главе объясняется, как определить и конкретизировать шаблон. Поддержка классов в C++ теперь рассматривается иначе – в свете наличия шаблонов, и снова обсуждаются функции-члены, объявления друзей и вложенные типы. Здесь мы еще раз вернемся к модели компиляции шаблонов, описанной в главе 10, чтобы показать, какое влияние оказывают на нее шаблоны классов.

Классы

Механизм классов в C++ позволяет пользователям определять собственные типы данных. По этой причине их часто называют пользовательскими типами. Класс может наделять дополнительной функциональностью уже существующий тип. Так, например, IntArray, введенный в главе 2, предоставляет больше возможностей, чем тип “массив int”. С помощью классов можно создавать абсолютно новые типы, например Screen (экран) или Account (расчетный счет). Как правило, классы используются для абстракций, не отражаемых встроенными типами адекватно.

В этой главе мы узнаем, как определять типы и использовать объекты классов; увидим, что определение класса вводит как данные-члены, описывающие его, так и функции-члены, составляющие набор операций, применимых к объектам класса. Мы покажем, как можно обеспечить сокрытие информации, объявив внутреннее представление и реализацию закрытыми, но открыв операции над объектами. Говорят, что закрытое внутреннее представление инкапсулировано, а открытую часть класса называют его интерфейсом.

Далее в этой главе мы познакомимся с особым видом членов класса – статическими членами. Мы расскажем также, как можно использовать указатели на члены и функции-члены класса, и рассмотрим объединения, представляющие собой специализированный вид класса для хранения объектов разных типов в одной области памяти. Завершается глава обсуждением области видимости класса и описанием правил разрешения имен в этой области; затрагиваются такие понятия, как вложенные классы, классы-члены пространства имен и локальные классы.

Определение класса

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

class Screen { /* ... */ } myScreen, yourScreen;

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

Каждое определение вводит новый тип данных. Даже если два класса имеют одинаковые списки членов, они все равно считаются разными типами:

Second obj2 = obj1; // ошибка: obj1 и obj2 имеют разные типы

Тело класса определяет отдельную область видимости. Объявление членов внутри тела помещает их имена в область видимости класса. Наличие в двух разных классах членов с одинаковыми именами – не ошибка, эти имена относятся к разным объектам. (Подробнее об областях видимости классов мы поговорим в разделе 13.9.)

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

· написать ключевое слово class, а после него – имя класса. В предыдущем примере объект obj1 класса First объявлен именно таким образом;

· указать только имя класса. Так объявлен объект obj2 класса Second из приведенного примера.

Оба способа сослаться на тип класса эквивалентны. Первый заимствован из языка C и остается корректным методом задания типа класса; второй способ введен в C++ для упрощения объявлений.

Данные-члены

Данные-члены класса объявляются так же, как переменные. Например, у класса Screen могут быть следующие данные-члены:

};

Поскольку мы решили использовать строки для внутреннего представления объекта класса Screen, то член _screen имеет тип string. Член _cursor – это смещение в строке, он применяется для указания текущей позиции на экране. Для него использован переносимый тип string::size_type. (Тип size_type рассматривался в разделе 6.8.)

Необязательно объявлять два члена типа short по отдельности. Вот объявление класса Screen, эквивалентное приведенному выше:

};

Член класса может иметь любой тип:

};

Описанные данные-члены называются нестатическими. Класс может иметь также и статические данные-члены. (У них есть особые свойства, которые мы рассмотрим в разделе 13.5.)

Объявления данных-членов очень похожи на объявления переменных в области видимости блока или пространства имен. Однако их, за исключением статических членов, нельзя явно инициализировать в теле класса:

};

Данные-члены класса инициализируются с помощью конструктора класса. (Мы рассказывали о конструкторах в разделе 2.3; более подробно они рассматриваются в главе 14.)

Функции-члены

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

Функции-члены класса объявляются в его теле. Это объявление выглядит точно так же, как объявление функции в области видимости пространства имен. (Напомним, что глобальная область видимости – это тоже область видимости пространства имен. Глобальные функции рассматривались в разделе 8.2, а пространства имен – в разделе 8.5.) Например:

};

Определение функции-члена также можно поместить внутрь тела класса:

};

home() перемещает курсор в левый верхний угол экрана; get() возвращает символ, находящийся в текущей позиции курсора.

Функции-члены отличаются от обычных функций следующим:

· функция-член объявлена в области видимости своего класса, следовательно, ее имя не видно за пределами этой области. К функции-члену можно обратиться с помощью одного из операторов доступа к членам – точки (.) или стрелки (->):

myScreen.home();

(в разделе 13.9 область видимости класса обсуждается более детально);

· функции-члены имеют право доступа как к открытым, так и к закрытым членам класса, тогда как обычным функциям доступны лишь открытые. Конечно, функции-члены одного класса, как правило, не имеют доступа к данным-членам другого класса.

Функция-член может быть перегруженной (перегруженные функции рассматриваются в главе 9). Однако она способна перегружать лишь другую функцию-член своего класса. По отношению к функциям, объявленным в других классах или пространствах имен, функция-член находится в отдельной области видимости и, следовательно, не может перегружать их. Например, объявление get(int, int) перегружает лишь get() из того же класса Screen:

};

(Подробнее мы остановимся на функциях-членах класса в разделе 13.3.)

Доступ к членам

Часто бывает так, что внутреннее представление типа класса изменяется в последующих версиях программы. Допустим, опрос пользователей нашего класса Screen показал, что для его объектов всегда задается размер экрана 80 ´ 24. В таком случае было бы желательно заменить внутреннее представление экрана менее гибким, но более эффективным:

};

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

Если бы данные-члены класса Screen были открыты и доступны любой функции внутри программы, как отразилось бы на пользователях изменение внутреннего представления этого класса?

· все функции, которые напрямую обращались к данным-членам старого представления, перестали бы работать. Следовательно, пришлось бы отыскивать и изменять соответствующие части кода;

· так как интерфейс не изменился, то коды, манипулировавшие объектами класса Screen только через функции-члены, не пришлось бы модифицировать. Но поскольку сами функции-члены все же изменились, программу пришлось бы откомпилировать заново.

Сокрытие информации – это формальный механизм, предотвращающий прямой доступ к внутреннему представлению типа класса из функций программы. Ограничение доступа к членам задается с помощью секций тела класса, помеченных ключевыми словами public, private и protected – спецификаторами доступа. Члены, объявленные в секции public, называются открытыми, а объявленные в секциях private и protected соответственно закрытыми или защищенными.

· открытый член доступен из любого места программы. Класс, скрывающий информацию, оставляет открытыми только функции-члены, определяющие операции, с помощью которых внешняя программа может манипулировать его объектами;

· закрытый член доступен только функциям-членам и друзьям класса. Класс, который хочет скрыть информацию, объявляет свои данные-члены закрытыми;

· защищенный член ведет себя как открытый по отношению к производному классу и как закрытый по отношению к остальной части программы. (В главе 2 мы видели пример использования защищенных членов в классе IntArray. Детально они рассматриваются в главе 17, где вводится понятие наследования.)

В следующем определении класса Screen указаны секции public и private:

};

Согласно принятому соглашению, сначала объявляются открытые члены класса. (Обсуждение того, почему в старых программах C++ сначала шли закрытые члены и почему этот стиль еще кое-где сохранился, см. в книге [LIPPMAN96a].) В теле класса может быть несколько секций public, protected и private. Каждая секция продолжается либо до метки следующей секции, либо до закрывающей фигурной скобки. Если спецификатор доступа не указан, то секция, непосредственно следующая за открывающей скобкой, по умолчанию считается private.

Друзья

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

Объявление друга начинается с ключевого слова friend и может встречаться только внутри определения класса. Так как друзья не являются членами класса, то не имеет значения, в какой секции они объявлены. В примере ниже мы сгруппировали все подобные объявления сразу после заголовка класса:

};

Операторы ввода и вывода теперь могут напрямую обращаться к закрытым членам класса Screen. Простая реализация оператора вывода выглядит следующим образом:

}

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: