Введение

Всем привет!! В статье на этой неделе мы продолжим изучение еще нескольких контейнеров C++ STL, а именно:

  • Приоритетная очередь
  • карта
  • Набор
  • Неупорядоченная карта
  • Неупорядоченный набор

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

std::priority_queue

Сразу оговоримся сразу: очереди с приоритетом сильно отличаются от обычных очередей. Да, вы можете получать только один элемент за раз, как в обычных очередях, но приоритетные очереди хранят данные в определенном порядке и не следуют правилу FIFO, как это делают обычные очереди. По умолчанию они хранят числа в порядке убывания, а строки хранятся в порядке убывания их соответствующего значения ASCII (побуквенное сравнение). Тем не менее, мы также можем хранить числа в порядке возрастания и строки в лексикографическом порядке, если мы используем priority_queue<int, vector<int>, greater<int>> и priority _queue<string, vector<string>, greater<string>> при объявлении очередей с приоритетом соответственно. Все эти функции делают очередь с приоритетом идеальным кандидатом для задач, требующих повторной оптимизации, как в алгоритме Дейкстры и т. д.

Часто используемые методы

Методы доступа

top() — используется для получения самого предыдущего элемента из приоритетной очереди. Если вы создали очередь с приоритетом по умолчанию, она вернет элемент с наибольшим значением, а если она была изменена на восходящий/лексикографический порядок при объявлении, она вернет элемент с наименьшим значением. Если приоритетная очередь пуста, этот метод демонстрирует неопределенное поведение. Временная сложность этого метода составляет O (1).

Методы, связанные с емкостью

empty() — используется для проверки наличия элементов в приоритетной очереди. Он возвращает 1 (истинное значение), если приоритетная очередь пуста, иначе возвращает 0 (ложное значение). Временная сложность этого метода составляет O (1).

size() — используется для определения количества элементов в приоритетной очереди. Он возвращает X, если есть X элементов с приоритетом, где X — целое число. Временная сложность этого метода составляет O (1).

Изменить методы

push(input) — используется для добавления элементов в приоритетную очередь. Он принимает 1 аргумент — добавляемый элемент, и этот указанный элемент будет добавлен в приоритетную очередь на основе приоритета. Временная сложность этого метода составляет O(logn).

pop() — используется для удаления самого предыдущего элемента из приоритетной очереди, но ничего не возвращает. Если приоритетная очередь была пустой, этот метод приводит к неопределенному поведению. Временная сложность этого метода составляет O(logn).

станд::карта

Если вы хотите хранить данные в виде пар, которые связаны друг с другом, карты — идеальный выбор. Карты хранят данные в виде пар ключ-значение. Учитывая «ключ», вы сможете найти его «значение», потому что «ключ» и «значение» связаны друг с другом. Очень важно отметить, что ключи должны быть уникальными и должны быть связаны с одним и только одним значением. Однако два разных ключа могут сопоставляться одному и тому же значению. Они очень похожи на функции, которые мы изучали на уроках математики. Еще один момент, касающийся карт нормалей, заключается в том, что их ключи отсортированы (по возрастанию/лексикографически по умолчанию, что может быть изменено так же, как мы обсуждали в очередях с приоритетом).

Часто используемые методы

Методы доступа

at(key) — дает значение, связанное с данным вводом «key». Однако, если данный входной «ключ» не существует, он выдает «ошибку вне диапазона». Временная сложность этого метода составляет O(logn).

name_of_map[key] — оператор квадратных скобок можно использовать так же, как и в случае с массивами. Будет указано «значение» «ключа», заключенного в квадратные скобки. Этот оператор также можно использовать для вставки элементов, присваивая новому ключу его значение, подобное этому name_of_map[new_key] = value Временная сложность этой операции — O(logn).

Методы, связанные с емкостью

empty() — возвращает 1, если карта пуста (не содержит элементов), или возвращает 0, если карта не пуста. Временная сложность этого метода составляет O (1).

size() — возвращает количество пар ключ-значение на карте. Временная сложность этого метода составляет O (1).

Изменить методы

insert() — используется для добавления пар ключ-значение на карту. Есть два способа его использования:

  • name_of_map.insert({key, value})
  • name_of_map.insert(std::make_pair(key, value))

В худшем случае временная сложность этого метода составляет O (logn).

