// из потока
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
, то в контейнере нет такого элемента.
