sharpc (sharpc) wrote,
sharpc
sharpc

Category:

Теормин по STL для СП, часть 1/2

Это теоретический минимум по STL для занимающихся спортивным программированием, подмножество возможностей стандартной библиотеки C++, полезных для решения алгоритмических задач. Группировка преимущественно по заголовку и контексту использования. Почти все упоминаемые имена лежат в пространстве имен std, для него и только для него  следует использовать после #include

using namespace std;



<iostream>, <iomanip>
    cout, cin, while (cin >> ...)
    getline, while+getline, getline после cin
    <iomanip>: fixed, setprecision, setw, setfill, hex/dec
    <iomanip>: noskipws/skipws
    cin/cout.tie(0); cin/cout.sync_with_stdio(false); endl vs '\n'
<cstdio>: printf/scanf для жирных инпутов
<vector>
    clean != empty
    begin, end, rbegin, rend
    push_back, pop_back, emplace_back, front, back
    insert
    size, resize, capacity, reserve, swap hack/shrink_to_fit
    vector<bool>
<string>
    string(10, ' '), std::string("a") + "b"
    length/size, substr
    push_back
    to_string, stoi
    find, rfind, find_*_of, string::npos
<sstream>: stringstream ss("str"), ss.str()
<cctype>
    isalpha, isalnum, isblank, isdigit, islower, isupper, isxdigit
    tolower, toupper, использование совместно с transform
<deque>
<queue>: priority_queue
<tuple>: pair, make_pair, .first/.second; tuple, make_tuple, get<#>();
Лексикографическое сравнение
<map>, <set>
    map, сортированность ключей
    [key]= vs at, for (auto kv : mapa) { }
    count, erase
    set, insert
<unordered_set>, <unordered_map>
    std::hash<T>::operator()
<algorithm>
    min, max, minmax, max_element, min_element
    sort, предикат с tie, stable_sort, is_sorted
    sort/iota + next_permutation
    unique/remove/remove_if + .erase
    reverse
    fill, copy, copy_n, <iterator>: back_inserter, istream_iterator
    most vexing parse
    find, find_if, count, count_if
    search
    includes, set_union, set_intersection, set_difference, set_symmetric_difference
    lower_bound/upper_bound
<iterator>: begin(cont), end(cont), size(cont)
<numeric>: accumulate, partial_sum, iota
<cmath>
    hypot, atan2, pi = atan(1) * 4
    round, floor, ceil
    abs
<complex>
<limits>: numeric_limits<int>::max()
<random>
<utility>: swap
<bitset>
<chrono>: std::chrono::high_resolution_clock::now()
<functional>
Compiler-specific: __builtin_popcount, __builtin_clz, __builtin_ctz, __gcd, __int128


Объяснения к каждому пункту под катом. Соавтор — udpn. Большинство примеров кода любезно предоставлены Evil_Stivie.

Еще вас могут заинтересовать:
Лексика решений TopCoder
Гримуар C++



<iostream>, <iomanip>

cout, cin, while (cin >> ...)

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

int n = 123123123;
char ch = 'a' + 3;
long long ll = 92233720368547758LL;
cout << n << " " << ch << " " << ll << endl; // 123123123 d 92233720368547758

Аналогично, ввод не требует форматной строки и использования указателей.

int k;
cin >> k;
cout << k << endl;

В некоторых задачах точный размер ввода не дан и вводить предлагается до EOF (run.exe<file или Ctrl-Z в stdin). Перегрузка оператора >> у потоков ввода возвращает istream&, который может быть неявно скастован к bool, каст возвращает !fail(), а fail() возвращает true при попытке чтения после EOF.

int k, sum = 0;
while (cin >> k) { // читает до EOF
    sum += k;
}
cout << sum << endl; // сумма введенных до EOF целых чисел

getline, while+getline, getline после cin

В некоторых задачах требуется выполнить ввод всей строки до перевода строки, простое string s; cin >> s; вводит до первого пробельного символа. Тогда следует использовать getline, который тоже возвращает istream& с тем же способом обработки EOF. Завершающий перевод строки не пишется в строковую переменную.

