Многие языки программирования, используемые в олимпиадном программировании, содержат набор стандартных библиотек (модулей) для работы с различными структурами данных. В данном разделе будут рассмотрены основные структуры для языков C++ и Python, наиболее часто используемые при решении олимпиадных задач.
STL – стандартная библиотека шаблонов и объектов в C++, содержащая ряд функций для работы с данными без привязки к конкретным типам с использованием шаблонного подхода.
Шаблон – механизм описания классов и функций без указания конкретных типов, что позволяет избегать дублирования кода.
Использование STL упрощает кодирование олимпиадных задач в силу возможности использования готовых функций, наиболее часто используемых в реализации программ.
Пара (pair) – шаблонная структура, содержащая два значения, возможно разных типов с именами first и second, обращаться к которым следует как к полям записи. Требуется подключение библиотеки utility. Элементы пары сравнимы: сначала сравнение идет по полю first, в случае равенства сравниваются поля second.
Кортеж (tuple) – структура, содержащая упорядоченный набор данных фиксированной длины. Структура поддерживает лексикографическое сравнение элементов. Доступ к полям элементов осуществляется по номеру. Требует подключение библиотеки tuple.
Линейный массив (vector) – ведет себя как динамически расширяемый массив, с элементами которого можно работать как с элементами обычного одномерного массива. Требуется подключение библиотеки .
Методы класса vector:
vector < int > v
–
описание динамического массива
v.push_back(x)
–
добавление элемента в конец вектора
v.size()
–
возвращает количество элементов в векторе
v.empty()
–
возвращает логическое значение: пуст ли вектор?
v.capacity()
–
возвращает число элементов, которые могут поместиться в векторе без расширения
Стек (stack) - динамическая структура, работающая по принципу LIFO (Last In First Out). Позволяет добавлять элементы в конец и извлекать их с конца. Требуется подключение библиотеки stack.
Дек (deque) – динамическая структура данных, позволяющая добавлять и извлекать элементы как в конец, так и в начало. Требуется подключение библиотеки deque.
Список (list) – динамическая структура данных, которая построена на двусвязных списках. Позволяет добавлять и извлекать элементы в любую позицию. Доступ к элементам происходит через итератор списка, который может перемещаться к смежным элементам. Не поддерживает обращение по номеру элемента. Требуется подключение библиотеки list.
Методы класса list:
list < int > a
–
описание списка
list < int >::iterator it
–
описание итератора (указателя) списка
a.begin()
–
итератор первого элемента
a.end()
–
итератор последнего элемента
a.push_front(x)
–
добавление элемента в начало списка
a.push_back(x)
–
добавление элемента в конец списка
a.pop_front()
–
удаляет элемент из начала списка
a.pop_back()
–
удаляет элемент из конца списка
a.front()
–
обращение к первому элементу
a.back()
–
обращение к последнему элементу
a.size()
–
возвращает количество элементов
a.empty()
–
возвращает истину, если список пуст
a.unique()
–
удаление всех повторяющихся элементов (дубликатов)
a.merge(b)
–
вставка элементов списка b в конец списка a
a.erase(it)
–
удаление элемента в позиции итератора it
a.erase(it_begin, it_end)
–
удаление элементов между итераторами it_begin и it_end
Очередь с приоритетом (priority_queue) – динамическая структура данных, именуемая «кучей». Позволяет добавлять и удалять элементы за O(log N), а так же находить максимальный элемент за O(1). Требуется подключение библиотеки queue.
Описание кучи:
priority_queue < int > h – куча максимумов (по умолчанию)
priority_queue < int, vector < int >, greater< int > > h – куча минимумов (functional)
Методы класса priority_queue (для кучи максимумов):
Множество (set) – упорядоченный контейнер, позволяющий хранить множество элементов, в котором каждый элемент встречается не более одного раза. Требует подключения библиотеки set.
Методы класса set:
set < int > s
–
описание множества
s.insert(x)
–
добавление элемента x в множество s с исключением дублей
s.erase(x)
–
удаление элемента x из множества s
s.erase(it1, it2)
–
удаление отрезка элементов между итераторами it1 и it2
s.size()
–
количество различных элементов множества s
s.count(x)
–
возвращает 0, если x не в s и 1, если x в s
*s.begin()
–
минимальный элемент множества s
*s.rbegin()
–
максимальный элемент множества s
Наряду со стандартным множеством set следует рассмотреть также следующие сходные структуры:
multiset – упорядоченное множество данных, сходный с set класс, за исключением того факта, что в нем могут быть равные элементы.
unordered_set – неупорядоченное множество, данный класс реализован с использованием хеш-таблиц, что позволяет ускорить операции доступа, добавления и поиска элементов практически при том же функционале (за исключением свойств сортировки).
unordered_multiset – неупорядоченный multiset (аналогично с set – unordered_set).
Например, используя multiset можно реализовать все функции «кучи» с той же асимптотикой и с большим функционалом, чем при использовании стандартного класса priority_queue:
Ассоциативный массив (map) – контейнер библиотеки map, позволяющий хранить данные в форме ключ-значение, map является отсортированным хешем по ключу и обеспечивает следующие возможности:
map < key_type, data_type > m
–
описание словаря
m[key] = data
–
добавление/изменение элемента key-data в словаре m
m.erase(key)
–
удаление элемента с ключом key из m
m.erase(it)
–
удаление элемента, на который указывает итератор it
Список (list) – наиболее часто используемая структура в Python, представляющая упорядоченную изменяемую коллекцию объектов произвольных типов (похоже на массив, но типы элементов могут отличаться).
Методы list:
a = list()
–
описание пустого списка
a[i]
–
обращение к элементу по номеру i (нумерация начинается с нуля)
len(a)
–
количество элементов в списке
a[start : finish : step]
–
срез списка в диапазоне от start до finish с шагом step
a.append(x)
–
добавление элемента x в конец списка a
a.extend(b)
–
добавляет элементы списка b в конец списка a
a.insert(i, x)
–
вставляет в i-ю позицию списка a элемент x
a.remove(x)
–
удаляет первый элемент со значением x в списке, если такого нет, то ValueError
a.pop(i)
–
возвращает и удаляет i-й элемент, если элемент не указан, то i = -1 (последний)
a.index(x, s, f)
–
возвращает индекс первого элемента со значением x в диапазоне [s,f)
Модуль array определяет массивы в Python. Массивы очень похожи на списки, но с ограничением на тип данных и размер каждого элемента. Использование массивов вместо списков экономит память и увеличивает производительность.
#пример использования array
from array import array
a = array('q', [1,2,3])
b = array('i', range(1, 11))
a.append(4)
print(a)
for x in b:
print(x, end=' ')
#Результат работы программы:
#array('q', [1, 2, 3, 4])
#1 2 3 4 5 6 7 8 9 10
Код типа
Тип в C++ (16-bit)
Тип в Python
Размер в байтах
'b'
signed char
int
1
'B'
unsigned char
int
1
'h'
signed short
int
2
'H'
unsigned short
int
2
'i'
signed int
int
2
'I'
unsigned int
int
2
'l'
signed long
int
4
'L'
unsigned long
int
4
'q'
signed long long
int
8
'Q'
unsigned long long
int
8
'f'
float
float
4
'd'
double
float
8
Размер и тип элемента в массиве определяется при его создании и может принимать значения, определенные в таблице, представленной выше.
Класс LifoQueue() модуля queue представляет собой конструктор для многопоточной очереди LIFO - стек (первым пришел - последним вышел).
Методы LifoQueue:
s = LifoQueue(maxsize)
–
инициализация стека (maxsize – максимальный его размер)
s.put(x)
–
добавление элемента в стек
s.get()
–
удаляет и возвращает элемент вершины стека
s.qsize()
–
определяет размер стека (количество элементов)
s.empty()
–
возвращает True, если стек пуст
s.full()
–
True, если стек заполнен (s.qsize() == maxsize)
#пример использования LifoQueue
from queue import LifoQueue
s = LifoQueue()
s.put(8)
s.put(7)
x = s.qsize() # x=2
while not s.empty():
print(s.get()) # 7 8
В качестве альтернативы для класса LifoQueue могут служить классы list и array.
Дек (deque) – динамическая структура данных модуля collections, позволяющая добавлять и извлекать элементы как в конец, так и в начало. Поддерживает практически все методы списка list.
Методы deque:
q = deque()
–
инициализация дека
d.append(x)
–
добавление элемента в конец дека
d.appendleft(x)
–
добавление элемента в начало дека
d.pop()
–
удаляет элемент из конца дека
d.popleft()
–
удаляет элемент из начала дека
d[i]
–
возвращает i-й элемент дека
len(d)
–
определяет размер дека
#пример использования deque
from collections import deque
d = deque() #[]
d.append(3) #[3]
d.append(5) #[3,5]
d.appendleft(2) #[2,3,5]
print(d[0], d[-1]) #2 5
d.pop() #[2,3]
d.popleft() #[3]
print(len(d)) #1
Очередь с приоритетом – динамическая структура данных, именуемая «кучей». Требуется подключение модуля heapq. Данная библиотека содержит функции для работы с кучей минимумов. Данные кучи хранятся в обычном списке list.
Методы «кучи»:
h = []
–
инициализация пустой кучи
h = heapify(a)
–
инициализация кучи из списка a
heappush(h, x)
–
добавление элемента x в кучу h
heappop(h)
–
возвращает и удаляет наименьший элемент кучи (h[0] – минимальный элемент)
heappushpop(h, x)
–
добавляет элемент x в кучу h, затем возвращает и удаляет наименьший элемент кучи
heapreplace(h, x)
–
возвращает и удаляет наименьший элемент кучи, затем добавляет в кучу элемент x
len(h)
–
количество элементов в куче
#пример использования модуля heapq
from heapq import *
h = list(map(int, input().split()))
#h = [1,6,8,7,12,11,9,16,15,13]
heapify(h)
while h:
print(heappop(h))
В качестве альтернативы для работы с очередью приоритетов можно использовать класс PriorityQueue модуля queue.
Словарь (dict) – стандартный контейнер Python, позволяющий хранить данные в форме ключ-значение. Словарь в Python является неупорядоченным ассоциативным массивом и обеспечивает следующие возможности:
d = dict()
–
инициализация пустого словаря (можно писать d = {})
d[key] = value
–
добавление/изменение элемента key-value в словаре d
x = d[key]
–
получение значения по ключу (KeyError, если нет ключа key)
x = d.get(key, val)
–
получение значения по ключу (если нет key, то возвращает val)
x = d.pop(key, val)
–
удаляет key и возвращает value (если нет key, то возвращает val)
key in d
–
True, если элемент с ключом key существует в d
d.items()
–
список кортежей вида (key, value) – все элементы словаря d
