Оглавление

Отказ от ответственности

Все, что я собираюсь здесь рассказать, основано на моем 4-летнем опыте работы с C ++ (и если я говорю C ++, я также имею в виду STL). Кроме того, мне очень поможет то, что я реализовал дерево префиксов, совместимое с STL.

Имейте в виду, что для полного понимания этой статьи важно иметь хотя бы некоторый опыт работы с C ++ и STL. Так что если вам где-то надоест, возвращайтесь и переходите по этой ссылке. Это отличный ресурс, чтобы отточить свои навыки C ++, независимо от того, новичок вы или нет.

Введение в STL и контейнеры

Стандартная библиотека шаблонов (STL) - это (встроенная в язык) библиотека для C ++. Это означает, что Стандарт C ++ определяет все в STL, и разработчики компиляторов должны их реализовать, чтобы мы, простые смертные, могли просто включать и использовать их. STL состоит из 4-х основных частей:

  1. контейнеры - структуры данных для хранения однотипных объектов с базовыми функциями (вставка, удаление, поиск).
  2. алгоритмы - набор полезных и надежных алгоритмов.
  3. итераторы - объекты, которые в основном используются для того, чтобы заставить алгоритмы работать с контейнерами, а также для итерации и управления данными в контейнерах.
  4. функторы - объекты, которые ведут себя как функции и используются алгоритмами.

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

Как уже упоминалось, контейнеры - это классы, объекты которых используются для хранения других объектов того же типа. В STL не так много контейнеров, так что давайте познакомимся с ними поскорее.

Самые известные из них - vector, list, set, map, unordered_set и unordered_map. Все они являются контейнерами, поэтому обычно они делают одно и то же. Они предоставляют интерфейсы для вставки, удаления и поиска элементов в них, но они делают это совершенно по-другому, с разной сложностью и с использованием разного объема памяти.

Выбранный

Итак, вы пишете код, и вдруг вам нужен контейнер. Какой выбрать? Их так много (мастер Скайуокер), что мы будем делать?

Нетрудно понять, что каждый из этих контейнеров действительно хорош в чем-то (так что он является гордым членом контейнеров STL), но также имеет некоторые недостатки (иначе это был бы один-единственный). Давайте посмотрим, каковы сильные и слабые стороны каждого из них. Мы рассмотрим следующие факторы:

  • вставка
  • удаление
  • найти
  • получить n-й элемент
  • использование памяти
  • категория итератора

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

Если последовательность элементов в контейнере имеет значение, мы можем использовать только контейнеры последовательности, которыми являются vector и list. Чтобы понять, почему конкретному контейнеру что-то легко или сложно сделать, нам нужно понять, какова основная структура данных (где и как хранятся элементы).

вектор

Базовая структура данных вектора - это массив. В большинстве случаев размер базового массива больше, чем размер элементов в нем, поэтому у вас есть больше места, чем вам нужно. Но это дает возможность быстро вставить элемент до конца или удалить последний, просто отслеживая количество элементов. Конечно, время от времени размер массива может быть недостаточным, поэтому будет выделен новый, более крупный, старые элементы будут скопированы в новый, а старый будет уничтожен. Имея это в виду, давайте посмотрим, насколько хорош вектор каждого фактора, упомянутого выше.

Для вставки он предоставляет два интерфейса. Во-первых, это функция push_back, которая добавляет элемент в конец контейнера. vector может сделать это либо очень быстро, что почти всегда, либо очень сильно, когда пришло время выделить новый массив. Профессиональный термин для обозначения сложности - «амортизированное постоянное время (O (1))». Стоит отметить, что все не так уж и плохо, как звучит. Фактически, если мы вставим 1 млн элементов и если коэффициент роста равен 2 (каждый раз, когда новый массив будет вдвое больше старого), это произойдет только для 19 вставок. Кроме того, vector предоставляет функциональные возможности для изменения размера базового массива в любой момент, так что, если у нас есть какая-либо подсказка о количестве элементов, мы можем значительно уменьшить возникновение этого процесса. Подводя итог, vector действительно хорош в добавлении элементов в конце.

