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

У шаблона list имеются еще четыре функции, которые здесь не показаны:

функция remove if() получает предикат для отбора удаляемых объектов;

функция uniqueO получает бинарный предикат для проверки уникаль ности;

функция merge() получает дополнительный аргумент, выполняющий срав нение;

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

Сравнение списка с множеством

Как видно из предыдущего примера, для получения отсортированной последова тельности элементов без дубликатов можно воспользоваться множеством (кон тейнер set). Интересно сравнить быстродействие этих двух контейнеров:

: C07:LiStVsSet.cpp

Сравнение списка и множества по быстродействию

#include <algorithm>

#1 nclude <cstdl1b>

#incl ude <ct1me>

#1nclude <iostream>

#1ncl ude <iteraror>

#Tncl ude <l1st>

#1 ncl ude <set>

#include PrintContainer.h

using namespace std:

class Obj {

int a[20]: Чтобы занять больше памяти

int val: public:

ObjO : vaKrandO % 500) {} friend bool

operator<(const Obj& a. const Obj& b) ( return a.val < b.val:

friend bool

operator==(const Obj& a. const Obj& b) { return a.val == b.val:

friend ostreamS

operator (ostream& os, const Obj& a) ( return OS a.val:

struct ObjGen { Obj OperatorOO ( return ObjO: }

Перестановка интервалов

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

: С07:Swapping.срр {-bor}

Функция swapO поддерживается всеми основными

последовательными контейнерами

{L} Noisy.h

#include <algorithm>

#include <deque>

#include <iostream>

int mainO ( const int SZ = 5000; srand(time(0)): list<Obj> lo: clock t ticks = clockO: generate n(back inserter(lo). SZ. ObjGenO): lo.sortO: lo.unique():

cout list: clockO - ticks endl: set<Obj> so: ticks = clockO:

generate n(inserter(so. so.begin()).

SZ, ObjGenO): cout set: clockO - ticks endl: print(lo): print(so): } /:-

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

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

: С07:PrintContainer.h

Вывод последовательного контейнера

#ifndef PRINT CONTAINER H

#define PRINT CONTAINER H

#include ../СОб/PrintSequence.h

tempiate<class Cont>

void print(Cont& c. const char* nm = .

const char* sep = \n .

std::ostream& os = std::cout) ( printCc.beginO. c.endO. nm. sep. os):

#endif III:-

Определяемый здесь шаблон print() просто вызывает шаблон функции print(), которая определялась в заголовке PrintSequence.h (см. главу 6).

#include <1terator>

#1nclude <list>

#include <vector>

#1nclude Noisy.h

#1nclude PrintContelner.h

using namespace std:

ostream iterator<Noisy> out(cout, ):

tempiate<class Cont> void testSwap(char* cname) ( Cont cl. c2:

generate n(back inserter(cl). 10. NoisyGenO):

generate n(back inserter(c2). 5, NoisyGenO):

cout \n cname : endl:

printed, cl ): print(c2. c2 );

cout \n Swapping the cname : endl:

cl.swap(c2):

pnntCcl. cl ): print(c2, c2 ):

int main() {

testSwap<vector<Noisy> >( vector ):

testSwap<deque<Noisy> >( deque ):

testSwap<list<Noi sy> >( 1i st ): } III:-

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

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

Множество

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

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