Теормин по STL для СП, часть 1/2
Это теоретический минимум по STL для занимающихся спортивным программированием, подмножество возможностей стандартной библиотеки C++, полезных для решения алгоритмических задач. Группировка преимущественно по заголовку и контексту использования. Почти все упоминаемые имена лежат в пространстве имен std, для него и только для него следует использовать после #include
using namespace std;
,
cout, cin, while (cin >> ...)
getline, while+getline, getline после cin
: fixed, setprecision, setw, setfill, hex/dec
: noskipws/skipws
cin/cout.tie(0); cin/cout.sync_with_stdio(false); endl vs '\n'
: printf/scanf для жирных инпутов
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
string(10, ' '), std::string("a") + "b"
length/size, substr
push_back
to_string, stoi
find, rfind, find_*_of, string::npos
: stringstream ss("str"), ss.str()
isalpha, isalnum, isblank, isdigit, islower, isupper, isxdigit
tolower, toupper, использование совместно с transform
: priority_queue
: pair, make_pair, .first/.second; tuple, make_tuple, get<#>();
Лексикографическое сравнение
,
map, сортированность ключей
[key]= vs at, for (auto kv : mapa) { }
count, erase
set, insert
,
std::hash::operator()
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, : 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
: begin(cont), end(cont), size(cont)
: accumulate, partial_sum, iota
hypot, atan2, pi = atan(1) * 4
round, floor, ceil
abs
: numeric_limits::max()
: swap
: std::chrono::high_resolution_clock::now()
Compiler-specific: __builtin_popcount, __builtin_clz, __builtin_ctz, __gcd, __int128
Объяснения к каждому пункту под катом. Соавтор - udpn. Большинство примеров кода любезно предоставлены Evil_Stivie.
Еще вас могут заинтересовать:
Лексика решений TopCoder
Гримуар C++
,
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 или 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
: fixed, setprecision, setw, setfill, hex/dec
Заголовок содержит возможности форматирования, в подавляющем большинстве случаев заменяющие форматные строки 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
: 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.
: 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);
Вместо массивов в программах на C++ следует всегда использовать последовательный контейнер vector. Его размер задается в конструкторе. Можно задать значение каждого элемента, по умолчанию будет дефолтное (пустой vector, 0, "", false).
vector v(5); // {0,0,0,0,0}
vectorint>> v(2, vector(3, -1)); // {{-1,-1,-1}, {-1,-1,-1}}
Если нужно выставить размер и заполняющее значение после создания
vector v;
v.assign(4, 1.0); // {1.0, 1.0, 1.0, 1.0}
Вектор можно инициализировать списками инициализации или из пары итераторов.
vector v{1, 2, 3, 4, 5};
vector 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 v{1, 2, 3}
// По индексу
for (int i = 0; i < v.size(); ++i) {
cout << v[i] << endl;
}
// По итераторам
// auto = vector::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::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 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
int, string>> v;
// Вместо v.push_back(make_pair(5, "hello"));
v.emplace_back(5, "hello");
Кроме добавления в конец, с конца можно и удалять элементы.
vector v{1, 2, 3};
v.pop_back(); // {1, 2}
К первому и последнему элементу можно обращаться по ссылке.
vector 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 v{1, 2, 3};
vector 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 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(v));
cout << v.size() << " " << v.capacity() << endl; // 5 5
Тот же эффект имеет метод .shrink_to_fit(), введенный в C++11.
vector
Вектор специализирован для bool, чтобы элемент занимал 1 бит, это позволяет экономить память, но медленнее и не дает использовать указатели на элемент.
Вместо 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
: 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
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 из .
string s = "where is STL?!";
transform(s.begin(), s.end(), s.begin(), toupper);
cout << s << endl; // WHERE IS STL?!
Дек подобен вектору, но в него можно добавлять/удалять элементы с обоих концов за O(1). Внутри это циклический буфер переменного размера с указателями на отрезки элементов равной длины.
deque 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 без лишних методов.
: priority_queue
Очередь с приоритетами позволяет за O(logN) вставлять элементы, и за O(1) получать максимальный элемент в коллекции, за O(logN) удалять его. Внутри это бинарная куча на векторе, поддерживающая инвариант для всех i A[i] >= A[2*i + 1] && A[i] >= A[2*i + 2].
priority_queue 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
int, char>> pq;
for (int i = 0; i < 5; ++i) {
pq.emplace(i, 'a' + i);
}
cout << pq.top().second << endl; // e
: pair, make_pair, .first/.second; tuple, make_tuple, get<#>();
Два или более связанных значения можно объединить в пару или кортеж. Доступ к элементам пары через поля:
pair 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 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 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, сортированность ключей
В STL есть ассоциативный контейнер map (словарь), позволяющий сопоставлять ключу любого типа, поддерживающего operator <, значение произвольного типа. Внутри он реализован на основе почти сбалансированного бинарного красно-черного дерева, поэтому поиск по ключу занимает O(logN) сравнений, вставка и удаление O(logN). Красно-черное дерево упорядочено по ключам, ключи уникальны.
[key]= vs at, for (auto kv : mapa) { }
Вызов оператора [] автоматически создает дефолтным конструктором значение, если такого ключа раньше не было. Поэтому для константных map вместо оператора [] надо использовать метод at, бросающий исключение out_of_range при отсутствии ключа.
Итерация по map дает pair.
map 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 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 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 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
}
,
В 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 u;
for (int i = 0; i < 26; ++i) {
u.insert('a' + i);
}
for (char ch : u) {
cout << ch;
} // iabcdefghjklmnopqrstuvwxyz
std::hash::operator()
Функция hash реализована для многих типов как xor с очередным байтом и умножение в цикле. Но для многих полезных типов вроде кортежей, hash придется специализировать самостоятельно:
namespace std {
template struct hash
> {
size_t operator () (pair const& arg) const {
return hash()(arg.first) ^ hash()(arg.second);
}
};
}
Продолжение в части 2.
using namespace std;
,
cout, cin, while (cin >> ...)
getline, while+getline, getline после cin
: fixed, setprecision, setw, setfill, hex/dec
: noskipws/skipws
cin/cout.tie(0); cin/cout.sync_with_stdio(false); endl vs '\n'
: printf/scanf для жирных инпутов
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
string(10, ' '), std::string("a") + "b"
length/size, substr
push_back
to_string, stoi
find, rfind, find_*_of, string::npos
: stringstream ss("str"), ss.str()
isalpha, isalnum, isblank, isdigit, islower, isupper, isxdigit
tolower, toupper, использование совместно с transform
: priority_queue
: pair, make_pair, .first/.second; tuple, make_tuple, get<#>();
Лексикографическое сравнение
,
map, сортированность ключей
[key]= vs at, for (auto kv : mapa) { }
count, erase
set, insert
,
std::hash::operator()
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, : 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
: begin(cont), end(cont), size(cont)
: accumulate, partial_sum, iota
hypot, atan2, pi = atan(1) * 4
round, floor, ceil
abs
: numeric_limits::max()
: swap
: std::chrono::high_resolution_clock::now()
Compiler-specific: __builtin_popcount, __builtin_clz, __builtin_ctz, __gcd, __int128
Объяснения к каждому пункту под катом. Соавтор - udpn. Большинство примеров кода любезно предоставлены Evil_Stivie.
Еще вас могут заинтересовать:
Лексика решений TopCoder
Гримуар C++
,
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 или 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
: fixed, setprecision, setw, setfill, hex/dec
Заголовок содержит возможности форматирования, в подавляющем большинстве случаев заменяющие форматные строки 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
: 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.
: 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);
Вместо массивов в программах на C++ следует всегда использовать последовательный контейнер vector. Его размер задается в конструкторе. Можно задать значение каждого элемента, по умолчанию будет дефолтное (пустой vector, 0, "", false).
vector
vectorint>> v(2, vector
Если нужно выставить размер и заполняющее значение после создания
vector
v.assign(4, 1.0); // {1.0, 1.0, 1.0, 1.0}
Вектор можно инициализировать списками инициализации или из пары итераторов.
vector
vector
Обращение к элементу вектора как у массива.
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
// По индексу
for (int i = 0; i < v.size(); ++i) {
cout << v[i] << endl;
}
// По итераторам
// auto = vector::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::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
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
int, string>> v;
// Вместо v.push_back(make_pair(5, "hello"));
v.emplace_back(5, "hello");
Кроме добавления в конец, с конца можно и удалять элементы.
vector
v.pop_back(); // {1, 2}
К первому и последнему элементу можно обращаться по ссылке.
vector
cout << v.front() << endl; // 2
cout << v.back() << endl; // 32
v.back() = -1; // {2, 4, 8, 16, -1}
insert
По произвольному итератору можно вставить значение или отрезок из пары итераторов, при этом все элементы после итератора копируются за O(N).
vector
vector
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
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
cout << v.size() << " " << v.capacity() << endl; // 5 5
Тот же эффект имеет метод .shrink_to_fit(), введенный в C++11.
vector
Вектор специализирован для bool, чтобы элемент занимал 1 бит, это позволяет экономить память, но медленнее и не дает использовать указатели на элемент.
Вместо 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
: 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
isalpha, isalnum, isblank, isdigit, islower, isupper, isxdigit
В СП чаще всего полезны эти классы символов, список из 0-127:
Ожидаемо преобразуют A-Z в a-z и наоборот. Строки можно преобразовать этими функциями, используя transform из .
string s = "where is STL?!";
transform(s.begin(), s.end(), s.begin(), toupper);
cout << s << endl; // WHERE IS STL?!
Дек подобен вектору, но в него можно добавлять/удалять элементы с обоих концов за O(1). Внутри это циклический буфер переменного размера с указателями на отрезки элементов равной длины.
deque
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 без лишних методов.
: priority_queue
Очередь с приоритетами позволяет за O(logN) вставлять элементы, и за O(1) получать максимальный элемент в коллекции, за O(logN) удалять его. Внутри это бинарная куча на векторе, поддерживающая инвариант для всех i A[i] >= A[2*i + 1] && A[i] >= A[2*i + 2].
priority_queue
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
int, char>> pq;
for (int i = 0; i < 5; ++i) {
pq.emplace(i, 'a' + i);
}
cout << pq.top().second << endl; // e
: pair, make_pair, .first/.second; tuple, make_tuple, get<#>();
Два или более связанных значения можно объединить в пару или кортеж. Доступ к элементам пары через поля:
pair
cout << p.first << " " << p.second << endl; // 1 2
p = make_pair(14, 28);
cout << p.first << " " << p.second << endl; // 14 28
к элементам кортежа шаблонной функцией:
tuple
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
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, сортированность ключей
В STL есть ассоциативный контейнер map (словарь), позволяющий сопоставлять ключу любого типа, поддерживающего operator <, значение произвольного типа. Внутри он реализован на основе почти сбалансированного бинарного красно-черного дерева, поэтому поиск по ключу занимает O(logN) сравнений, вставка и удаление O(logN). Красно-черное дерево упорядочено по ключам, ключи уникальны.
[key]= vs at, for (auto kv : mapa) { }
Вызов оператора [] автоматически создает дефолтным конструктором значение, если такого ключа раньше не было. Поэтому для константных map вместо оператора [] надо использовать метод at, бросающий исключение out_of_range при отсутствии ключа.
Итерация по map дает pair.
map
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
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
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
s.insert(add.begin(), add.end());
s.erase(7);
for (int item : s) {
cout << item << " "; // 0 1 2 3 5 6 8
}
,
В 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
for (int i = 0; i < 26; ++i) {
u.insert('a' + i);
}
for (char ch : u) {
cout << ch;
} // iabcdefghjklmnopqrstuvwxyz
std::hash::operator()
Функция hash реализована для многих типов как xor с очередным байтом и умножение в цикле. Но для многих полезных типов вроде кортежей, hash придется специализировать самостоятельно:
namespace std {
template
> {
size_t operator () (pair const& arg) const {
return hash()(arg.first) ^ hash()(arg.second);
}
};
}
Продолжение в части 2.