Но он также предоставляет функциональные возможности для вставки элемента в любое место посередине с помощью insert функций. В этом случае все элементы, следующие за желаемой позицией, должны сместиться на одну позицию вправо, чтобы освободить место для новой. В худшем случае, когда новый элемент вставляется в начало, все элементы должны быть сдвинуты. Сложность линейна в зависимости от размера контейнера (O (N)).

Сложность и интерфейс удаления почти такие же, как и для вставки. Есть функция pop_back, которая работает в O (1), но на этот раз реальный O (1) (в случае удаления новых проблем с выделением памяти нет). Функция erase, с другой стороны, сдвигает все, что находится после удаленного элемента, обратно влево. Таким образом, его сложность снова равна O (N).

Очевидно, что сложность поиска элемента также линейна (O (N)). Нет другого способа сделать это, кроме простой проверки каждого элемента, пока мы не добьемся успеха (или нет).

Получив n-й элемент, vector выиграет. Это очень быстро и со сложностью O (1).

Использование памяти также является профи. Базовая структура данных представляет собой массив, поэтому он не может быть лучше (игнорируя неиспользуемую его часть, о которой можно легко позаботиться).

Итераторы для vector относятся к категории «произвольный доступ». Теперь это самое лучшее в нем, единственное, что хотели бы иметь другие контейнеры. Эта функция позволяет многим алгоритмам работать быстрее, чем с другими итераторами. Некоторые из них (std::sort) работают даже только для итераторов с произвольным доступом.

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

список

list, он же двусвязный список, также является последовательным контейнером. По сути, это набор узлов, связанных друг с другом. Каждый узел содержит один элемент и два указателя на предыдущий и следующий узлы. Сам объект list хранит два указателя на первый и последний узел (для некоторых реализаций размер тоже).

Для вставки и удаления он предоставляет те же функции, что и vector, плюс функции push_front и pop_front. В отличие от vector, вставка в список всегда требует очень низких затрат, на самом деле const time. И это легко понять: новый узел можно создать где угодно в памяти, ему просто нужно указать свои указатели на новые соседние узлы и «попросить» их сделать то же самое. Или, в случае удаления, ему просто нужно познакомить двух своих соседей, прежде чем он исчезнет.

Вы можете подумать, а почему у vector нет push/pop_front функций, если это где-то еще есть? Я имею в виду, что вы можете получить итератор для первого элемента с помощью begin(), а затем вставить / удалить первый элемент с помощью этого итератора, верно? Это правильно, но все это сделано намеренно. Просто имейте это в виду, мы обсудим это позже.

Поиск элемента в list имеет ту же сложность и по той же причине, что и в vector: O (N).

Получив n-й элемент, вот где выигрывает vector. В случае vector после простых вычислений вы точно знаете, по какому адресу находится n-й элемент, но для list вы понятия не имеете. Вам просто нужно идти по одному, от начала до конца или иначе. =

Будет ли list хорошим с точки зрения использования памяти, зависит от размера объекта элементов. Помните, что каждый элемент хранится в узле с двумя указателями. Итак, если размер объекта большой, наличие еще двух указателей не имеет большого значения, но если он маленький, например, если элементы являются указателями, вы используете в 3 раза больше памяти, чем с vector.

итераторы для list относятся к категории «двунаправленные». Это не хорошо. Это означает, что многие алгоритмы будут работать медленнее, а некоторые будут недоступны, например алгоритм sort. Однако list предоставляет свою собственную sort функцию, которая имеет такую ​​же сложность, как и другая.

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

набор / карта

Если вас не волнует порядок размещения, вы можете воспользоваться ассоциативными контейнерами. Базовая абстрактная структура данных set и map - это двоичное дерево поиска. Большинство компиляторов реализуют его как красно-черное дерево (дерево RB).

Прежде чем мы продолжим и рассмотрим все факторы для этих контейнеров, давайте посмотрим, для чего они могут быть использованы. set предназначен для хранения уникальных элементов в отсортированном порядке. Это (автоматическая сортировка), пожалуй, самая лучшая и самая полезная его функция. map в значительной степени то же самое, но вместо элементов он хранит пары ключ-значение (сортировка и все остальное основаны на ключе).

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

