Вектор

#include <vector>

void push_back(<type>) — добавление элемента в конец вектора. При необходимости (вектор заполнен) он расширяется вдвое;
unsigned int size() — определяет размер вектора (количество элементов);
unsigned int capacity() — возвращает максимальное количество элементов, которое может поместиться в вектор без расширения;
void resize() — изменяет размер вектора. Эта операция аналогична realloc;
void clear() — очищает содержимое вектора (размер вектора становится равным нулю).
Insert (iterator, n) вставка элемента перед тем, на который указывает итератор.
Erase (iterator) удаляет элемент, который соответствует указанному итератору.
Erase (iterator1, iterator2) удаляет диапозон элементов.
Advance(iterator, n)Операция сдвига итератора на n для любого контейнера
At(n) Альтернативный прямой доступ по индексу

Стек

#include <stack>

void push(<type>) — добавление элемента в стек;
void pop() — удаляет элемент с вершины стека;
<type> top() — возвращает элемент с вершины стека;
unsigned int size() — определяет размер стека (количество элементов);
bool empty() — возвращает истину, если стек пуст.

Очередь

#include < queue >

void push(<type>) — добавление элемента в очередь;
void pop() — удаляет элемент из головы очереди;
<type*> front() — возвращает ссылку на элемент из головы очереди;
<type*> back() — возвращает ссылку на элемент из хвоста очереди;
unsigned int size() — определяет размер очереди (количество элементов);
bool empty() — возвращает истину, если очередь пуста.

Очередь с приоритетами

#include < queue >

priority_queue <double> h; описание;
void push(<type>) — добавление элемента в кучу;
void pop() — удаляет наибольший элемент из кучи;
<type> top() — возвращает наибольший элемент в куче;
unsigned int size() — определяет размер кучи (количество элементов);
bool empty() — возвращает истину, если куча пуста.
priority_queue< int, vector<int>, greater<int> > q; - изменение приоритета на возрастание.

Множество

#include < set >

