Шрифт:
{
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
, то в контейнере нет такого элемента.
find
(представляющий собой линейный поиск). Алгоритмы бинарного поиска в стандартной библиотеке называются binary_search
и equal_range
. Что мы понимаем под словом “длинные”? Это зависит от обстоятельств, но десяти элементов обычно уже достаточно, чтобы продемонстрировать преимущество алгоритма binary_search
над алгоритмом find
. На последовательности, состоящей из тысячи элементов, алгоритм binary_search
работает примерно в 200 раз быстрее, чем алгоритм find
, потому что он имеет сложность O(log2N) (см. раздел 21.6.4). Алгоритм
binary_search
имеет два варианта.
template<class Ran, class T>
bool binary_search(Ran first,Ran last,const T& val);
template<class Ran,class T,class Cmp>
bool binary_search(Ran first,Ran last,const T& val,Cmp cmp);
binary_search
просто сообщает, содержит ли контейнер заданное значение.
void f(vector<string>& vs) // vs упорядочено
{
if (binary_search(vs.begin,vs.end,"starfruit")) {
// в контейнере есть строка "starfruit"
}
// ...
}
binary_search
— идеальное средство, если нас интересует, есть заданное значение в контейнере или нет. Если нам нужно найти этот элемент, мы можем использовать функции lower_bound
, upper_bound
или equal_range
(разделы 23.4 и Б.5.4). Как правило, это необходимо, когда элементы контейнера представляют собой объекты, содержащие больше информации, чем просто ключ, когда в контейнере содержатся несколько элементов с одинаковыми ключами или когда нас интересует, какой именно элемент удовлетворяет критерию поиска. Задание
После выполнения каждой операции выведите содержание вектора на экран.
1. Определите структуру
struct Item { string name; int iid; double value; /* ... */ };
, создайте контейнер vector<Item> vi
и заполните его десятью строками из файла. 2. Отсортируйте контейнер
vi
по полю name
. 3. Отсортируйте контейнер
vi
по полю iid
. 4. Отсортируйте контейнер
vi
по полю value
; выведите его содержание на печать в порядке убывания значений (т.е. самое большое значение должно быть выведено первым). 5. Вставьте в контейнер элементы
Item("horse shoe",99,12.34)
и Item("Canon S400",9988,499.95)
. 6. Удалите два элемента Item из контейнера
vi
, задав поля name
. 7. Удалите два элемента Item из контейнера
vi
, задав поля iid
. 8. Повторите упражнение с контейнером типа
list<Item>
, а не vector<Item>
. Теперь поработайте с контейнером
map
.