Бинарное дерево считается сбалансированным, если для любого узла разница между высотой левого и правого поддеревьев не превышает 1.

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

Вставка, удаление и поиск элемента имеют одинаковую логарифмическую стоимость (O (logN)). Это потому, что чтобы найти элемент, мы должны перейти к нижней части дерева (максимум). Начиная с корня, мы проводим сравнение на каждом уровне и спускаемся на один уровень, пока не найдем то, что ищем, или до конца (уходит), если его не существует. Но какой высоты это дерево? Поскольку у каждого узла есть два дочерних элемента, на каждом уровне может быть вдвое больше узлов, чем на последнем, то есть на первом уровне у нас есть 1 элемент, в следующем 2, затем 4, 8, 16 и так далее. Итак, если у нас есть дерево с L полностью загруженными уровнями, общее количество элементов будет:

1 + 2 + ... + 2^L = 2^(L + 1) — 1

Помните, вопрос в том, если мы знаем количество узлов, а также знаем, что оно сбалансировано, сколько в нем уровней? С математической точки зрения, для заданного количества узлов (N) мы должны найти количество слоев (L), так что:

2^(L+1)-1 >= N      and       2^L <= N
L >= log(N+1)-1     and       L <= log(N)

Вообще говоря, в сбалансированном двоичном дереве из N узлов есть log(N) уровней.

Как указано выше, для ассоциативных контейнеров невозможно получить n-й элемент.

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

итераторы этих контейнеров двунаправленные. Как обсуждалось для list, эти итераторы не самые лучшие в своем деле, но все же кое-что.

Существуют также контейнеры multiset и multimap, которые в основном одинаковы, с одним отличием: ключи не уникальны для последних.

unordered_set / unordered_map

Эти контейнеры присоединились к семейству контейнеров STL довольно поздно, начиная с C ++ 11. Абстрактной структурой данных для них является хорошо известная хеш-таблица. Самое лучшее в нем то, что все, что он делает, он делает почти мгновенно. Возможно, вы осознали, что до сих пор каждый контейнер хорош в чем-то, но также очень плох в другом. Это не относится к этим контейнерам. Вставка, поиск и удаление элементов занимает постоянное время (O (1)). Но ... но ... сэр ... если они такие хорошие, почему они не сделали других устаревшими? Потому что они не идеальны. Они ассоциативны, что означает, что, в отличие от vector и list, они не хранят данные в порядке размещения и не сортируют. Кроме того, если тип ключа не является стандартным, вы должны подумать о функции хеширования, от которой зависит общая производительность. Чтобы понять, что для них все O (1), давайте посмотрим, как реализована хеш-таблица.

Представьте, что вам нужно хранить пары ключ-значение, ключи которых являются целыми числами определенного диапазона. Вместо map вы можете просто использовать vector. Это даст преимущество мгновенного получения значения из ключа. Что, если бы я сказал вам, что есть трюк, чтобы смоделировать это? Итак, ваши ключи могут быть любого типа, но если у вас есть так называемая хеш-функция для генерации целого числа для ключа, вы можете сохранить элементы в векторе и мгновенно получить к ним доступ. Это примерно так:

uint32_t hash(const KeyT& key)
{
    // generate and return some value
}

