Программирование. Принципы и практика использования C++ Исправленное издание, стр. 300

// из потока

istream_iterator<string> eos; // сигнальная метка для ввода

ostream_iterator<string> oo(os," "); // создаем итератор

// вывода в поток

set<string> b(ii,eos); // b — вектор, который инициализируется

// данными из потока ввода

copy(b.begin(),b.end(),oo); // копируем буфер в поток вывода

}

Когда мы вставляем значение в контейнер

set

, дубликаты игнорируются. Более того, элементы контейнера

set

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

21.7.4. Алгоритм copy_if()

Алгоритм

copy()

выполняет копирование без каких-либо условий. Алгоритм

unique_copy()

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

template<class In,class Out,class Pred>

Out copy_if(In first,In last,Out res,Pred p)

// копирует элементы, удовлетворяющие предикату

{

while (first!=last) {

if (p(*first)) *res++ = *first;

++first;

}

return res;

}

Используя наш объект-функцию

Larger_than

из раздела 21.4, можем найти все элементы последовательности, которые больше шести.

void f(const vector<int>& v)

// копируем все элементы, которые больше шести

{

vector<int> v2(v.size());

copy_if(v.begin(),v.end(),v2.begin(),Larger_than(6));

// ...

}

Из-за моей ошибки этот алгоритм выпал из стандарта 1998 ISO Standard. В настоящее время эта ошибка исправлена, но до сих пор встречаются реализации языка С++, в которых нет алгоритма

copy_if

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

21.8. Сортировка и поиск

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

map

set

, или выполняя сортировку. Наиболее распространенной и полезной операцией сортировки в библиотеке STL является функция

sort()

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

sort()

в качестве критерия сортировки использует оператор

<

, но мы можем задавать свои собственные критерии.

template<class Ran> void sort(Ran first, Ran last);

template<class Ran,class Cmp> void sort(Ran first,Ran last,Cmp cmp);

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

struct No_case { // lowercase(x) < lowercase(y)

bool operator()(const string& x, const string& y) const

{

for (int i = 0; i<x.length(); ++i) {

if (i == y.length()) return false; // y<x

char xx = tolower(x[i]);

char yy = tolower(y[i]);

if (xx<yy) return true; // x<y

if (yy<xx) return false; // y<x

}

if (x.length()==y.length()) return false; // x==y

return true; // x<y (в строке x меньше символов)

}

};

void sort_and_print(vector<string>& vc)

{

sort(vc.begin(),vc.end(),No_case());

for (vector<string>::const_iterator p = vc.begin();

p!=vc.end(); ++p)

cout << *p << '\n';

}

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

find()

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

Предположим, что мы ищем значение x; посмотрим на средний элемент.

• Если значение этого элемента равно

x

, мы нашли его!

• Если значение этого элемента меньше

x

, то любой элемент со значением

х

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

• Если значение этого элемента больше

x

, то любой элемент со значением

х

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

• Если мы достигли последнего элемента (перемещаясь влево или вправо) и не нашли значение

x

, то в контейнере нет такого элемента.