стереть(клавиша) / стереть(итератор) / стереть(итератор1, итератор2) — Как вы могли заметить, существует 3 способа использования метода стирания. Erase(key) удаляет пару ключ-значение входного ключа. Erase(iterator) удаляет пару ключ-значение, на которую указывает итератор, переданный в качестве входных данных. Erase(iterator1, iterator2) используется для удаления диапазона пар ключ-значение, предоставляя в качестве входных данных два итератора — начальный итератор (включенный) и конечный итератор (исключенный). В худшем случае временная сложность этого метода составляет O (logn).

clear() — используется для удаления всех пар ключ-значение с карты. Временная сложность этого метода составляет O(n).

Методы поиска

find(key) — принимает «ключ» в качестве входных данных. Если «ключ» существует, он возвращает итератор для этого «ключа» на карте. Если «ключ» не существует, он возвращает константный итератор, который ссылается на итератор end(). Временная сложность этого метода составляет O(logn).

count(key) — принимает в качестве входных данных «ключ» и возвращает 1, если «ключ» существует на карте, иначе возвращает 0. Временная сложность этого метода — O(logn).

lower_bound(key) — этот метод возвращает итератор, указывающий на ключ (ввод) в контейнере карты. Если ключ отсутствует на карте, функция возвращает итератор, указывающий на ближайший следующий элемент, который чуть больше ключа. Если ключ, переданный в параметре, превышает максимальный ключ в контейнере, то возвращаемый итератор указывает на количество элементов в карте, поскольку ключ и элемент могут быть любыми элементами. Временная сложность этого метода составляет O(logn).

upper_bound(key) — функция возвращает итератор, указывающий на ближайший следующий элемент, который чуть больше ключа (входной). Если ключ, переданный в параметре, превышает максимальный ключ в контейнере, возвращаемый итератор ссылается на name_of_map.end(). Временная сложность этого метода составляет O(logn).

Самый большой и самый маленький ключ

Если вы хотите найти самый маленький ключ на карте, есть остроумный способ сделать это. Вы можете использовать name_of_map.begin(), который вернет итератор к первому ключу карты, но по умолчанию элементы расположены в порядке возрастания в картах, поэтому первый ключ также является самым маленьким ключом. Точно так же, если вы хотите найти самый большой ключ, вы можете использовать name_of_map.rbegin(), который вернет итератор, ссылающийся на последний ключ карты. Вы можете увеличить эти итераторы, чтобы получить последующие меньшие/большие ключи. Временная сложность увеличения этих итераторов составляет O (logn).

Ключ и значение от итератора

Предположим, у вас есть итератор, указывающий на ключ на вашей карте, и вы хотите узнать ключ и связанное с ним значение. Вы можете использовать name_of_iterator->first для получения ключа и name_of_iterator->second для получения значения. Вы также можете использовать *(name_of_iterator).first и *(name_of_iterator).second для получения ключа и значения соответственно.

станд:: набор

Вы можете думать о наборах просто как о наборе данных, которые должны быть уникальными (не повторяться). Следовательно, вы можете думать о множествах как о картах только с «ключевой» частью. Как и в случае с картами, числа, хранящиеся в наборах, автоматически располагаются в порядке возрастания, а строки — в лексикографическом порядке.

Общие методы

Методы доступа

Для наборов нет явных методов доступа. Однако вы можете использовать метод find(), чтобы заставить итератор ссылаться на элемент (если он существует).

find(parameter) — если вы хотите получить доступ к элементу, вы можете использовать этот метод, который возвращает итератор для элемента, переданного в качестве параметра. Если элемент не существует, он возвращает итератор end(). Временная сложность этого метода составляет O(logn).

Методы, связанные с емкостью

size() — используется для получения количества элементов в наборе. Временная сложность этого метода составляет O (1).

empty() — этот метод возвращает 1, если в наборе нет элементов, иначе он возвращает 0. Временная сложность этого метода — O(1).

Изменить методы

insert(parameter) — этот метод используется для добавления элементов в наборы. Добавляемый элемент необходимо передать в качестве параметра. В худшем случае временная сложность этого метода составляет O (logn).

erase(parameter) — используется для удаления элемента из набора. Удаляемый элемент необходимо передать в качестве параметра. Если элемент, который вы передали, не присутствовал в наборе, он не выдает никакой ошибки. В худшем случае временная сложность этого метода составляет O (logn).

clear() — удаляет все элементы, хранящиеся в наборе. Временная сложность этого метода составляет O(n).

Методы поиска