Он принимает любое значение типа KeyT и возвращает 4-байтовое целое число без знака. В идеальном мире у нас могла бы быть идеальная хеш-функция, так что если бы у нас было, скажем, 100 значений KeyT, у нас мог бы быть массив размером 100, и по модулю 100 (mod 100) этих хеш-значений было бы разные, и мы могли хранить, удалять и находить мгновенно. Однако реальность немного далека от этого, поэтому есть некоторые обходные пути. Один из подходов (возможно, лучший) - иметь массив так называемых корзин, которые представляют собой не что иное, как список элементов. Итак, если вы хотите вставить, удалить или найти элемент, вы его хешируете, используйте это хеш-значение в качестве индекса для (мгновенного) поиска корзины, а затем добавляйте, удаляйте или находите в этом списке. Конечно, поиск в списке занимает линейное время, но не в том случае, если его размер всегда небольшой. Идея состоит в том, чтобы всегда отслеживать load_factor, который является средним размером ведра, то есть size / bucket_count, и когда это количество больше некоторой константы max_load_factor, происходит повторное хеширование. Это когда мы добавляем новую корзину. Звучит просто, просто добавьте новую корзину, но все существующие элементы придется перераспределить. Это потому, что, если раньше у нас было 10 сегментов, и нам нужно было вставить элемент, хеш-значение которого равно 149983, мы сохранили его в 3-м сегменте (149983 mod 10 = 3). А теперь, если мы просто добавим новую 11-ю группу и будем искать этот элемент, мы пойдем и будем искать в 9-й группе (149983 mod 11 = 9), где мы его не найдем. Этот сценарий очень похож на тот, где vector необходимо увеличить свою емкость. Конечно, как и std::vector, std::unordered_set и std::unordered_map предоставляют функции, позволяющие избежать этих тяжелых перефразировок, если вы приблизительно знаете, сколько элементов вы будете хранить.

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

Конфликт ключей - это когда два разных значения имеют одно и то же хеш-значение. Это означает, что они будут храниться в одном ведре. Поэтому, если у нас есть плохая хеш-функция, которая очень часто допускает конфликты ключей или, в худшем случае, возвращает одно и то же значение для каждого ввода, наша хеш-таблица превратится в список (все значения должны будут храниться в одном ведре) . Конечно, не всегда удается избежать столкновений клавиш. Во-первых, даже если хеш-значения различны, их «моды» могут быть одинаковыми. Кроме того, если ваш тип хеш-значения представляет собой 32-битное целое число без знака, что означает, что оно может иметь 2 ² различных значения, ваш ввод может быть такого типа, что существует гораздо больше возможных вводов. Например, если вход относится к типу string и его длина равна 10, может быть 2⁸⁰ различных входных данных, а это означает, что невозможно избежать конфликта ключей. Итак, наша задача - сделать столкновение ключей редким. Один из способов - сделать вывод равномерно распределенным в кодомене ([0, 2³²-1]). Другой способ - использовать все части ввода. Например, если ваши входные данные представляют собой строки длиной 10, и если вы используете только первые четыре символа, есть большая вероятность, что ваши ключи будут часто конфликтовать (например, входы - это пути к файлам с одинаковым началом). С другой стороны, это замедлит работу хеш-функции. В конце концов, выбор алгоритма хеширования во многом зависит от ситуации и входных данных.

STL предоставляет std::hash функцию для всех основных типов, которые очень хорошо спроектированы, поэтому в большинстве случаев вам даже не нужно беспокоиться об этом, или вы можете создать свою собственную хеш-функцию на их основе.

Итак, имея это в виду, давайте посмотрим, как ведут себя эти контейнеры.

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

Удаление - это в точности постоянное время: это то же самое, что и удаление из списка.

Найти сложность также константное время, но помните, что константное время не означает быстро. Насколько быстро это зависит от max_load_factor. Все известные компиляторы позаботились о хорошем max_load_factor, так что поиск действительно быстр.

Конечно, это ассоциативные контейнеры, поэтому нет смысла говорить о n-м элементе.

Использование памяти этих контейнеров слишком велико. Он хранит vector из lists. Думаю, остальное очевидно.

итераторы у него двунаправленные, та же история, что и с map и set.

Этого мало?

Итак, мы рассмотрели все контейнеры, которые предоставляет STL, их плюсы и минусы, и в итоге мы пришли к выводу, что не существует единственного лучшего контейнера, каждый подходит для определенного сценария, а их так много, что в большинстве случаев вы можете просто использовать один из них, а не создавать свои собственные. Но, конечно, люди, которые придумали эти контейнеры, или те, кто их реализовал, не знают, для чего они вам понадобятся, насколько необычным и необычным может быть ваш сценарий. Давайте рассмотрим реализованный мной контейнер: prefix_tree. Это замена std::map<std::string, T> для любого типа T. Конечно, не мне пришла в голову эта замечательная идея, я просто реализовал ее. Итак, в каком сценарии prefix_tree лучше существующих контейнеров?

