4.5 Другие структуры¶

В стандартной библиотеке C++ есть несколько полезных структур данных, которые не попали в предыдущие разделы, но часто встречаются в задачах.

flowchart TB
    A[Что нужно?]

    A -- Битовая маска --> B[bitset]
    A -- Операции с двух концов --> C[deque]
    A -- LIFO --> D[stack]
    A -- FIFO --> E[queue]
    A -- Максимум или минимум сверху --> F[priority_queue]
    A -- Индексация в упорядоченном множестве --> G[indexed_set]

Bitset¶

bitset — это массив битов (значения только 0 или 1) фиксированной длины, известной во время компиляции.

Зачем он нужен¶

• Экономит память: один элемент занимает 1 бит, а не, скажем, 1 байт или 4 байта.
• Быстрые операции над множествами: &, |, ^, ~ выполняются сразу над блоками битов (очень эффективно на практике).

Пример: выставляем биты вручную¶

#include <bits/stdc++.h>
using namespace std;

int main() {
    bitset<12> s;      // 12 бит: индексы 0..11
    s[2] = 1;
    s[5] = 1;
    s[9] = 1;

    cout << s[5] << "\n"; // 1
    cout << s[6] << "\n"; // 0
}

Пример: создаём из строки¶

Строка читается справа налево: самый правый символ — это бит 0.

#include <bits/stdc++.h>
using namespace std;

int main() {
    bitset<12> s(string("001001000101"));

    cout << s[2] << "\n"; // 1
    cout << s[3] << "\n"; // 0
}

Сколько единиц?¶

bitset<12> s(string("001001000101"));
cout << s.count() << "\n"; // число единиц

Побитовые операции¶

bitset<8> a(string("10110010"));
bitset<8> b(string("11000101"));

cout << (a & b) << "\n";
cout << (a | b) << "\n";
cout << (a ^ b) << "\n";

Deque¶

deque (double-ended queue) — динамический массив, у которого можно эффективно добавлять и удалять элементы с обоих концов.

У deque есть всё, что есть у vector (push_back, pop_back, доступ по []), и дополнительно:

• push_front — добавить в начало
• pop_front — удалить из начала

Пример:

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> d;

    d.push_back(10);   // [10]
    d.push_back(4);    // [10,4]
    d.push_front(7);   // [7,10,4]

    d.pop_back();      // [7,10]
    d.pop_front();     // [10]

    cout << d.front() << "\n"; // 10
}

Обычно deque чуть медленнее vector из‑за более сложной внутренней организации, но операции на концах остаются O(1) в среднем.

Stack¶

stack — структура данных «стек»:

• push(x) — положить элемент наверх
• pop() — снять верхний элемент
• top() — посмотреть верхний элемент

Все эти операции работают за O(1).

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;

    st.push(8);
    st.push(1);
    st.push(6);

    cout << st.top() << "\n"; // 6
    st.pop();
    cout << st.top() << "\n"; // 1
}

Queue¶

queue — обычная очередь «первым пришёл — первым вышел»:

• push(x) — добавить в конец
• pop() — удалить из начала
• front() — первый элемент
• back() — последний элемент

Операции добавления/удаления — O(1).

#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<string> q;

    q.push("alpha");
    q.push("beta");
    q.push("gamma");

    cout << q.front() << "\n"; // alpha
    q.pop();
    cout << q.front() << "\n"; // beta
}

Priority queue¶

priority_queue хранит элементы так, чтобы можно было быстро получать «самый приоритетный» элемент.

• Вставка: O(log n)
• Удаление верхнего: O(log n)
• Просмотр верхнего: O(1)

По умолчанию в C++ это max-heap (наверху — максимум).

#include <bits/stdc++.h>
using namespace std;

int main() {
    priority_queue<int> pq;

    pq.push(4);
    pq.push(9);
    pq.push(1);
    pq.push(7);

    cout << pq.top() << "\n"; // 9
    pq.pop();
    cout << pq.top() << "\n"; // 7
}

Мини-куча (min-heap)¶

Чтобы наверху был минимум, задают компаратор greater:

priority_queue<int, vector<int>, greater<int>> pq;

Policy-based data structures (PBDS)¶

Компилятор g++ поддерживает ряд структур данных, которые не входят в стандарт C++, но иногда очень помогают в олимпиадных задачах.

Один из самых известных примеров — tree (упорядоченное множество с поддержкой порядковой статистики).

Подключение:

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

indexed_set: как set, но с индексами¶

Сделаем структуру, которая:

• хранит уникальные элементы, как set

• умеет:

• find_by_order(i) — i-й (0‑индекс) элемент в отсортированном порядке

• order_of_key(x) — сколько элементов строго меньше x

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

using indexed_set = tree<
    int,
    null_type,
    less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update
>;

int main() {
    indexed_set s;
    s.insert(5);
    s.insert(1);
    s.insert(8);
    s.insert(3);

    // элементы по порядку: [1,3,5,8]

    auto it = s.find_by_order(2);
    cout << *it << "\n"; // 5

    cout << s.order_of_key(5) << "\n"; // 2 (меньше 5: 1 и 3)

    cout << s.order_of_key(7) << "\n"; // 3 (меньше 7: 1,3,5)
}

Обе операции работают за O(log n).

Мини-итог¶

• bitset — компактные биты + быстрые побитовые операции.
• deque — «вектор», но можно быстро работать с обоими концами.
• stack/queue — классические структуры для LIFO/FIFO.
• priority_queue — быстрый доступ к максимуму/минимуму.
• PBDS tree — «прокачанный set» с порядковыми статистиками.