count(parameter) — помогает вам получить количество элементов в наборе. Поскольку элементы в наборах уникальны, его можно использовать для проверки существования элемента в наборе. Временная сложность этого метода составляет O(logn).

find(parameter) — если вы хотите получить доступ к элементу, вы можете использовать этот метод, который возвращает итератор для элемента, переданного в качестве параметра. Если элемент не существует, он возвращает итератор end(). Временная сложность этого метода составляет O(logn).

lower_bound(entry) — этот метод возвращает итератор, указывающий на запись (ввод) в контейнере карты. Если запись отсутствует на карте, функция возвращает итератор, указывающий на ближайший следующий элемент, который чуть больше записи. Если запись, переданная в параметре, превышает максимальное значение в контейнере, то возвращаемый итератор ссылается на name_of_set.end(). Временная сложность этого метода составляет O(logn).

upper_bound(entry) — функция возвращает итератор, указывающий на ближайший следующий элемент, который чуть больше входа (входа). Если запись, переданная в параметре, превышает максимальную запись в контейнере, то возвращаемый итератор ссылается на name_of_set.end(). Временная сложность этого метода составляет O(logn).

Самая большая и самая маленькая запись

Как и в картах, в наборах вы можете найти самую маленькую и самую большую запись, используя name_of_set.begin() и name_of_set.rbegin() соответственно. Вы можете увеличить эти итераторы, чтобы получить последующие меньшие/большие записи. Временная сложность приращения остается O(logn) и для наборов.

std:: unordered_map

Неупорядоченная карта отличается от упорядоченной по 4 основным параметрам:

  1. Встроенная реализация: неупорядоченная карта внутри строится на основе хеш-карт, тогда как упорядоченные карты строятся на основе красно-черных деревьев (самобалансирующиеся бинарные деревья). Это фундаментальное различие порождает все различия, существующие между неупорядоченным и упорядоченным отображением. Пока нет необходимости углубляться в то, что такое хеш-карты или красно-черные деревья. Просто сосредоточьтесь на различиях и на том, как вы можете извлечь из этого пользу.
  2. Порядок, в котором хранятся данные: это различие зависит от имени. Неупорядоченные карты не имеют порядка, когда речь идет о хранении данных, в то время как упорядоченные карты имеют отсортированный порядок.
  3. Временная сложность некоторых операций. Как вы скоро увидите в методах, неупорядоченные карты быстрее по сравнению с упорядоченными картами. Временная сложность некоторых операций упорядоченных карт улучшена по сравнению с неупорядоченными картами.
  4. Ограничение на типы данных ключа: любая структура данных, хэш-значение которой не может быть найдено, не может использоваться в качестве ключей в неупорядоченных картах. Проще говоря, примитивные типы данных, такие как int, char, strings, хороши, но сложные, такие как векторы, пары, — нет, нет. Однако с упорядоченными картами такой проблемы не возникает, поскольку они основаны на деревьях (где достаточно сравнения данных). Это ограничение можно устранить, если мы сделаем тип данных хэшируемым, написав собственный std::hash‹› для класса. Подробнее здесь

Часто используемые методы

Методы неупорядоченных карт такие же, как и для упорядоченных карт, но их временная сложность различается.

Методы доступа

at(key) — дает значение, связанное с данным вводом клавиши. Однако, если данный входной ключ не существует, он выдает «ошибку вне диапазона». Средняя временная сложность составляет O (1), а наихудшая временная сложность - O (n).

Теперь вы можете спросить: «Почему наихудшая сложность O(n) лучше постоянной временной сложности O(logn), как в упорядоченных картах?». Ответ основан на хешировании, потому что наихудший сценарий возникает, когда хеширование приводит к коллизиям, то есть более чем один «ключ» начинает давать одно и то же «значение» после хеширования. Но это редкий случай, и, следовательно, большую часть времени этот метод работает при O (1). Вам нужно будет запомнить это, потому что все методы доступа, вставки, удаления и поиска здесь и в неупорядоченных наборах имеют одинаковое обоснование своей временной сложности.

name_of_map[key] — этот оператор квадратных скобок можно использовать так же, как и в случае с массивами. Будет указано значение ключа, заключенного в квадратные скобки. Этот оператор также можно использовать для вставки элементов, назначив новому ключу его значение, подобное этому name_of_map[new_key] = value Средняя временная сложность равна O(1), а временная сложность в наихудшем случае равна O(n).

Методы, связанные с емкостью