Не углубляясь слишком глубоко в структуру данных под капотом, скажем так, что сложность find, поскольку она зависит от длины string, которую мы ищем, тогда как, помните, для map (двоичного дерева поиска) она зависит от числа элементов в нем. Это означает, что асимптотически (после некоторого числа N элементов) find будет быстрее на prefix_tree.

В зависимости от реализации он также может быть победителем с точки зрения использования памяти. Моя первая версия реализации делала это, поэтому, если бы у вас было много элементов с одинаковым началом, для этого потребовалось бы значительно меньше памяти. Но когда я решил сделать его совместимым с STL, особенно когда я попытался реализовать reverse_iterator на основе уже реализованного iterator, оказалось, что мой итератор не соответствует требованиям стандарта, и мне пришлось изменить всю структуру данных для контейнера, чтобы они соответствовали. , и теряют это преимущество. Итак, прежде чем приступить к написанию собственного контейнера, совместимого с STL, вы должны спросить себя, стоит ли делать этот контейнер совместимым с STL?

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

Итак, проблема в том, что в моей первоначальной реализации каждый узел имеет символ и указатель на сопоставленный тип. Если этот указатель не равен нулю, мы можем подняться по дереву и собрать все символы, в результате чего получится строка, которая сопоставляется со значением, на которое указывает наш указатель. Но value_type моего контейнера определен как std::pair<const key_type, mapped_type>, и функции доступа iterator должны были возвращать указатель или ссылку на объект этого типа. Сначала я решил проблему, сделав прокси-объект этого типа членом итератора. У него должно быть время жизни итератора, у итератора был указатель на узел, и когда он изменился, чтобы указать на другой узел, он снова вычислил ключ и обновил член прокси. Все было хорошо, пока я не добавил reverse_iterator. STL предоставляет класс адаптера std::reverse_iterator, который можно использовать для создания reverse_iterator на основе вашего правильно определенного iterator. Я думал, что мой правильно определен, но это не так. Я узнал об этом благодаря модульным тестам, которые не дали результата при разыменовании reverse_iterator. В реализации GCC std::reverse_iterator в operator* он создает временный iterator, уменьшает его и разыменовывает, возвращая результат. В этом случае этот указатель указывал на прокси-объект внутри временно созданного iterator, который уже вышел из области видимости и был уничтожен. Покопавшись в источниках GCC, я обнаружил, что когда-то это считалось ошибкой в реализации. Эта ошибка еще не исправлена, она считается недействительной и реализация действительна, поскольку в стандарте (24.2.5 [forward.iterators] / 6) четко указано, что:

If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object.

Это была проблема с моими итераторами. Каждый итератор имел свой собственный объект для привязки, даже если он указывал на один и тот же узел. Чтобы решить эту проблему, я просто изменил структуру узла, так что теперь он хранит правильный value_type, то есть std::pair<const key_type, mapped_type>.

Пусть начнется взлом

Мы собираемся реализовать ассоциативный контейнер, совместимый с STL, который должен быть заменой существующего контейнера map. Собственно, это хорошая новость, потому что мы можем просто взглянуть на его интерфейс и все повторить. Не только можем, но и должны. Если наш контейнер претендует на замену, ожидается, что у него будет такой же интерфейс.

Когда дело доходит до написания кода, мне проще подход «снизу вверх». То есть я начинаю с интерфейса, определяю все функции и реализую их на другом уровне реализации. В этом случае я как бы использовал технику «pimpl», за исключением того, что моей целью было не скрыть реализацию, так что это не указатель на реализацию, а просто реализация. Итак, я полагаю, что у меня есть основная реализация этого контейнера, которая не знает о внешних абстракциях и имеет самый простой интерфейс (вставить, найти, удалить). Основной класс имеет члена и ссылается на него.