Для добавления элемента в множество используется метод insert:
S.insert(x);
Для проверки принадлежности элемента множеству используется метод count. Этот метод возвращает количество вхождения передаваемого параметра в данный контейнер, но поскольку в множестве все элементы уникальные, то count для типа set всегда возвращает 0 или 1. То есть для проверки принадлежности значения x множеству S можно использовать следующий код:
if (S.count(x)) { …
Для удаления элемента используется метод erase. Ему можно передать значение элемента, итератор, указывающий на элемент или два итератора (в этом случае удаляется целый интервал элементов, содержащийся между заданными итераторами). Вот два способа удалить элемент x:
S.erase(x); S.erase(S.find(x));
Метод size() возвращает количество элементов в множестве, метод empty(), возвращает логическое значение, равное true, если в множестве нет элементов, метод clear() удаляет все элементы из множества.

Ассоциативный массив

#include < map >

Map<int,int> m;
m[n] – ассоциативный массив. Не заполненные элементы массива не находятся в памяти. (n –ключ (first) m[n] – значение (second) )
Пройтись по элементам массива по порядку можно с помощью итераторов begin(), end().
Можно делать быструю сортировку целых чисел и нецелых чисел, символов и строк.
begin() - итератор на первый элемент;
end() - итератор на элемент идущий после последнего;
rbegin() - итератор на последний элемент (для обратных алгоритмов);
rend() - итератор на позицию перед первым элементом (для обратных алгоритмов).
размер отображения
empty() - возвращает истину, если размер отображения 0;
size() - возвращает число элементов;
max_size() - максимально возможный размер отображения.
count(key) - число элементов соответствующих указанному ключу. Для класса map значения 1 или 0;
find(key) - итератор на первый элемент с указанным ключом;
lower_bound(key) - итератор на первый элемент, чей ключ больше или равен указанному ключу;
upper_bound(key) - итератор на первый элемент, чей ключ больше указанного ключа;
equal_range(key) - диапазон элементов, чей ключ равен указанному ключу;
[] - операция индексации по ключу.
swap(map& m) - обмен значениями с другим отображением;
insert(el) - вставка элемента, возвращается его позиция;
insert(beg,end) - вставка элементов из указанного диапазона;
erase(key) - удалить указанный элемент;
erase(it), erase(start,end) - удаляет элемент с заданным итератором или между заданными
clear() - удалить все элементы.
прочие методы
Для классов перегружены операции =,[],==,!=,<,>,<=,>=.
Про работы с итераторами:
Для обращения к элементу в строках и векторах достаточно было перед именем контейнера поставить *, но в map так не получится, т.к. в каждом элементе хранится 2 значения (ключ и данные). Поэтому надо писать так:
(*iter).first - для обращения к ключу и
(*iter).second -для обращения к данным,
где iter - итератор элемента.

Строка

#include < string >

include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main(){
ifstream file_in("input.txt");
ofstream file_out("output.txt");
int i=0,k=0, a,b,c;
string s,s1;

getline(file_in,s); // ввод строки
file_in>>a>>b; // ввод чисел
c=a+b;
s=s+" papa";
s1=s.substr(6, 4); //копировать со строки s начиная с 6 четыре символа
s1.insert(2,s); // вставить за вторым символом строки s1 строку s
s1.erase(2,5); // удалить начиная со второго 5 символов
c=s.length(); // длина строки
file_out<<c<<endl;
file_out<<s<<endl;
file_in.close();
file_out.close();
return 0;}

Вывод определенного количества цифр после запятой

#include <iomanip>

cout << fixed << setprecision(3) << (13.5 / 2) << endl;
double a=1.23456;
cout << fixed << setprecision(3) << a << endl;

Пара (pair)

#include <utility>

Пара фактически является шаблонной структурой, которая содержит два поля (возможно, разных типов), они называются first и second.
Пусть, например, мы хотим создать пару из целого и вещественного числа. Тогда ее создание будет выглядеть следующим образом:
pair <int, double> p;
Теперь мы можем обращаться к p точно так же, как к обычной структуре, например, так:
p.first = 5; p.second = 3.1415;
Пары одинакового типа можно присваивать друг другу. Пары используются в ассоциативных контейнерах (о них будет сказано позже). Поля пары могут быть не только элементарного, но и составного типа, например, опять же парой. Для примера приведем реализацию структуры, хранящей дату с использованием пар (год, месяц, день):
pair <int, pair <int, int> > date1, date2;
Обратите внимание, что > разделены пробелом; если не разделять их, то эта запись будет интерпретироваться как оператор сдвига вправо >>, что приведет к ошибке при компиляции.
Обращение к полям будет выглядеть так:
int year = date1.first;
int month = date1.second.first;
int day = date1.second.second;
Не очень удобный формат, но можно придумать макросы, которые облегчат нам доступ к полям.
Крайне полезное свойство состоит в том, что пары можно сравнивать. При этом сравнение идет слева направо. Таким образом, для нашей даты сначала сравнятся годы, при равных годах сравнятся месяцы и т.д. Это очень удобно использовать при сортировке.

Геометрия

Коэфициенты прямой А, В, С

A:=y 2 —y 1; B:=x1-x 2; С : = —x1*А-y1*В.

Точка пересечения отрезков

У = (А₁С₂-А₂С₁)/(A₂B₁-A₁B₂); X = (B₁С₂-B₂С₁)/(B₂A₁-B₁A₂);

Расстояние от очки до прямой

D = abs(Ax+By+C)/T; T²=A²+B²

Реализация поиска в глубину

vector < vector<int> > g; // граф
int n; // число вершин

vector<char> used;

void dfs (int v) {
used[v] = true;
for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
if (!used[*i])
dfs (*i);

Поиск в глубину на паскале (1)

procedure find(i:integer);
begin
was[i]:=1;
for j:=1 to n do
if (gr[i,j]=1)and(was[j]=0) then
find(j);
end;

Поиск в глубину на паскале (2)

procedure find(i:integer);
begin
if was[i]<>0 then
exit;
was[i]:=1;
for j:=1 to n do
if gr[i,j]=1 then
find(j);
end;


Граф двухдольный или нет

procedure find(i,c:integer);
var j:integer;
begin
if was[i]<>0 then begin
if was[i]<>c then печать и выход из программы;
exit;
end;
was[i]:=c;
for j:=1 to n do
if gr[i,j]=1 then begin
find(j,3-c);
end;
end;


Топологическая сортировка в графе

procedure find(i:integer);
begin
if was[i]<>0 then exit;
was[i]:=1;
for j:=1 to n do
if gr[i,j]<>0 then
find(j);
out[pos]:=i; // cначала pos равно n
n:=n-1;
end;


Граф циклический или нет (дерево)

procedure find(i:integer);
begin
if was[i]=1 then (граф цикличный, выход);
was[i]:=1;
for j:=1 to n do
if gr[i,j]<>0 then
find(j);
end;
Алгоритм Дейстры
#include<iostream>
#include<queue>
#include<utility>
using namespace std;

int a[101][101],m[101],sum;

int main(){
pair<int,int> p;
priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > > q;
long int k,d,t,n,s,f,i,j,x,y,b[101];
cin>>n>>s>>f;
for(i=1;i<=n;i++){
cin>>k>>d>>t;
a[k][d]=t;
a[d][k]=t;}

for(i=1;i<=n;i++) b[i]=1000000;
p.first=0;
p.second=1;
q.push(p);
while(!q.empty()){
x=q.top().first;
y=q.top().second;
for(i=1;i<=n;i++){
if(a[y][i]>0 && m[i]!=1 && b[i]>x+a[y][i]){
p.first=x+a[y][i];
p.second=i;
b[i]=x+a[y][i];
q.push(p);
}
}
m[y]=1;
q.pop();
}
if(b[f]==1000000) cout<<"-1";
else cout<<b[f];
return 0;}

Каркас минимальной длины (выводиться длина)
#include<iostream>
#include<utility>
#include<queue>
using namespace std;

int main(){
int n,m,i,j,a,b,c,k=0,x,y,mark[101],z,z2,sum=0;
pair<int,pair<int,int> > p;
priority_queue< pair<int,pair<int,int> >, vector<pair<int,pair<int,int> > >, greater<pair<int,pair<int,int> > > > q;
cin>>n>>m;
for(i=1;i<=m;i++){
cin>>a>>b>>c;

p.first=c;
p.second.first=a;
p.second.second=b;
q.push(p);
}
for(i=1;i<=n;i++) mark[i]=i;
while(k<n-1){
x=q.top().second.first;
y=q.top().second.second;
if(mark[x]!=mark[y]){
k++;sum=sum+q.top().first;
z=mark[x];z2=mark[y];
if(mark[x]<mark[y]){
for(i=1;i<=n;i++)
if(mark[i]==z2) mark[i]=mark[x];
}
else{
for(i=1;i<=n;i++)
if(mark[i]==z) mark[i]=mark[y];
}
}
q.pop();
}
cout<<sum;
return 0;}

Каркас минимаальной длины (выводиться дерево)
include<iostream>
#include<queue>
using namespace std;

int m[10];

int main(){
int n,k,a[10],b,c,d,i,mark[10],j;
pair<int,pair<int,int> > p;
priority_queue< pair<int,pair<int,int> >, vector<pair<int,pair<int,int> > >, greater<pair<int,pair<int,int> > > > q;
cin>>n>>k;

for(i=1;i<=k;i++){
cin>>b>>c>>d;
p.first=d;
p.second.first=b;
p.second.second=c;
q.push(p);
}
cout<<endl;
for(i=1;i<=n;i++) mark[i]=i;
i=0;
while(i<n){
if(mark[q.top().second.first]!=mark[q.top().second.second]){
cout<<q.top().second.first<<" "<<q.top().second.second<<" "<<q.top().first;
cout<<endl;
i++;
if(q.top().second.first<q.top().second.second) {
for(j=1;j<=n;j++){
if(mark[j]==mark[q.top().second.second]) mark[j]=mark[q.top().second.first];
}
}
else{
for(j=1;j<=n;j++){
if(mark[j]==q.top().second.first) mark[j]=q.top().second.second;
}
}
q.pop();

}
else q.pop();
}
return 0;}

Циклы Эйлера в графе
#include<iostream>
using namespace std;

int a[100][100],n,k,l=0,c[100];

void foo(int j){
int i;
for(i=1;i<=n;i++)
if(a[j][i]!=0){
a[j][i]=0;
a[i][j]=0;
foo(i);}
l++;
c[l]=j;
cout<<c[l]<<" ";
}

int main(){
int z,x,y,c,f,g,sum=0;
cin>>n>>k;
for(z=1;z<=k;z++){
cin>>x>>y;
a[x][y]=1;
a[y][x]=1;}

for(f=1;f<=n;f++)
for(g=1;g<=n;g++){
if(a[f][g]!=0)sum++;
if(g==n && sum%2!=0) {
cout<<"no";
return 0;
}
if(g==n) sum=0;}
z=1;
foo(z);
return 0;}

Поиск в глубину на векторе
#include<iostream>
#include<vector>
using namespace std;

int Nnew[10];
vector<int> v[10];

void foo(int j){
vector<int>:: iterator it;
cout<<j<<" ";
Nnew[j]=1;
for(it=v[j].begin();it<v[j].end();it++){
if(Nnew[*it]!=1) foo(*it);
}
}
int main(){
int n,i,m,l;
cin>>n;
for(i=1;i<=n;i++){
cin>>m>>l;
v[m].push_back(l);
v[l].push_back(m);
}

i=1;
foo(i);
return 0;}
Поиск в ширину на векторе
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int Nnew[10];

int main(){
int n,i,j,m,l;
vector<int> v[10];
vector<int>:: iterator it;
queue<int> q;
cin>>n;
for(i=1;i<=n;i++){
cin>>m>>l;
v[m].push_back(l);
v[l].push_back(m);
}

q.push(1);
while(!q.empty()){
cout<<q.front()<<" ";
Nnew[q.front()]=1;
for(it=v[q.front()].begin();it<v[q.front()].end();it++){
if(Nnew[*it]!=1) q.push(*it);
}
q.pop();
}
return 0;}
Топологическая сортировка
#include<iostream>
#include<stack>
using namespace std;

int a[10][10],n,k,c[10];
stack<int> s;
void foo(int b){
int j;
c[b]=1;
for(j=1;j<=n;j++)
if(a[b][j]!=0 && c[j]!=2){
foo(j);}
c[b]=2;
s.push(b);
}

int main(){
int x,y,i;
cin>>n>>k;
for(i=1;i<=k;i++){
cin>>x>>y;
a[x][y]=1;}

foo(1);
while(!s.empty()) {
cout<<s.top()<<" ";
s.pop();}
return 0;}