С.Б. Липпман, Ж. Лажойе - Язык программирования С++ Вводный курс (1114944), страница 100
Текст из файла (страница 100)
Численные алгоритмыСледующие четыре алгоритма реализуют численные операции с контейнером. Для ихиспользования необходимо включить заголовочный файл <numeric>.accumulate(), partial_sum(), inner_product(), adjacent_difference()12.5.6. Алгоритмы генерирования и модификацииШесть алгоритмов генерирования и модификации либо создают и заполняют новуюпоследовательность, либо изменяют значения в существующей.fill(), fill_n(), for_each(), generate(),generate_n(), transform()12.5.7. Алгоритмы сравненияСемь алгоритмов дают разные способы сравнения одного контейнера с другим(алгоритмыmin()иmax()сравниваютдваэлемента).Алгоритм576С++ для начинающих577lexicographical_compare() выполняет лексикографическое (словарное) упорядочениеequal(), includes(), lexicographical_compare(), max(), max_element(),(см. также обсуждение перестановок и Приложение).min(), min_element(), mismatch()12.5.8.
Алгоритмы работы с множествамиЧетыре алгоритма этой категории реализуют теоретико-множественные операции надлюбым контейнерным типом. При объединении создается отсортированнаяпоследовательность элементов, принадлежащих хотя бы одному контейнеру, припересечении – обоим контейнерам, а при взятии разности – принадлежащих первомуконтейнеру, но не принадлежащих второму. Наконец, симметрическая разность – этоотсортированная последовательность элементов, принадлежащих одному из контейнеров,set_union(), set_intersection(), set_difference(),но не обоим.set_symmetric_difference()12.5.9. Алгоритмы работы с хипомХип (heap) – это разновидность двоичного дерева, представленного в массиве.Стандартная библиотека предоставляет такую реализацию хипа, в которой значениеключа в любом узле больше либо равно значению ключа в любом потомке этого узла.make_heap(), pop_heap(), push_heap(), sort_heap()12.6.КогдаалгоритмынельзяиспользоватьобобщенныеАссоциативные контейнеры (отображения и множества) поддерживают определенныйпорядок элементов для быстрого поиска и извлечения.
Поэтому к ним не разрешаетсяприменять обобщенные алгоритмы, меняющие порядок, такие, как 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() оставляет один элемент из каждой цепочки одинаковых смежныхэлементовvoid list::merge( list rhs );template <class Compare>12.6.1.
Операция list_merge()void list::merge( list rhs, Compare comp );Элементы двух упорядоченных списков объединяются либо на основе оператора“меньше”, определенного для типа элементов в контейнере, либо на основе указаннойпользователем операции сравнения. (Заметьте, что элементы списка rhs перемещаются всписок, для которого вызвана функция-член merge(); по завершении операции списокrhs будет пуст.) Например:578С++ для начинающихint array1[ 10 ] = { 34, 0, 8, 3, 1, 13, 2, 5, 21, 1 };int array2[ 5 ] = { 377, 89, 233, 55, 144 };list< int > ilist1( array1, array1 + 10 );list< int > ilist2( array2, array2 + 5 );// для объединения требуется, чтобы оба списка были упорядоченыilist1.sort(); ilist2.sort();ilist1.merge( ilist2 );После выполнения операции merge() список ilist2 пуст, а ilist1 содержит первые 15чисел Фибоначчи в порядке возрастания.12.6.2.
Операция list::remove()void list::remove( const elemType &value );Операция remove() удаляет все элементы с заданным значением:ilist1.remove( 1 );template < class Predicate >12.6.3. Операция list::remove_if()void list::remove_if( Predicate pred );Операция remove_if() удаляет все элементы, для которых выполняется указанноеclass Even {public:bool operator()( int elem ) { return ! (elem % 2 ); }};условие, т.е. предикат pred возвращает true. Например:ilist1.remove_if( Even() );удаляет все четные числа из списка, определенного при рассмотрении merge().12.6.4. Операция list::reverse()void list::reverse();579С++ для начинающихОперация reverse()противоположный:580изменяетпорядокследованияэлементовсписканаilist1.reverse();void list::sort();template <class Compare>12.6.5. Операция list::sort()void list::sort( Compare comp );По умолчанию sort() упорядочивает элементы списка по возрастанию с помощьюоператора “меньше”, определенного в классе элементов контейнера.
Вместо этого можноявно передать в качестве аргумента оператор сравнения. Так,list1.sort();упорядочивает list1 по возрастанию, аlist1.sort( greater<int>() );упорядочивает list1 по убыванию, используя оператор “больше”.void list::splice( iterator pos, list rhs );void list::splice( iterator pos, list rhs, iterator ix );void list::splice( iterator pos, list rhs,12.6.6. Операция list::splice()iterator first, iterator last );Операция splice() имеет три формы: перемещение одного элемента, всех элементов илидиапазона из одного списка в другой.
В каждом случае передается итератор,указывающий на позицию вставки,а перемещаемые элементы располагаютсяint array[ 10 ] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 };list< int > ilist1( array, array + 10 );непосредственно перед ней. Если даны два списка:list< int > ilist2( array, array + 2 );// содержит 0, 1то следующее обращение к splice() перемещает первый элемент ilist1 в ilist2.Теперь ilist2 содержит элементы 0, 1 и 0, тогда как в ilist1 элемента 0 больше нет.С++ для начинающих////////581ilist2.end() указывает на позицию, куда нужно переместить элементэлементы вставляются перед этой позициейilist1 указывает на список, из которого перемещается элементilist1.begin() указывает на сам перемещаемый элементilis2.splice( ilist2.end(), ilist1, ilist1.begin() );Вследующемпримерепримененияsplice()передаютсядваитератора,list< int >::iterator first, last;first = ilist1.find( 2 );last = ilist1.find( 13 );ограничивающие диапазон перемещаемых элементов:ilist2.splice( ilist2.begin(), ilist1, first, last );В данном случае элементы 2, 3, 5 и 8 удаляются из ilist1 и вставляются в началоilist2.
Теперь ilist1 содержит пять элементов 1, 1, 13, 21 и 34. Для их перемещенияlist< int >::iterator pos = ilist2.find( 5 );в ilist2 можно воспользоваться третьей вариацией операции splice():ilist2.splice( pos, ilist1 );Итак, список ilist1 пуст.
Последние пять элементов перемещены в позицию спискаilist2, предшествующую той, которую занимает элемент 5.void list::unique();template <class BinaryPredicate>12.6.7. Операция 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() принимает альтернативный оператор сравнения.
Например,С++ для начинающихclass EvenPair {public:bool operator()( int val1, val2 ){ return ! (val2 % val1 );}};ilist.unique( EvenPair() );удаляет соседние элементы, если второй элемент без остатка делится на первый.Эти операции, являющиеся членами класса, следует предпочесть соответствующимобобщенным алгоритмам при работе со списками. Остальные обобщенные алгоритмы,такие, как find(), transform(), for_each() и т.д., работают со списками так жеэффективно, как и с другими контейнерами (еще раз напомним, что подробно всеалгоритмы рассматриваются в Приложении).Упражнение 12.8Измените программу из раздела 12.2, используя список вместо вектора.582С++ для начинающих583Часть IVОбъектное программированиеВ части 4 мы сосредоточимся на объектном программировании, т.е.
на примененииклассов C++ для определения новых типов, манипулировать которыми так же просто, каки встроенными. Создавая новые типы для описания предметной области, C++ помогаетпрограммисту писать более легкие для понимания приложения. Классы позволяютотделить детали, касающиеся реализации нового типа, от определения интерфейса иопераций, предоставляемых пользователю. При этом уделяется меньше вниманиямелочам, из-за чего программирование становится таким утомительным занятием.Значимые для приложения типы можно реализовать всего один раз, после чегоиспользовать повторно.
Средства, обеспечивающие инкапсуляцию данных и функций,необходимых для реализации типа, помогают значительно упростить последующеесопровождение и развитие приложения.В главе 13 мы рассмотрим общий механизм классов: порядок их определения, концепциюсокрытия информации (т.е. отделение открытого интерфейса от закрытой реализации),способы определения и манипулирования объектами класса, область видимости,вложенные классы и классы как члены пространства имен.В главе 14 изучаются предоставляемые C++ средства инициализации и уничтоженияобъектов класса, а также присваивания им значений путем применения такихспециальных функций-членов класса, как конструкторы, деструкторы и копирующиеконструкторы.
Мы рассмотрим вопрос о почленной инициализации и копировании,когда объект класса инициализируется или ему присваивается значение другого объектатого же класса.В главе 15 мы расскажем о перегрузке операторов, которая позволяет использоватьоперанды типа класса со встроенными операторами, описанными в главе 4. Такимобразом, работа с объектами типа класса может быть сделана столь же понятной, как иработа со встроенными типами.
В начале главы 15 представлены общие концепции исоображения, касающиеся проектирования перегрузки операторов, а затем рассмотреныконкретные операторы, такие, как присваивание, взятие индекса, вызов, а такжеспецифичные для классов операторы new и delete. Иногда необходимо объявитьперегруженный оператор, как друга класса, наделив его специальными правами доступа,в данной главе объясняется, зачем это нужно. Здесь же представлен еще одинспециальный вид функций-членов – конвертеры, которые позволяют программистуопределитьстандартныепреобразования.Конвертерынеявноприменяютсякомпилятором, когда объекты класса используются в качестве фактических аргументовфункции или операндов встроенного либо перегруженного оператора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