empty() — возвращает 1, если карта пуста (не содержит элементов), или возвращает 0, если карта не пуста. Временная сложность этого метода составляет O (1).

size() — возвращает количество пар ключ-значение на карте. Временная сложность этого метода составляет O (1).

Изменить методы

insert() — используется для добавления пар ключ-значение на карту. Есть два способа его использования:

  • name_of_map.insert({key, value})
  • name_of_map.insert(std::make_pair(key, value))

Средняя временная сложность составляет O (1), а наихудшая временная сложность - O (n).

стереть(клавиша) / стереть(итератор) / стереть(итератор1, итератор2) — Как вы могли заметить, существует 3 способа использования метода стирания. Erase(key) удаляет пару ключ-значение входного ключа. Erase(iterator) удаляет пару ключ-значение, на которую указывает итератор, переданный в качестве входных данных. Erase(iterator1, iterator2) используется для удаления диапазона пар ключ-значение, предоставляя в качестве входных данных два итератора — начальный итератор (включенный) и конечный итератор (исключенный). Средняя временная сложность составляет O (1), а наихудшая временная сложность - O (n).

clear() — используется для удаления всех пар ключ-значение с карты. Временная сложность этого метода составляет O(n).

Методы поиска

find(key) — принимает «ключ» в качестве входных данных. Если «ключ» существует, он возвращает итератор для этого «ключа» на карте. Если «ключ» не существует, он возвращает постоянный итератор, который ссылается на итератор end(). Средняя временная сложность составляет O (1), а наихудшая временная сложность - O (n).

count(key) — принимает «ключ» в качестве входных данных и возвращает 1, если «ключ» существует на карте, иначе возвращает 0. Средняя временная сложность — O(1), в худшем случае временная сложность O (n).

Ключ и значение от итератора

Предположим, у вас есть итератор, указывающий на ключ в вашей неупорядоченной карте, и вы хотите узнать ключ и связанное с ним значение, вы можете использовать name_of_iterator->first для получения ключа и name_of_iterator->second для получения значения. Вы также можете использовать *(name_of_iterator).first и *(name_of_iterator).second для получения ключа и значения соответственно.

std:: unordered_set

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

Общие методы

Методы доступа

Явных методов доступа нет. Однако вы можете использовать метод find(), чтобы заставить итератор ссылаться на элемент (если он существует).

find(parameter) — если вы хотите получить доступ к элементу, вы можете использовать этот метод, который возвращает итератор для элемента, переданного в качестве параметра. Если элемент не существует, он возвращает итератор end(). Средняя временная сложность составляет O (1), а наихудшая временная сложность - O (n).

Методы, связанные с емкостью

size() — используется для получения количества элементов в наборе. Временная сложность этого метода составляет O (1).

empty() — возвращает 1, если в наборе нет элементов, иначе возвращает 0. Временная сложность этого метода — O(1).

Изменить методы

insert(parameter) — этот метод используется для добавления элементов в наборы. Добавляемый элемент необходимо передать в качестве параметра. Средняя временная сложность составляет O (1), а наихудшая временная сложность - O (n).

erase(parameter) — используется для удаления элемента из набора. Удаляемый элемент необходимо передать в качестве параметра. Если элемент, который вы передали, не присутствовал в наборе, он не выдает никакой ошибки. Средняя временная сложность составляет O (1), а наихудшая временная сложность - O (n).

clear() — удаляет все элементы, хранящиеся в наборе. Временная сложность метода составляет O(n).

Методы поиска

count(parameter) — помогает вам получить количество элементов в наборе. Поскольку элементы в наборах уникальны, его можно использовать для проверки существования элемента в наборе. Средняя временная сложность составляет O (1), а наихудшая временная сложность - O (n).

find(parameter) — если вы хотите получить доступ к элементу, вы можете использовать этот метод, который возвращает итератор для элемента, переданного в качестве параметра. Если элемент не существует, он возвращает итератор end(). Средняя временная сложность составляет O (1), а наихудшая временная сложность - O (n).

Заключение

Я изо всех сил старался охватить все основы контейнеров C++ STL на этой неделе. Надеюсь, вы извлекли что-то полезное из этой статьи и получили от нее столько же удовольствия. Я еще раз подчеркиваю, что это только основы, и вы узнаете больше, когда будете писать код и столкнетесь с проблемами при использовании этих контейнеров. Чтобы узнать больше об этих и других контейнерах в STL, посетите cppreference.com.