aa bb
cc ddddd^Z


string s1, s2;
while (getline(cin, s1)) { // читает до EOF
    s2 += s1;
}
cout << s2.length() << endl; // 13

Следует добавить, что cin >> var; не вводит перевод строки, поэтому может понадобиться сделать дополнительный вызов getline, чтобы его съесть.

stringstream ss("5\na b c");
int n;
string s;
ss >> n;
getline(ss, s); // ест перевод строки после 5
getline(ss, s); // читает вторую строку
cout << n << " : " << s << endl; // 5 : a b c

<iomanip>: fixed, setprecision, setw, setfill, hex/dec

Заголовок <iomanip> содержит возможности форматирования, в подавляющем большинстве случаев заменяющие форматные строки printf.

Манипуляторы setprecision и fixed позволяют выставлять точность вывода вещественных чисел для всех последующих <<, указывая число всех цифр или цифр после запятой.

double n = 3.141592653;
cout << setprecision(5) << n << endl; // 3.1416
cout << fixed << setprecision(5) << n << endl; // 3.14159

Пара setw и setfill позволяет выводить строку или число на указанное число позиций, возможно, заполняя их чем-то непробельным.

cout << setw(8) << "hello" << endl; // "  hello"
cout << setfill('0') << setw(3) << 7 << endl; // "007"

Манипуляторы hex и dec позволяют выводить целые числа в шестнадцатеричной или десятичной системе счисления.

int n;
stringstream("2A") >> hex >> n;
cout << dec << n << endl; // 42
cout << hex << 42 << endl; // 2a

<iomanip>: noskipws/skipws

По умолчанию cin вводит несколько char, пропуская пробельные символы. Манипуляторы noskipws/skipws позволяют переключить это поведение.

char s1, s2, s3;
stringstream("a b c") >> s1 >> s2 >> s3;
cout << s1 << ", " << s2 << ", " << s3 << endl; // a, b, c
stringstream("a b c") >> noskipws >> s1 >> s2 >> s3;
cout << s1 << "," << s2 << "," << s3 << endl; // a, ,b

cin/cout.tie(0); cin/cout.sync_with_stdio(false); endl vs '\n'

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

cin.tie(0);
cin.sync_with_stdio(false);

для объемного ввода, или такая же с cout для объемного вывода.

Как правило, в СП следует использовать << endl для перевода строки при выводе. Он аналогичен << '\n' << flush. Манипулятор flush выводит все из буфера в вывод, при выводе очень большого количества строк это изрядно тормозит. В этом случае стоит заменить все endl на "\n", оставив в конце endl или flush.

<cstdio>: printf/scanf для жирных инпутов

Если заставить потоки ввода-вывода зайти в TL никак не получается (только если дело именно в этом и только из-за этого), можно использовать сишные функции.

int n;
long long n_l;
double d;
float f;
char s[5];
char ch;
scanf("%d %lld %lf %f %s %c", &n, &n_l, &d, &f, &s, &ch);
printf("%d %lld %lf %f %s %c", n, n_l, d, f, s, ch);

<vector>

Вместо массивов в программах на C++ следует всегда использовать последовательный контейнер vector. Его размер задается в конструкторе. Можно задать значение каждого элемента, по умолчанию будет дефолтное (пустой vector, 0, "", false).

vector<int> v(5); // {0,0,0,0,0}
vector<vector<int>> v(2, vector<int>(3, -1)); // {{-1,-1,-1}, {-1,-1,-1}}

Если нужно выставить размер и заполняющее значение после создания

vector<double> v;
v.assign(4, 1.0); // {1.0, 1.0, 1.0, 1.0}

Вектор можно инициализировать списками инициализации или из пары итераторов.

vector<int> v{1, 2, 3, 4, 5};
vector<int> v2(v.begin() + 2, v.begin() + 4); // {3, 4}

Обращение к элементу вектора как у массива.