Теперь давайте взглянем на map интерфейс и сделаем наш как можно ближе к нему. Вот его определение:

template<
     class Key,
     class T,
     class Compare = std::less<Key>,
     class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

Конечно, это шаблонный класс с четырьмя аргументами. У нашего контейнера будут почти такие же параметры.

Я внес некоторые изменения. Во-первых, Key переименовывается в StringT, чтобы содержать дополнительную подсказку о том, что тип ключа этого контейнера должен быть строковым. Сложно сказать, но сложно понять, что такое строковый тип. По сути, это должен быть контейнер последовательностей, совместимый с STL. Параметр Compare также пропал, потому что он нам сейчас не нужен. На данный момент достаточно, чтобы для символов StringT было определено std::hash (что в большинстве случаев так и есть). Имейте в виду, что в основном std::map используется с двумя параметрами шаблона, типами ключа и значения. Теперь мы поддерживаем тот же интерфейс. Двигаемся дальше.

Еще одна важная часть контейнеров STL - это общедоступные определения. А вот модели std::map можно найти здесь. В нашем случае это:

Эти определения не только полезны, так как сделают кодирование простым и читаемым, но и важны. Они могут и будут использоваться не только STL, но и другими пользователями. Фактически, мы уже использовали эти определения других классов в этом коде. См. Строки 5, 10, 11. Мы ожидаем, что key_type, который является параметром шаблона StringT, будет иметь определение открытого типа с именем value_type, а в самой известной строке std::basic_string оно есть.

Определения почти такие же, как в map, с одним дополнением char_type. Вообще-то он там на всякий случай, даже реального применения не имеет. Это скорее философский вопрос, должен ли контейнер иметь ту или иную функциональность или определение. Мы вернемся к этому позже. Я добавил char_type, потому что думал, что этот тип является важной частью этого контейнера, и было бы хорошо иметь отдельное определение для него, чтобы подчеркнуть его важность.

Затем конструкторы, операторы присваивания и деструктор. Те из std ::map находятся здесь. В нашем случае это будет:

Важно помнить, что каждый контейнер STL имеет конструктор по умолчанию (в основном с необязательным параметром распределителя), конструктор из std::initializer_list (для более новых стандартов) и конструктор с двумя итераторами. Он также должен иметь правильный конструктор копирования (и перемещения), оператор присваивания и, конечно же, деструктор. Конечно, могут быть и другие конструкторы, например vector и list, которые имеют конструкторы заливки, но это основные.

Затем у нас есть селекторы и мутаторы.

Вы можете увидеть здесь, что std::map имеет больше функций, особенно тех, которые доступны с C++17. Возможно, позже я добавлю их для идеального соответствия, но сейчас самые важные из них здесь. Это та часть, когда вы даете волю своему воображению и творчеству. Вы должны предоставить некоторый базовый интерфейс, но вы также можете добавить что угодно. Очевидно, что под базовой функциональностью мы подразумеваем функции для добавления, удаления и поиска элемента (в конце концов, это контейнер). Будьте осторожны с именами и подписями.

Что касается вставки, это зависит от типа контейнера (будь то последовательность или нет). Если это контейнер последовательности, вы должны рассмотреть следующие функции:

  • push_back
  • push_front
  • pop_back
  • pop_front

Это важно, потому что адаптеры STL, такие как std::stack и std::queue, опираются на эти функции. Имейте в виду, что необязательно иметь их все. vector, например, их всего два («задние»).

Время философии. Если у вас есть достаточный опыт работы с STL, вы уже знаете, что контейнеры STL не предоставляют все функции в мире, поэтому вы можете просто вызвать их. Они предоставляют только функции, которые будут работать относительно быстро. Это немного сложно, но важно понять. Возьмем QVector контейнер из библиотеки Qt. Он заменяет std::vector и предоставляет функцию push_front, и в официальной документации утверждается, что это займет линейное время. Тот факт, что std::vector не предоставляет для этого отдельную функцию, не означает, что вы не можете сделать то же самое для этого. Вы можете использовать функцию insert с итератором, возвращаемым из begin(). Другими словами:

