Чтение онлайн

на главную - закладки

Жанры

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

При копировании, сравнении и выполнении других операций над двумя последовательностями первая из них задается парой итераторов

[b:e]
, а вторая — только одним итератором
b2
, который считается началом последовательности, содержащей элементы, количество которых достаточно для выполнения алгоритма, например, столько же, сколько элементов в первой последовательности:
[b2:b2+(e–b)]
.

Некоторые алгоритмы, такие как

sort
, используют итераторы произвольного доступа, а многие другие, такие как
find
, только считывают элементы с помощью однонаправленного
итератора.

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

Б.5.1. Немодицифирующие алгоритмы для последовательностей

Немодифицирующий алгоритм просто считывает элементы последовательности; он не изменяет порядок следования элементов последовательности и не изменяет их значения.

Предотвратить модификацию элементов операцией, передаваемой алгоритму

for_each
, невозможно; это считается приемлемым. Передача операции, изменяющей проверяемые ею элементы, другим алгоритмам (например, count или
==
) недопустима.

Рассмотрим пример правильного использования алгоритма.

bool odd(int x) { return x&1; }

int n_even(const vector<int>& v) // подсчитывает количество четных

// чисел в v

{

return v.size–count_if(v.begin,v.end,odd);

}

Б.5.2. Алгоритмы, модифицирующие последовательности

Модифицирующие алгоритмы могут изменять элементы последовательностей, являющихся их аргументами.

Алгоритм

shuffle
перетасовывает последовательность точно так же, как перетасовывается колода карт; иначе говоря, после перетасовки элементы следуют в случайном порядке, причем смысл слова “случайно” определяется распределением, порожденным датчиком случайных чисел.

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

remove
, не может уменьшить длину входной последовательности, удалив (стерев) ее элементы; вместо этого он передвигает эти элементы к началу последовательности.

typedef vector<int>::iterator VII;

void print_digits(const string& s, VII b, VII e)

{

cout << s;

while (b!=e) { cout << *b; ++b; }

cout << '\n';

}

void ff

{

int a[] = { 1,1,1,2,2,3,4,4,4,3,3,3,5,5,5,5,1,1,1 };

vector<int> v(a,a+sizeof(a)/sizeof(int));

print_digits("all: ",v.begin, v.end);

vector<int>::iterator pp = unique(v.begin,v.end);

print_digits("head: ",v.begin,pp);

print_digits("tail: ",pp,v.end);

pp=remove(v.begin,pp,4);

print_digits("head: ",v.begin,pp);

print_digits("tail: ",pp,v.end);

}

Результат

приведен ниже.

all: 1112234443335555111

head: 1234351

tail: 443335555111

head: 123351

tail: 1443335555111

Б.5.3. Вспомогательные алгоритмы

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

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

uninitialized_fill
и
uninitialized_copy
, должны иметь встроенный тип или быть неинициализированными.

Б.5.4. Сортировка и поиск

Сортировка и поиск относятся к категории фундаментальных алгоритмов. В то же время потребности программистов довольно разнообразны. Сравнение по умолчанию выполняется с помощью оператора

<
, а эквивалентность пар значений
a
и
b
определяется условием
!(a<b)&&!(b<a)
, а не оператором
==
.

Рассмотрим следующий пример:

vector<int> v;

list<double> lst;

v.push_back(3); v.push_back(1);

v.push_back(4); v.push_back(2);

lst.push_back(0.5); lst.push_back(1.5);

lst.push_back(2); lst.push_back(2.5); // список lst упорядочен

sort(v.begin,v.end); // сортировка вектора v

vector<double> v2;

merge(v.begin,v.end,lst.begin,lst.end,back_inserter(v2));

Поделиться:
Популярные книги

Печать Пожирателя

Соломенный Илья
1. Пожиратель
Фантастика:
попаданцы
аниме
сказочная фантастика
фэнтези
5.00
рейтинг книги
Печать Пожирателя

Привет из Загса. Милый, ты не потерял кольцо?

Лисавчук Елена
Любовные романы:
современные любовные романы
5.00
рейтинг книги
Привет из Загса. Милый, ты не потерял кольцо?

Мастер 2

Чащин Валерий
2. Мастер
Фантастика:
фэнтези
городское фэнтези
попаданцы
технофэнтези
4.50
рейтинг книги
Мастер 2

Нечто чудесное

Макнот Джудит
2. Романтическая серия
Любовные романы:
исторические любовные романы
9.43
рейтинг книги
Нечто чудесное

Клан

Русич Антон
2. Долгий путь домой
Фантастика:
боевая фантастика
космическая фантастика
5.60
рейтинг книги
Клан

Имя нам Легион. Том 3

Дорничев Дмитрий
3. Меж двух миров
Фантастика:
боевая фантастика
рпг
аниме
5.00
рейтинг книги
Имя нам Легион. Том 3

Запасная дочь

Зика Натаэль
Фантастика:
фэнтези
6.40
рейтинг книги
Запасная дочь

Убивать чтобы жить 7

Бор Жорж
7. УЧЖ
Фантастика:
героическая фантастика
космическая фантастика
рпг
5.00
рейтинг книги
Убивать чтобы жить 7

У врага за пазухой

Коваленко Марья Сергеевна
5. Оголенные чувства
Любовные романы:
остросюжетные любовные романы
эро литература
5.00
рейтинг книги
У врага за пазухой

Кодекс Охотника. Книга XXI

Винокуров Юрий
21. Кодекс Охотника
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Кодекс Охотника. Книга XXI

Генерал Скала и ученица

Суббота Светлана
2. Генерал Скала и Лидия
Любовные романы:
любовно-фантастические романы
6.30
рейтинг книги
Генерал Скала и ученица

Оцифрованный. Том 1

Дорничев Дмитрий
1. Линкор Михаил
Фантастика:
боевая фантастика
попаданцы
аниме
5.00
рейтинг книги
Оцифрованный. Том 1

Его маленькая большая женщина

Резник Юлия
Любовные романы:
современные любовные романы
эро литература
8.78
рейтинг книги
Его маленькая большая женщина

Хуррит

Рави Ивар
Фантастика:
героическая фантастика
попаданцы
альтернативная история
5.00
рейтинг книги
Хуррит