cout << v2[0]; // 3

Вектор имеет почти ту же производительность, что и массив, поэтому в release он не проверяет границы массива. Можно заставить его это делать (и кидать исключение при нарушении):

cout << v2.at(2); // Exception: out_of_range

clean != empty

Очистить (не путать с проверить v.empty() (а есть такие, кто путает?)), работает для любого контейнера.

v.clear();

begin, end, rbegin, rend

Есть несколько способов проитерироваться по контейнеру (пример для vector):

vector<int> v{1, 2, 3}

// По индексу
for (int i = 0; i < v.size(); ++i) {
    cout << v[i] << endl;
}

// По итераторам
// auto = vector<int>::iterator
for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << endl;
}

// Рекомендуемый: С++11 range-based for
for (int item : v) {
    cout << item << endl;
}

Контейнер можно обойти и в обратном порядке.

// auto = vector<int>::reverse_iterator
for (auto it = v.rbegin(); it != v.rend(); ++it) {
    cout << *it << endl;
}

push_back, pop_back, emplace_back, front, back

Вектор это динамический массив, ему в конец можно добавлять за амортизированную O(1) новые элементы (push_back) , меняя размер (size). Чтобы такая сложность соблюдалась, вектор выделяет больше памяти, чем нужно (сколько именно — capacity), а при достижении лимита (.size() == .capacity()) увеличивает размер сразу в 1.5-2 раза (пример для MSVC), копируя старые элементы (что портит все итераторы).

vector<int> v;
for (int i = 0; i < 16; ++i) {
    v.push_back(123);
    cout << v.size() << "-" << v.capacity() << " ";
}
// 1-1 2-2 3-3 4-4 5-6 6-6 7-9 8-9 9-9 10-13 11-13 12-13 13-13 14-19 15-19 16-19

Если объект для вставки нужно сначала создать (например, пару), конструктор и push_back можно объединить в один вызов, экономящий копирование.

vector<pair<int, string>> v;
// Вместо v.push_back(make_pair(5, "hello"));
v.emplace_back(5, "hello");

Кроме добавления в конец, с конца можно и удалять элементы.

vector<int> v{1, 2, 3};
v.pop_back(); // {1, 2}

К первому и последнему элементу можно обращаться по ссылке.

vector<int> v{2, 4, 8, 16, 32};
cout << v.front() << endl; // 2
cout << v.back() << endl; // 32
v.back() = -1; // {2, 4, 8, 16, -1}

insert

По произвольному итератору можно вставить значение или отрезок из пары итераторов, при этом все элементы после итератора копируются за O(N).

vector<int> v{1, 2, 3};
vector<int> w{5, 6};
v.insert(v.begin() + 1, w.begin(), w.end()); // {1, 5, 6, 2, 3}
v.insert(v.begin() + 2, 8); // {1, 5, 8, 6, 2, 3}

size, resize, capacity, reserve, swap hack/shrink_to_fit

У существующего вектора можно изменить размер

vector<int> v{1, 2, 3};
v.resize(5, -1); // {1, 2, 3, -1, -1}

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

cout << v.size() << " " << v.capacity() << endl; // 5 5
v.reserve(1000);
cout << v.size() << " " << v.capacity() << endl; // 5 1000

С помощью reserve емкость можно изменить только вверх, но можно пересоздать вектор с существующими элементами и минимальной емкостью одной строкой (так называемый swap hack). Это может быть полезно, если суммарный размер векторов в каждый момент ограничен, но суммарный максимальный слишком велик.

v.swap(vector<int>(v));
cout << v.size() << " " << v.capacity() << endl; // 5 5

Тот же эффект имеет метод .shrink_to_fit(), введенный в C++11.

vector<bool>

Вектор специализирован для bool, чтобы элемент занимал 1 бит, это позволяет экономить память, но медленнее и не дает использовать указатели на элемент.

<string>

Вместо zero-terminated C-строк в программах на C++ следует всегда использовать string.

