C++17 STL Стандартная библиотека шаблонов

Как это работает 

Контейнер std::priority_queue очень прост в использовании. Нам понадобилось всего три функции.

1. q.push(item) помещает элемент в очередь.

2. q.top() возвращает ссылку на элемент, который первым покинет очередь.

3. q.pop() удаляет первый элемент из очереди.

Но каким образом происходит упорядочение элементов? Мы сгруппировали числа, указывающие на приоритет, и строки, описывающие элементы списка текущих дел, в объекты типа std::pair, что позволило упорядочить элементы автоматически. Если у нас есть экземпляр p типа std::pair, std::string>, то с помощью нотации p.first можно получить число, а благодаря нотации p.second — строку. Мы сделали это в цикле, где выводятся на экран все наши текущие дела.

Но как очередь с приоритетом узнала, что пара {2, "do homework"} важнее, чем {0, "watch tv"}? Мы ведь не говорили ей сравнивать числовую часть.

Оператор сравнения < по-разному обрабатывает разные ситуации. Предположим, у нас имеется сравнение left < right, где left и right представляют собой пары.

1. Если выполняется условие left.first != right.first, то возвращается результат сравнения left.first < right.first.

2. Если выполняется условие left.first == right.first, то возвращается результат сравнения left.second < right.second.

Таким образом можно упорядочить все, что нам угодно. Важным здесь является тот факт, что приоритет — первый член пары, а описание — второй. В противном случае контейнер std::priority_queue упорядочил бы элементы по алфавиту, а не по числам, указывающим на приоритеты. (В данном случае очередь предложит нам сначала посмотреть телевизор (watch TV), а затем, спустя какое-то время, заняться домашней работой (do homework). Это бы понравилось самым ленивым из нас!) 

Глава 3 Итераторы

В этой главе:

□ построение собственного итерабельного диапазона данных;

□ обеспечение совместимости ваших итераторов с категориями итераторов STL;

□ использование оболочек для итераторов для заполнения обобщенных структур данных;

□ реализация алгоритмов с помощью итераторов;

□ перебор (итерирование) в обратную сторону с применением обратных адаптеров для итераторов;

□ завершение перебора диапазонов данных с использованием ограничителей;

□ автоматическая проверка кода итератора с помощью проверяемых итераторов;

□ создание собственного адаптера для итераторов-упаковщиков. 

Введение

Итераторы — крайне важная концепция языка С++. Библиотека STL создавалась максимально гибкой и обобщенной, а итераторы способствуют этому. К сожалению, иногда применять их несколько утомительно, и многие новички избегают их и возвращаются к стилю программирования, свойственному языку С. Программист, который избегает использования итераторов, по сути, отказывается от половины потенциала библиотеки STL. В данной главе мы рассмотрим итераторы, постаравшись разобраться в их достоинствах и недостатках. Надеюсь, показанные примеры помогут вам понять основные принципы работы с итераторами.

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

□ Один алгоритм, который работает с массивом, проверяя его размер и суммируя все его члены, выглядит так:

int sum {0};

for (size_t i {0}; i < array_size; ++i) { sum += array[i]; }

□ Другой алгоритм, который работает со связанным списком и итерирует по нему до конца, выглядит следующим образом:

int sum {0};

while (list_node != nullptr) {

  sum += list_node->value; list_node = list_node->next;

}

Оба алгоритма суммируют целые числа, но какая часть введенных нами символов непосредственно связана с решением задачи? Работает ли какой-нибудь из этих алгоритмов с другими видами структур данных, например с std::map, или нужно реализовывать еще одну версию алгоритма суммирования? Отсутствие итераторов приведет к нелепым решениям.

Только с помощью итераторов можно реализовать этот алгоритм в обобщенном виде:

int sum {0};

for (int i : array_or_vector_or_map_or_list) { sum += i; }