Многопоточное программирование (Лекция 1). Стандарты C++, контейнеры C++, красно-черные деревья, B-деревья

Литература

Джеф Элджер. С++: Библиотека пограммиста
Jeff Alger. C++ for Real Programmers

Стандарты C++

C++98/C++03
Boost
C++11
C++14

Контейнеры C++

STL
STL (C++11)
Boost

Контейнеры STL

Последовательные контейнеры
Ассоциативные контейнеры
Контейнеры-адаптеры
Псевдоконтейнеры

Контейнеры STL

Последовательные контейнеры
Ассоциативные контейнеры
Контейнеры-адаптеры
Псевдоконтейнеры

Последовательные контейнеры STL

std::vector
std::list
std::deque

Ассоциативные контейнеры STL

std::set
std::map
std::multiset
std::multimap

Красно-черные деревья

Красно-черные деревья

Красно-черные деревья

http://www.youtube.com/v/vDHFF4wjWYU

B-деревья

https://code.google.com/p/cpp-btree/

B-деревья

btree_set
btree_map
btree_multiset
btree_multimap

Контейнеры-адаптеры STL

std::stack
std::queue
std::priority_queue

Псевдоконтейнеры STL

std::bitset
std::basic_string
std::valarray

Последовательные контейнеры STL (C++11)

std::array
std::forward_list

std::array vs. std::vector

std::vector хранит все элементы в куче
std::array хранит все элементы

std::forward_list

Итератор может двигаться только в одном направлении.

#include
#include
int main ()
{

Хэш-таблицы STL (C++11)

std::unordered_set
std::unordered_map
std::unordered_multiset
std::unordered_multimap

Хэш-таблицы STL (C++11)

Хэш-таблицы STL (C++11)

boost::circular_buffer

boost::circular_buffer_space_optimized

Умные указатели

Умные указатели

Пример «самодельного» умного указателя.

class PFoo {
private:
Foo* foo;

Умные указатели

Пример «самодельного» умного указателя.

template
class SP {
private:

std::auto_ptr (C++03)

std::auto_ptr (C++03)

Не использовать!

std::auto_ptr (C++03)

#include
int func()
{
std::auto_ptr PFoo1(new CFoo());
std::auto_ptr PFoo2;
PFoo2 = PFoo1;
}

Пример некорректного использования

std::unique_ptr (C++11)

Невозможность скопировать std::unique_ptr

#include
int func()
{
std::unique_ptr PFoo1(new CFoo());
std::unique_ptr PFoo2;
PFoo2 = PFoo1;

std::unique_ptr (C++11)

Перемещение std::unique_ptr

#include
int func()
{
std::unique_ptr PFoo1(new CFoo());
std::unique_ptr PFoo2;
PFoo2 = std::move(PFoo1);
}

std::shared_ptr (C++11)

Пример использования std::shared_ptr

#include
int func()
{
std::shared_ptr PFoo1(new CFoo());
std::shared_ptr PFoo2;
PFoo2 = PFoo1;
}

std::shared_ptr (C++11)

std::shared_ptr (C++11)

std::weak_ptr (C++11)

Аллокаторы

Аллокаторы

Аллокаторы

Аллокаторы

Аллокаторы

Аллокаторы

Аллокаторы

Аллокаторы

Аллокаторы

Аллокаторы

Аллокаторы

Аллокаторы

Аллокаторы

malloc/calloc/realloc/free
new/delete
new[]/delete[]

Аллокаторы

ccmalloc
dmalloc
tcmalloc

ccmalloc

Делаем утечки.

void Leak(char *inStr)
{
char *str = (char *) malloc(strlen(inStr));
memcpy(str,

ccmalloc

Функция main с утечками.

int main()
{
char *str;
Leak("This leaks 19 bytes");

ccmalloc

Результат ccmalloc (1).

* 61.3% = 19 Bytes of garbage allocated in

ccmalloc

Результат ccmalloc (2).

|
* 38.7% = 12 Bytes of garbage allocated

dmalloc

Результат dmalloc.

not freed: '0x45008' (12 bytes) from 'ra=0x1f8f4'
not freed: '0x45028' (12

tcmalloc

Работает быстрее, чем malloc из glibc
LD_PRELOAD="/usr/lib/libtcmalloc.so"

Уплотнение памяти

Уплотнение памяти

Уплотнение памяти

Уплотнение памяти

Алгоритм Бейкера

Уплотнение на месте

Разобраться самостоятельно

git
make