string s = "hello, world!";
char c = s[6]; // аналогично вектору s.at(6);
cout << s << endl;
s += c; s += s; // Конкатенация: "hello, world! hello, world! "

string(10, ' '), std::string("a") + "b"

Конструктор string, как и у vector, позволяет указывать число элементов и сам элемент.

cout << string(5, '!') << endl; // "!!!!!"

Для совместимости с C строковый литерал "a" это char const *, + их не конкатенирует.

string s = "AaBb";
s += string("C") + "c"; // s += "C" + "c" дает compilation error
cout << s << endl; // AaBbCc

В С++14 появился литерал, создающий строки.

string s = "a"s + "b";

length/size, substr

Аналогично vector, string имеет методы assign, clear, empty, begin, end, rbegin, rend, size, resize, capacity, reserve. Синонимом для size служит length.

string t = "Hedgehog is gonna get out from that jail";
cout << t.length() << endl; // 40

Подстрока (начало, длина):

cout << t.substr(18, 3) << endl; // "get"

push_back

Аналогично vector, string имеет методы, push_back, pop_back, front, back, insert.

string s;
for (int i = 0; i < 10; ++i) {
    s.push_back('a' + i);
}
cout << s << endl; // abcdefghij

to_string, stoi

Числовые типы можно преобразовать в строку to_string и обратно семейством stoi/stoll/stoull/stof/stod.

double pi = 3.14159265;
string s = "Pi = " + to_string(pi);
cout << s << endl; // Pi = 3.141593

s = "12345678901";
//cout << stoi(s) << endl; // Exception: out_of_range
cout << stoll(s) << endl; // 12345678901

find, rfind, find_*_of, string::npos

В string можно искать подстроки (тривиальным алгоритмом за O(NM)). Необязательный второй аргумент — смещение, с которого начинать поиск. Если подстроки нет, возвращается string::npos.

string s = "hello, world!";
//          0123456789012
cout << s.find("wo") << endl; // 7
cout << boolalpha << (s.find("hi") == string::npos) << endl; // true

Поиск с конца (найденная подстрока будет иметь начало не правее смещения):

cout << s.rfind("l", 9) << endl; // 3

Такой цикл найдет все вхождения подстроки

size_t off = 0;
while (true) {
    off = s.find("l", off);
    if (off == string::npos) { break; }
    cout << off << endl; // 2 3 10
    off += 1;
}

Кроме подстрок, можно искать символы из некоторого множества методом find_first_of. Аналогично find_first_not_of ищет символы, не принадлежащие множеству, а find_last_of и find_last_not_of ищут такие символы с конца строки.

cout << s.find_last_of("aeiou") << endl; // последняя гласная на позиции 8

<sstream>: stringstream ss("str"), ss.str()

Строковый поток ввода-вывода аналогичен cin/cout, но работает не с stdin/stdout, а со строкой.

stringstream ss;
ss << 2 << " " << 4 << " " << 8;
string s = ss.str();
cout << s << endl; // "2 4 8"

stringstream ss("1 2 3");
int n1, n2, n3;
ss >> n1 >> n2 >> n3;
cout << n1 << " " << n2 << " " << n3 << endl; // 1 2 3

<cctype>

isalpha, isalnum, isblank, isdigit, islower, isupper, isxdigit