std::vector<int> sv;
QVector<int>     qv;
//...
sv.insert(sv.begin(), 42);
qv.push_front(42);

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

Но это не наш случай, наш контейнер не является последовательным. У нас должно быть insert функций. У меня их 3 штуки. Давайте обсудим их по очереди.

Первый находится на 11-й строке, он не имеет ничего общего с совместимостью с STL, std::map не имеет подписи с этой подписью, только что добавленной мной. Второй, в строке 12, представляет собой сигнатуру функции вставки для ассоциативных контейнеров, она берет элемент value_type и вставляет его в нужное место. Возвращаемое значение (пара итератора и логического значения) также такое же, как для std::map и std::unordered_map. Самый интересный - третий. Как видите, он принимает итератор и значение в качестве входных данных и возвращает итератор. Все контейнеры STL имеют insert функцию с этой сигнатурой. Это сделано для поддержки идеи контейнерно-независимого кода. В своей легендарной книге Эффективный STL у Скотта Мейерса есть замечательная статья об этой идее, которую определенно стоит проверить. Идея состоит в том, чтобы написать такой код, который мог бы работать для любого контейнера, чтобы, если вы измените определение одного типа, все остальное по-прежнему будет работать. Как утверждает Мейерс, это хорошая, но опасная идея. Не следует всегда пытаться сделать контейнер кода независимым, особенно когда шансы на его полезность практически равны нулю. Однако однажды мне понадобилась эта функция контейнеров STL, и было действительно приятно, что они позаботились об этом. Взгляните на этот мой код.

Дело в том, что я написал две шаблонные функции и хочу, чтобы они работали для любого контейнера. Взгляните на строки 4, 6, 19 и (особенно) 21. Итак, благодаря тому факту, что все контейнеры STL предоставляют один и тот же базовый интерфейс, этот код работает для меня. Все они имеют size функцию-член, begin и end функции и правильные итераторы, value_type определение открытого типа и, конечно же, insert функции, которые принимают итератор и значение, возвращают итератор. Стоит отметить, что для контейнеров последовательности итератор, который является входом этой insert функции, влияет на то, куда вставляется новый элемент, но это не относится к ассоциативным контейнерам. Вот почему имя этого параметра hint для map, и большинство реализаций даже не используют этот параметр, как и мой prefix_tree. Он нужен только для того, чтобы соответствовать общему интерфейсу.

То же самое и с удалением. Здесь у нас есть две erase функции, вторая из которых (строка 16) принимает итератор в качестве входных данных и возвращает итератор. Эта версия является универсальной функцией удаления.

Что касается других функций, важны size, max_size, empty и clear. Эти функции есть у всех контейнеров. Ожидается, что первые три из них будут иметь постоянную временную сложность, а последний - линейный.

Возвращаясь к философии STL, были интересные дебаты и дискуссии о size функции-члене для std::list. Как обсуждалось выше, контейнеры STL строго придерживались идеи предоставления простых функций только тогда, когда они работают быстро. Если мы говорим о функции size, под быстрой мы подразумеваем за константное время. Интуитивно кажется, что для контейнера не проблема каким-то образом определить его размер или отслеживать его. Очевидно, что в случае списка решение состоит в том, чтобы отслеживать размер, приращение и уменьшение в случае вставки и удаления соответственно. Оказывается, это проблема для списка, и проблема возникает с другой (не менее важной) функцией-членом: splice. Эта функция передает элементы из одного списка в другой. Только список имеет эту функцию, потому что его структура данных дает возможность делать это очень быстро, за постоянное время. Есть несколько перегрузок этой функции, но одна из них разрушает все, та, которая принимает два итератора другого списка, определяя диапазон элементов, которые нужно переместить из него. Это можно было бы сделать за константное время, и это должно быть сделано за константное время, но тогда мы потеряем счет размера. Мы не можем знать, сколько элементов находится в этом диапазоне. Итак, мы на заборе. Либо мы отслеживаем размер, так что size будет иметь постоянную временную сложность, но делаем splice линейной сложностью, чтобы мы могли отслеживать размер, или мы оставляем splice эффективно работать в const время и не отслеживать размер, просто считайте его каждый раз, делая size линейной сложностью. Были и другие варианты, чтобы отпустить одну из этих функций, но обе они были слишком важны, чтобы их не учитывать. Я не знаю, как старейшины C ++ обсуждали это (хотелось бы, чтобы я был там, чтобы знать), но я знаю, что они придумали. До C ++ 11 в стандарте говорилось, что size должно быть постоянным временем (поэтому это не обязательно), а splice должно быть постоянным временем. Начиная с C ++ 11, стандарт требовал size иметь постоянную временную сложность, а splice разрешалось работать в линейном времени для этой конкретной перегрузки. Это хороший пример того, насколько люди заботятся о правильном интерфейсе, и вы тоже должны это делать.

