Containers
A container is a holder object that stores a collection of other objects (its elements). They are implemented as class templates, which allows a great flexibility in the types supported as elements.
The container manages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference objects with similar properties to pointers).
Containers replicate structures very commonly used in programming: dynamic arrays (vector), queues (queue), stacks (stack), heaps (priority_queue), linked lists (list), trees (set), associative arrays (map).
Many containers have several member functions in common, and share functionalities. The decision of which type of container to use for a specific need does not generally depend only on the functionality offered by the container, but also on the efficiency of some of its members (complexity). This is especially true for sequence containers, which offer different trade-offs in complexity between inserting/removing elements and accessing them.
stack, queue and priority_queue are implemented as container adaptors. Container adaptors are not full container classes, but classes that provide a specific interface relying on an object of one of the container classes (such as deque or list) to handle the elements. The underlying container is encapsulated in such a way that its elements are accessed by the members of the container adaptor independently of the underlying container class used.
Container class templates
Sequence containers:
array Array class (class template) vector Vector (class template) deque Double ended queue (class template) forward_list Forward list (class template) list List (class template)
Container adaptors:
stack LIFO stack (class template) queue FIFO queue (class template) priority_queue Priority queue (class template)
Associative containers:
set Set (class template) multiset Multiple-key set (class template) map Map (class template) multimap Multiple-key map (class template)
Unordered associative containers:
unordered_set Unordered Set (class template) unordered_multiset Unordered Multiset (class template) unordered_map Unordered Map (class template) unordered_multimap Unordered Multimap (class template)
Other:
Two class templates share certain properties with containers, and are sometimes classified with them: bitset and valarray .
Member map
This is a comparison chart with the different member functions present on each of the different containers:
Legend:
| C++98 | Available since C++98 |
|---|---|
| C++11 | New in C++11 |
Sequence containers
| Headers | ||||||||
| Members | array | vector | deque | forward_list | list | |||
| constructor | implicit | vector | deque | forward_list | list | |||
| destructor | implicit | ~vector | ~deque | ~forward_list | ~list | |||
| operator= | implicit | iterators | begin | begin | begin | begin | begin before_begin | begin |
| end | end | end | end | end | end | |||
| rbegin | rbegin | rbegin | rbegin | rbegin | ||||
| rend | rend | rend | rend | rend | ||||
| const iterators | cbegin | cbegin | cbegin | cbegin | cbegin cbefore_begin | cbegin | ||
| cend | cend | cend | cend | cend | cend | |||
| crbegin | crbegin | crbegin | crbegin | crbegin | ||||
| crend | crend | crend | crend | crend | ||||
| capacity | size | size | size | size | size | |||
| max_size | max_size | max_size | max_size | max_size | max_size | |||
| empty | empty | empty | empty | empty | empty | |||
| resize | resize | resize | resize | resize | ||||
| shrink_to_fit | shrink_to_fit | shrink_to_fit | ||||||
| capacity | capacity | |||||||
| reserve | reserve | |||||||
| element access | front | front | front | front | front | front | ||
| back | back | back | back | back | ||||
| operator[] | operator[] | operator[] | operator[] | |||||
| at | at | at | at | |||||
| modifiers | assign | assign | assign | assign | assign | |||
| emplace | emplace | emplace | emplace_after | emplace | ||||
| insert | insert | insert | insert_after | insert | ||||
| erase | erase | erase | erase_after | erase | ||||
| emplace_back | emplace_back | emplace_back | emplace_back | |||||
| push_back | push_back | push_back | push_back | |||||
| pop_back | pop_back | pop_back | pop_back | |||||
| emplace_front | emplace_front | emplace_front | emplace_front | |||||
| push_front | push_front | push_front | push_front | |||||
| pop_front | pop_front | pop_front | pop_front | |||||
| clear | clear | clear | clear | clear | ||||
| swap | swap | swap | swap | swap | swap | |||
| list operations | splice | splice_after | splice | |||||
| remove | remove | remove | ||||||
| remove_if | remove_if | remove_if | ||||||
| unique | unique | unique | ||||||
| merge | merge | merge | ||||||
| sort | sort | sort | ||||||
| reverse | reverse | reverse | ||||||
| observers | get_allocator | get_allocator | get_allocator | get_allocator | get_allocator | |||
| data | data | data | ||||||
Associative containers
| Headers | ||||||||||
| Members | set | multiset | map | multimap | unordered_set | unordered_multiset | unordered_map | unordered_multimap | ||
| constructor | set | multiset | map | multimap | unordered_set | unordered_multiset | unordered_map | unordered_multimap | ||
| destructor | ~set | ~multiset | ~map | ~multimap | ~unordered_set | ~unordered_multiset | ~unordered_map | ~unordered_multimap | ||
| assignment | iterators | begin | begin | begin | begin | begin | begin | begin | begin | begin |
| end | end | end | end | end | end | end | end | end | ||
| rbegin | rbegin | rbegin | rbegin | rbegin | ||||||
| rend | rend | rend | rend | rend | ||||||
| const iterators | cbegin | cbegin | cbegin | cbegin | cbegin | cbegin | cbegin | cbegin | cbegin | |
| cend | cend | cend | cend | cend | cend | cend | cend | cend | ||
| crbegin | crbegin | crbegin | crbegin | crbegin | ||||||
| crend | crend | crend | crend | crend | ||||||
| capacity | size | size | size | size | size | size | size | size | size | |
| max_size | max_size | max_size | max_size | max_size | max_size | max_size | max_size | max_size | ||
| empty | empty | empty | empty | empty | empty | empty | empty | empty | ||
| reserve | reserve | reserve | reserve | reserve | ||||||
| element access | at | at | at | |||||||
| operator[] | operator[] | operator[] | ||||||||
| modifiers | emplace | emplace | emplace | emplace | emplace | emplace | emplace | emplace | emplace | |
| emplace_hint | emplace_hint | emplace_hint | emplace_hint | emplace_hint | emplace_hint | emplace_hint | emplace_hint | emplace_hint | ||
| insert | insert | insert | insert | insert | insert | insert | insert | insert | ||
| erase | erase | erase | erase | erase | erase | erase | erase | erase | ||
| clear | clear | clear | clear | clear | clear | clear | clear | clear | ||
| swap | swap | swap | swap | swap | swap | swap | swap | swap | ||
| operations | count | count | count | count | count | count | count | count | count | |
| find | find | find | find | find | find | find | find | find | ||
| equal_range | equal_range | equal_range | equal_range | equal_range | equal_range | equal_range | equal_range | equal_range | ||
| lower_bound | lower_bound | lower_bound | lower_bound | lower_bound | ||||||
| upper_bound | upper_bound | upper_bound | upper_bound | upper_bound | ||||||
| observers | get_allocator | get_allocator | get_allocator | get_allocator | get_allocator | get_allocator | get_allocator | get_allocator | get_allocator | |
| key_comp | key_comp | key_comp | key_comp | key_comp | ||||||
| value_comp | value_comp | value_comp | value_comp | value_comp | ||||||
| key_eq | key_eq | key_eq | key_eq | key_eq | ||||||
| hash_function | hash_function | hash_function | hash_function | hash_function | ||||||
| buckets | bucket | bucket | bucket | bucket | bucket | |||||
| bucket_count | bucket_count | bucket_count | bucket_count | bucket_count | ||||||
| bucket_size | bucket_size | bucket_size | bucket_size | bucket_size | ||||||
| max_bucket_count | max_bucket_count | max_bucket_count | max_bucket_count | max_bucket_count | ||||||
| hash policy | rehash | rehash | rehash | rehash | rehash | |||||
| load_factor | load_factor | load_factor | load_factor | load_factor | ||||||
| max_load_factor | max_load_factor | max_load_factor | max_load_factor | max_load_factor | ||||||
STL для новичков. Реализация класса-контейнера
Привет Хабр, наверное все, кто изучает С++ хотят разобраться как реализованы и как работают классы-контейнеры из стандартной библиотеки. Как по мне, чтобы лучше освоить нечто похожее на контейнеры, то надо попробовать реализовать один из контейнеров самому. В этой статье я хочу показать вам хотя бы примерно как реализуются классы-контейнеры на примере списка. Хочу сразу сказать, что это не будет копирование всего функционала, а будет показана только концепция работы контейнера, а именно реализуем класс списка и класс итератора для работы с ним.
Статья будет интересна только новичкам, которые начинают изучать стандартную библиотеку, профессионалы не найдут здесь для себя ничего новго.
Ну что ж, начнем. Что собой представляет list из стандартной библиотеки? Это последовательный контейнер, который оптимизирован для вставки и удаления элементов. Для работы с этим контейнером в STL используется двунаправленный итератор, который мы попробуем реализовать. Также мы реализуем функцию вставки на начало и в конец списка, вставку после элемента на который указывает iterator, удаление элементов и еще несколько функций.
А сейчас будет много кода с комментариями.
файл «dlist.h»
#ifndef DLIST_H_ #define DLIST_H_ #include template class Double_list < public: class iterator; friend class iterator; //класс итератора должен иметь доступ к полям класса Double_list private: class Double_node; friend class Double_node; class Double_node // < public: friend class Double_list; friend class iterator; //Создать вузол с какимто значением типа T Double_node(T node_val): val(node_val) <> Double_node() <> ~Double_node() <> void print_val() Double_node *next; //указывает на следующий узел списка Double_node *prev; //указывает на предыдущий узел. T val; //данные. >; public: class iterator < friend class Double_list; public: // нулевой конструкрор iterator() :the_node(0) <> //здесь мы создаем итератор с указателя на узел Double_node iterator(Double_node *dn): the_node(dn) <> //конструктор копии iterator(const iterator &it): the_node(it.the_node) <> iterator& operator=(const iterator &it) < the_node = it.the_node; return *this; >// в этом классе оператор == означает, что два итератора указывают на // один и тот же узел bool operator == (const iterator &it) const < return (the_node == it.the_node); >bool operator!=(const iterator &it) const < return !(it == *this); >//переводит итератор на следующий узел списка. iterator& operator++() < if (the_node == 0) throw "incremented an empty iterator"; if (the_node->next == 0) throw "tried to increment too far past the end"; the_node = the_node->next; return *this; > //переводит итератор на предідущий узел списка. iterator & operator--() < if (the_node == 0) throw "decremented an empty iterator"; if (the_node->prev == 0) throw "tried to decrement past the beginning"; the_node = the_node->prev; return *this; > //Возвращает значение данных. T& operator*() const < if (the_node == 0) throw "tried to dereference an empty iterator"; return the_node->val; > private: Double_node *the_node; >; private: Double_node *head; //указывает на начало списка. Double_node *tail; //указывает на елемент, который идет за последним iterator head_iterator; //итератор, который всегда указывает на начало списка iterator tail_iterator; //итератор, который всегда указывает на элемент, который находится за последним. public: Double_list() < head = tail = new Double_node; tail->next = nullptr; tail->prev = nullptr; //инициализирует итераторы head_iterator = iterator(head); tail_iterator = iterator(tail); > //Создать список, который содержит один элемент. Double_list(T node_val) < head = tail = new Double_node; tail->next = nullptr; tail->prev = 0; head_iterator = iterator(head); tail_iterator = iterator(tail); add_front(node_val); > ~Double_list() < Double_node *node_to_delete = head; for (Double_node *sn = head; sn != tail;) < sn = sn->next; delete node_to_delete; node_to_delete = sn; > delete node_to_delete; > bool is_empty() iterator front() iterator rear() //вставляем узел в начало списка void add_front(T node_val) < Double_node *node_to_add = new Double_node (node_val); node_to_add->next = head; node_to_add->prev = nullptr; head->prev = node_to_add; head = node_to_add; //так как head изменился, нужно изменить head_iterator head_iterator= iterator(head); > //вставляем узел в конец списка void add_rear(T node_val) < if (is_empty()) add_front(node_val); else < Double_node *node_to_add = new Double_node(node_val); node_to_add->next = tail; node_to_add->prev = tail->prev; tail->prev->next = node_to_add; tail->prev = node_to_add; //изменяем tail_iterator tail_iterator = iterator(tail); > > //вставляет в спсиок node_val после итератора key_i bool insert_after(T node_val, const iterator &key_i) < for (Double_node *dn = head; dn != tail; dn = dn->next) < //Найден ли узел для заданного итератора if (dn == key_i.the_node) < Double_node *node_to_add = new Double_node(node_val); node_to_add->prev = dn; node_to_add->next = dn->next; dn->next->prev = node_to_add; dn->next = node_to_add; return true; > > return false; > //Удалить первый элемент списка. T remove_front() < if (is_empty()) throw "tried to remove from an empty list"; Double_node *node_to_remove = head; T return_val = node_to_remove->val; head = node_to_remove->next; head->prev = 0; head_iterator = iterator(head); delete node_to_remove; return return_val; > T remove_rear() < if (is_empty()) throw "tried to remove from an empty list"; Double_node *node_to_remove = tail->prev; if(node_to_remove->prev == 0) < return remove_front(); >else < T return_val = node_to_remove->val; node_to_remove->prev->next = tail; tail->prev = node_to_remove->prev; delete node_to_remove; return return_val; > > bool remove_it(iterator &key_i) < for (Double_node *dn = head; dn != tail; dn = dn-next) < //Найден ли узел для заданного итератора if (dn == key+i.the_node) < dn->prev->next = dn->next; dn->next->prev = dn->prev; delete dn; key_i.the_node =0; return true; > > return false; > //Возвращает первый итератор, указывающий на node_val iterator find(T node_val) const < for (double_node *dn = head; dn != tail; dn = dn->next) < if (dn->val == node_val) return iterator(dn); > //Если node_val нет в списке возвращает tail_iterator return tail_iterator; > //возвращает итератор, который указывает на n-ый элемент списка iterator get_nth(const int element_num) const < if (element_num < 1) return tail_iterator; int count = 1; for(Double_node *dn = head; dn != tail; dn = dn->next) < if (count++ == element_num) return iterator(dn); >return tail_iterator; > //Количество узлов в списке. int size() const < int count = 0; for (Double_node *dn = head; dn != tail; dn = dn->next) ++count; return count; > void print() const < for (Double_node *dn = head; dn!= tail; dn = dn->next) < dn->print_val(); > std::cout >; #endif #include "dlist.h" int main() < Double_listthe_list; Double_list::iterator list_iter; for (int i=0; i the_list.print(); the_list.remove_front(); for (list_iter = the_list.front(); list_iter != the_list.rear(); ++ list_iter) < std::cout std::cout << std:: endl; //выводим в обратном порядке for (list_iter = the_list.rear(); list_iter != the_list.front();) < --list_iter; std::cout std::cout
Анализ кода
Итератор реализован как открытый вложенный класс. Так как класс открытый, пользователи могут создавать объекты. Класс iterator должен знать о некоторых закрытых элементах класса Double_list, поэтому мы объявляем класс iterator дружественным к классу Double_list и так же в классе iterator объявляем другом класс Double_list.
Теперь посмотрим на внутреннее устройство класса Double_list::iterator. У него есть единственный элемент данных: Double_node* the_node. Именно это итератор и должен скрывать. Операции, объявляемые в классе iterator, позволяют пользователям манипулировать этим узлом определенным образом.
Конец
Вот на этом и все. Примерно так реализован класс списка в библиотеке STL. Конечно, наш класс очень общий пример, в STL все сложнее, но общий принцип с этого кода понять можно.