В СП чаще всего полезны эти классы символов, список из 0-127:

  • isalpha — A-Za-z
  • isalnum — 0-9A-Za-z
  • isblank — \t и пробел
  • isdigit — 0-9
  • islower — a-z
  • isupper — A-Z
  • isxdigit — 0-9A-Fa-f
  • tolower, toupper, использование совместно с transform

    Ожидаемо преобразуют A-Z в a-z и наоборот. Строки можно преобразовать этими функциями, используя transform из <algorithm>.

    string s = "where is STL?!";
    transform(s.begin(), s.end(), s.begin(), toupper);
    cout << s << endl; // WHERE IS STL?!

    <deque>

    Дек подобен вектору, но в него можно добавлять/удалять элементы с обоих концов за O(1). Внутри это циклический буфер переменного размера с указателями на отрезки элементов равной длины.

    deque<int> d;
    d.push_back(3);
    d.push_front(2);
    d.push_back(4);
    d.push_front(1);
    d.push_back(5);
    for (int i = 0; i < d.size(); ++i) {
        cout << d[i] << " ";
    }
    cout << endl; // 1 2 3 4 5

    На основе deque построены std::stack и std::queue, которые просто оставляют обернутый deque без лишних методов.

    <queue>: priority_queue

    Очередь с приоритетами позволяет за O(logN) вставлять элементы, и за O(1) получать максимальный элемент в коллекции, за O(logN) удалять его. Внутри это бинарная куча на векторе, поддерживающая инвариант для всех i A[i] >= A[2*i + 1] && A[i] >= A[2*i + 2].

    priority_queue<int> pq;
    for (int i = 0; i < 5; ++i) {
        pq.push(i);
    }
    while (pq.size()) {
        int item = pq.top();
        cout << item << " ";
        pq.pop();
    }
    cout << endl; // 4 3 2 1 0

    Обычно очередь с приоритетами используют над парами (приоритет, задание), откуда она и получила свое название.

    priority_queue<pair<int, char>> pq;
    for (int i = 0; i < 5; ++i) {
        pq.emplace(i, 'a' + i);
    }
    cout << pq.top().second << endl; // e

    <tuple>: pair, make_pair, .first/.second; tuple, make_tuple, get<#>();

    Два или более связанных значения можно объединить в пару или кортеж. Доступ к элементам пары через поля:

    pair<int, int> p(1, 2);
    cout << p.first << " " << p.second << endl; // 1 2
    p = make_pair(14, 28);
    cout << p.first << " " << p.second << endl; // 14 28

    к элементам кортежа шаблонной функцией:

    tuple<int, int, int> tp(1, 2, 3);
    cout << get<0>(tp) + get<1>(tp) + get<2>(tp) << endl; // 6
    tp = make_tuple(14, 28, 42);
    cout << get<0>(tp) + get<1>(tp) + get<2>(tp) << endl; // 84

    Лексикографическое сравнение

    Для последовательных контейнеров (vector, string, deque, pair, tuple) в STL определен оператор <, сравнивающий их лексикографически (сначала по первому элементу, если равны, по второму, и так далее), а значит, их можно сравнивать, а контейнеры из них — сортировать.

    Сравнение векторов:

    vector<int> box1(3), box2(3);
    for (int i = 0; i < 3; ++i) { cin >> box1[i]; }
    for (int i = 0; i < 3; ++i) { cin >> box2[i]; }

    sort(box1.begin(), box1.end());
    sort(box2.begin(), box2.end());

    if (box1 <= box2) {
        cout << "You can put the first box into the second one" << endl;
    } else if (box2 <= box1) {
        cout << "You can put the second box into the first one" << endl;
    } else {
        cout << "You can't put one box into another" << endl;
    }

    Сравнение строк:

    cout << boolalpha << (string("a") < string("abcd")) << endl; // true
    cout << boolalpha << (string("a") < string("ABCD")) << endl; // false

    Сравнение пар:

    cout << boolalpha << (make_pair(1, 2) < make_pair(1, 3)) << endl; // true

    <map>, <set>

    map, сортированность ключей

    В STL есть ассоциативный контейнер map (словарь), позволяющий сопоставлять ключу любого типа, поддерживающего operator <, значение произвольного типа. Внутри он реализован на основе почти сбалансированного бинарного красно-черного дерева, поэтому поиск по ключу занимает O(logN) сравнений, вставка и удаление O(logN). Красно-черное дерево упорядочено по ключам, ключи уникальны.

    [key]= vs at, for (auto kv : mapa) { }

    Вызов оператора [] автоматически создает дефолтным конструктором значение, если такого ключа раньше не было. Поэтому для константных map вместо оператора [] надо использовать метод at, бросающий исключение out_of_range при отсутствии ключа.

    Итерация по map дает pair<TKey, TValue>.

    map<char, int> m;
    for (char ch : string("hello, world!")) {
        m[ch] += 1;
    }
    cout << m.size() << endl; // 10
    for (auto kv : m) {
        cout << kv.first << "-" << kv.second << " ";
    } //  -1 !-1 ,-1 d-1 e-1 h-1 l-3 o-2 r-1 w-1

    count, erase

    Проверить наличие ключа в map можно, либо сравнивая m.find(key) (возвращает итератор) с m.end(), либо воспользовавшись методом count.

    map<char, int> m{{'a', 1}, {'c', 1}, {'b', 0}, {'d', 2}, {'f', 1}};
    cout << m.count('a') << " " << m.count('e') << endl; // 1 0

    Удалять из map можно методом erase, который может принимать и ключ, и итератор, и отрезок, заданный двумя итераторами.

    m.erase('c'); // {'a': 1, 'b': 0, 'd': 2, 'f': 1}
    m.erase(m.find('f')); // {'a': 1, 'b': 0, 'd': 2}

    set, insert

    Контейнер set (множество) подобен map, только без значений и, следовательно, без []. Вставку делает метод insert (как элемента, так и отрезка итераторов).

    set<int> s{1, 2, 3, 5, 6};
    cout << s.count(1) << " " << s.count(4) << endl; // 1 0

    cout << s.size() << endl; // 5
    s.insert(2);
    cout << s.size() << endl; // 5
    s.insert(0);
    cout << s.size() << endl; // 6

    vector<int> add{6, 7, 8};
    s.insert(add.begin(), add.end());

    s.erase(7);

    for (int item : s) {
        cout << item << " "; // 0 1 2 3 5 6 8
    }

    <unordered_set>, <unordered_map>

    В STL реализована открытая хэш-таблица, позволяющая вставку и поиск ключа за амортизированную O(1). Ее реализация опирается на std::list, хранящий все вставленные элементы в порядке обхода контейнера, и указатели внутрь этого списка на голову и хвост b = 2n бакетов в векторе длины 2b. Число бакетов поддерживается не меньшим, чем число элементов. При исчерпании размера происходит изменение числа бакетов в 2 раза (в MSVC при маленьком размере хэш-таблицы сразу в 8 раз) и пересчет хэша std::hash для всех элементов.

    Контейнеры unordered_map и unordered_set подобны map и set, но ключи отсортированы по hash % u.bucket_count().

    unordered_set<char> u;
    for (int i = 0; i < 26; ++i) {
        u.insert('a' + i);
    }
    for (char ch : u) {
        cout << ch;
    } // iabcdefghjklmnopqrstuvwxyz

    std::hash<T>::operator()

    Функция hash реализована для многих типов как xor с очередным байтом и умножение в цикле. Но для многих полезных типов вроде кортежей, hash придется специализировать самостоятельно:

    namespace std {
    template<typename T1, typename T2> struct hash<pair<T1, T2>> {
        size_t operator () (pair<T1, T2> const& arg) const {
            return hash<T1>()(arg.first) ^ hash<T2>()(arg.second);
        }
    };
    }




    Продолжение в части 2.
    Tags: #include, олимпиады, программирование
    Subscribe

    • Ферматистов++

      #include <iostream> using namespace std; int main() { int x = 232900, y = 519944, z = 535076; cout << boolalpha <<…

    • Инфраструктура Python

      В ноябре 2017 я начал собирать в виде IPython Notebook сниппеты работы с разными полезными для исследовательского программирования библиотеками…

    • Ежегодных контестов псто 2019

      Google Code Jam В качестве решений принимается код программы на C, C++, Python, Java, Bash, Go, добавили C#, Haskell, Javascript, PHP и Ruby. 5…

    • Post a new comment

      Error

      default userpic

      Your IP address will be recorded 

      When you submit the form an invisible reCAPTCHA check will be performed.
      You must follow the Privacy Policy and Google Terms of use.
    • 3 comments