Далее у нас есть раздел «итераторы».

Остальные общедоступные функции просты и утомительны, get_allocator и несколько операторов сравнения.

После определения интерфейса пора реализовать эти функции. Будьте осторожны, не бойтесь писать надлежащие модульные тесты и тесты покрытия.

Мы почти там. Прежде чем перейти к последней серьезной части, реализации правильных итераторов, небольшой совет: заимствуйте реализацию контейнера из вашего типа распределителя, как это делают STL. Это нормально, потому что должен быть один экземпляр распределителя для каждого контейнера, а также, производя от него, мы можем извлечь выгоду из EBO (пустой базовой оптимизации), так что если распределитель является классом без членов (как в большинстве случаев ), это не увеличит размер объекта-контейнера.

Вернемся к итераторам. Попробуйте ответить на знаменитый вопрос интервью: в чем разница между типами std::vector<int>::const_iterator и const std::vector<int>::iterator? Это важно для нас, потому что, если они одинаковы, мы можем реализовать только iterator и просто "typedef" const_iterator. Но если они разных типов, нам нужно будет написать два отдельных класса. Правильный ответ: это разные типы. Первый - const_iterator, что означает, что его экземпляр нельзя использовать для изменения элемента, к которому он относится. Второй - const iterator, что означает, что он может изменить элемент, на который он ссылается, но не может ссылаться на другой элемент. И, конечно же, reverse_iterator -ы тоже разных типов. Об этих итераторах следует помнить следующее:

  • const_iterator должен иметь конструктор из iterator
  • reverse_iterator-s должен иметь base функции-члены

Будем надеяться, что в STL есть класс адаптера std::reverse_iterator, который обертывает iterator, чтобы стать reverse_iteartor. Так что не нужно писать совершенно новый класс, просто убедитесь, что ваш iterator относится как минимум к двунаправленной категории и определите его тип, как в строках 14 и 15 в определениях общедоступных типов.

В остальном почти то же самое. Тогда давай писать. Вместо того, чтобы писать итератор внутри контейнера, я написал его где-то снаружи и просто «typedef» ввел в контейнер.

Только пять из этих определений важны, публичные. Очень важно правильно определить эти типы, особенно iterator_category. Его следует определить как один из этих 5 типов:

  • input_iterator_tag
  • output_iterator_tag
  • forward_iterator_tag
  • bidirectional_iterator_tag
  • random_access_iterator_tag

Эти типы определены в пространстве имен std в заголовке <iterator>. Это определение типа помогает алгоритмам STL решить, какую реализацию использовать. Это то, что заставляет std::distance и std::advance работать быстрее для итераторов std::vector, чем для итераторов std::list. Но как узнать, к какой категории относится ваш итератор?

Это зависит от того, какой интерфейс предоставляет ваш итератор. По сути, итератор должен иметь определенные операторы operator*() и operator->(). Если он также может иметь operator++, он относится к категории вперед. Если он также имеет operator--, он относится к категории двунаправленный. Если он также имеет operator+, operator-, operator+=, operator-=, operator[], operator< и другие операторы сравнения (›, ≤, ≥), он относится к категории random_access. На самом деле правила немного строже.

Вот и все. Не забудьте в конце правильно провести модульное тестирование.