Этот сайт использует cookies. Продолжение работы с сайтом означает, что Вы согласны!
Динамические массивы
В предыдущей главе мы научились создавать пользовательские шаблонные классы. Даже если вы не будете создавать свои шаблонные классы, то уж с вероятностью 100% будете пользоваться готовыми шаблонными классами, входящими в состав стандартной библиотеки шаблонов (STL — Standard Template Library), которые реализуют различные структуры данных: динамические массивы, списки, очереди, словари, множества и др. Очень уж они удобны в использовании и полезны в большинстве случаев. STL является неотъемлемой частью стандартной библиотеки языка C++, поэтому ничего дополнительно устанавливать не придется.
Ранее мы рассматривали классы string
и wstring
, которые являются спецификациями шаблонного класса basic_string
. Этот класс хотя и не является частью STL, но полностью совместим с этой библиотекой. Таким образом к классам string
и wstring
можно применять алгоритмы, имеющиеся в STL. Кроме того, объекты этих классов можно сохранить в других контейнерах.
В STL контейнеры делятся на три основных типа:
- последовательные контейнеры. К этому типу относятся классы
deque
(двусторонняя очередь),list
(двусвязный список) иvector
(динамический массив); - ассоциативные контейнеры. К этому типу относятся классы
map
(ассоциативный массив, в котором каждому ключу соответствует одно значение),multimap
(ассоциативный массив, в котором ключу может соответствовать несколько значений),set
(множество, состоящее из уникальных элементов) иmultiset
(множество, в котором элементы могут повторяться); - контейнеры-адаптеры. К этому типу относятся классы
priority_queue
(очередь с приоритетами),queue
(очередь) иstack
(стек). Обратите внимание на то, что контейнеры-адаптеры не позволяют использовать итераторы.
Почти все контейнеры являются динамическими. Это означает, что при добавлении нового элемента следить за размерами контейнера нет необходимости. Управление динамической памятью осуществляется автоматически с помощью распределителя памяти, который реализуется классом allocator
. При создании объектов контейнера можно указать экземпляр класса, который реализует пользовательский распределитель памяти. Получить доступ к распределителю памяти через объект контейнера позволяет метод get_allocator()
. Т. к. в большинстве случаев достаточно возможностей встроенного распределителя памяти мы не станем создавать собственные классы, а также рассматривать класс allocator
. Чтобы получить подробные сведения по этим вопросам обращайтесь к документации.
Вспомогательные средства
Прежде чем изучать структуры данных, вначале рассмотрим вспомогательные средства: итераторы, функторы, инверторы, редакторы связей и адаптеры, а затем перейдем к контейнерам и алгоритмам.
Итераторы
Итератор — это объект, выполняющий в контейнере роль указателя. С помощью итератора можно перемещаться внутри контейнера и получать доступ к отдельным элементам. В STL определены следующие типы итераторов:
iterator
— обычный итератор. При увеличении значения итератор перемещается к концу контейнера. Пример объявления переменной:
std::vector<int>::iterator it;
const_iterator
— константный итератор. Изменить значение, на которое ссылается итератор, нельзя. Пример объявления переменной:
std::vector<int>::const_iterator it;
reverse_iterator
— обратный итератор. При увеличении значения итератор перемещается к началу контейнера. Пример объявления переменной:
std::vector<int>::reverse_iterator it;
const_reverse_iterator
— константный обратный итератор. Изменить значение, на которое ссылается итератор, нельзя. Пример объявления переменной:
std::vector<int>::const_reverse_iterator it;
Присвоить значения переменным позволяют следующие методы:
begin()
— возвращает обычный итератор, установленный на первый элемент контейнера. Прототипы метода:
iterator begin() noexcept;
const_iterator begin() const noexcept;
Выведем значение первого элемента:
std::vector<int> arr = {1, 2, 3};
std::vector<int>::iterator it;
it = arr.begin();
std::cout << *it << std::endl; // 1
Вместо метода begin()
можно воспользоваться шаблонной функцией begin()
:
std::vector<int> arr = {1, 2, 3};
std::vector<int>::iterator it = std::begin(arr);
std::cout << *it << std::endl; // 1
end()
— возвращает обычный итератор, установленный на позицию после последнего элемента контейнера. Прототипы метода:
iterator end() noexcept;
const_iterator end() const noexcept;
Выведем значение последнего элемента:
std::vector<int> arr = {1, 2, 3};
std::vector<int>::iterator it;
it = arr.end();
std::cout << *(--it) << std::endl; // 3
Вместо метода end()
можно воспользоваться шаблонной функцией end()
:
std::vector<int> arr = {1, 2, 3};
std::vector<int>::iterator it = std::end(arr);
std::cout << *(--it) << std::endl; // 3
cbegin()
— возвращает константный итератор, установленный на первый элемент контейнера. Прототип метода:
const_iterator cbegin() const noexcept;
cend()
— возвращает константный итератор, установленный на позицию после последнего элемента контейнера. Прототип метода:
const_iterator cend() const noexcept;
rbegin()
— возвращает обратный итератор, установленный на последний элемент контейнера. Прототипы метода:
reverse_iterator rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;
Выведем значение последнего элемента:
std::vector<int> arr = {1, 2, 3};
std::vector<int>::reverse_iterator it;
it = arr.rbegin();
std::cout << *it << std::endl; // 3
rend()
— возвращает обратный итератор, установленный на позицию перед первым элементом контейнера. Прототипы метода:
reverse_iterator rend() noexcept;
const_reverse_iterator rend() const noexcept;
Выведем значение первого элемента:
std::vector<int> arr = {1, 2, 3};
std::vector<int>::reverse_iterator it;
it = arr.rend();
std::cout << *(--it) << std::endl; // 1
crbegin()
— возвращает константный обратный итератор, установленный на последний элемент контейнера. Прототип метода:
const_reverse_iterator crbegin() const noexcept;
crend()
— возвращает константный обратный итератор, установленный на позицию перед первым элементом контейнера. Прототип метода:
const_reverse_iterator crend() const noexcept;
Для работы с итераторами предназначены следующие функции:
begin()
— возвращает обычный итератор, установленный на первый элемент контейнера. Прототипы функции:
template<typename _Container>
auto begin(_Container &cont) -> decltype(cont.begin());
template<typename _Container>
auto begin(const _Container &cont) -> decltype(cont.begin());
template<typename _Tp, size_t _Nm>
_Tp *begin(_Tp (&arr)[_Nm]);
Выведем значение первого элемента:
std::vector<int> arr = {1, 2, 3};
std::vector<int>::iterator it = std::begin(arr);
std::cout << *it << std::endl; // 1
Третий прототип можно использовать с обычными массивами:
int arr[3] = {1, 2, 3};
auto it = std::begin(arr);
std::cout << *it << std::endl; // 1
end()
— возвращает обычный итератор, установленный на позицию после последнего элемента контейнера. Прототипы функции:
template<typename _Container>
auto end(_Container &cont) -> decltype(cont.end());
template<typename _Container>
auto end(const _Container &cont) -> decltype(cont.end());
template<typename _Tp, size_t _Nm>
_Tp *end(_Tp (&arr)[_Nm]);
Выведем значение последнего элемента:
std::vector<int> arr = {1, 2, 3};
std::vector<int>::iterator it = std::end(arr);
std::cout << *(--it) << std::endl; // 3
Третий прототип можно использовать с обычными массивами:
int arr[3] = {1, 2, 3};
auto it = std::end(arr);
std::cout << *(--it) << std::endl; // 3
cbegin()
— возвращает константный итератор, установленный на первый элемент контейнера. Функция доступна, начиная со стандарта C++14. Прототип функции:
template<typename _Container>
constexpr auto cbegin(const _Container &cont) ->
decltype(std::begin(cont));
cend()
— возвращает константный итератор, установленный на позицию после последнего элемента контейнера. Функция доступна, начиная со стандарта C++14. Прототип функции:
template<typename _Container>
constexpr auto cend(const _Container &cont) ->
decltype(std::end(cont));
rbegin()
— возвращает обратный итератор, установленный на последний элемент контейнера. Функция доступна, начиная со стандарта C++14. Прототипы функции:
template<typename _Container>
auto rbegin(_Container &cont) -> decltype(cont.rbegin());
template<typename _Container>
auto rbegin(const _Container &cont) ->
decltype(cont.rbegin());
template<typename _Tp, size_t _Nm>
reverse_iterator<_Tp*> rbegin(_Tp (&arr)[_Nm]);
Выведем значение последнего элемента:
std::vector<int> arr = {1, 2, 3};
auto it = std::rbegin(arr);
std::cout << *it << std::endl; // 3
rend()
— возвращает обратный итератор, установленный на позицию перед первым элементом контейнера. Функция доступна, начиная со стандарта C++14. Прототипы функции:
template<typename _Container>
auto rend(_Container &cont) -> decltype(cont.rend());
template<typename _Container>
auto rend(const _Container &cont) -> decltype(cont.rend());
template<typename _Tp, size_t _Nm>
reverse_iterator<_Tp*> rend(_Tp (&arr)[_Nm]);
Выведем значение первого элемента обычного массива:
int arr[3] = {1, 2, 3};
auto it = std::rend(arr);
std::cout << *(--it) << std::endl; // 1
crbegin()
— возвращает константный обратный итератор, установленный на последний элемент контейнера. Функция доступна, начиная со стандарта C++14. Прототип функции:
template<typename _Container>
auto crbegin(const _Container &cont) ->
decltype(std::rbegin(cont));
crend()
— возвращает константный обратный итератор, установленный на позицию перед первым элементом контейнера. Функция доступна, начиная со стандарта C++14. Прототип функции:
template<typename _Container>
auto crend(const _Container &cont) ->
decltype(std::rend(cont));
prev()
— возвращает итератор, ссылающийся на предыдущий элемент. Смещение предыдущего элемента можно указать в параметреn
. Прототип функции:
template<typename _BiIterator>
_BiIterator prev(_BiIterator it,
typename iterator_traits<_BiIterator>::difference_type n=1);
Пример:
std::vector<int> arr = {1, 2, 3};
auto it = std::end(arr);
std::cout << *std::prev(it) << std::endl; // 3
std::cout << *std::prev(it, 2) << std::endl; // 2
std::cout << *std::prev(it, 3) << std::endl; // 1
next()
— возвращает итератор, ссылающийся на следующий элемент. Смещение следующего элемента можно указать в параметреn
. Прототип функции:
template<typename _InputIterator>
_InputIterator next(_InputIterator it,
typename iterator_traits<_InputIterator>::difference_type n=1);
Пример:
std::vector<int> arr = {1, 2, 3};
auto it = std::begin(arr);
std::cout << *it << std::endl; // 1
std::cout << *std::next(it) << std::endl; // 2
std::cout << *std::next(it, 2) << std::endl; // 3
advance()
— перемещает итераторit
наn
позиций. Для перемещения в обратном направлении нужно указать отрицательное значение. Прототип функции:
template<typename _InputIterator, typename _Distance>
void advance(_InputIterator &it, _Distance n);
Пример:
std::vector<int> arr = {1, 2, 3};
auto it = std::begin(arr);
std::cout << *it << std::endl; // 1
std::advance(it, 2);
std::cout << *it << std::endl; // 3
std::advance(it, -1);
std::cout << *it << std::endl; // 2
distance()
— возвращает количество элементов между двумя итераторами. Прототип функции:
template<typename _InputIterator>
typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator first, _InputIterator last);
Получим количество элементов динамического массива:
std::vector<int> arr = {1, 2, 3};
std::cout << std::distance(arr.begin(), arr.end())
<< std::endl; // 3
С итераторами можно производить такие же операции, как и с указателями. Чтобы получить или изменить значение, на которое ссылается итератор, перед названием переменной указывается оператор *
(*it
). Перемещение итератора осуществляется с помощью операторов +
, -
, ++
и --
. Кроме того, итераторы можно сравнивать с помощью операторов сравнения. В качестве примера изменим значение первого элемента, а затем выведем все элементы динамического массива в прямом и обратном порядке с помощью цикла for
(листинг 16.1).
Листинг 16.1. Перебор элементов с помощью итераторов
#include <iostream>
#include <vector>
int main() {
std::vector<int> arr;
std::vector<int>::iterator it1, it2;
std::vector<int>::reverse_iterator it3, it4;
// Добавляем элементы
for (int i = 1; i <= 10; ++i) arr.push_back(i);
it1 = arr.begin();
*it1 = 800; // Изменение значения
// Перебор элементов в прямом порядке
for (it1 = arr.begin(), it2 = arr.end(); it1 != it2; ++it1) {
std::cout << *it1 << std::endl;
}
std::cout << "------------------" << std::endl;
// Перебор элементов в обратном порядке
for (it3 = arr.rbegin(), it4 = arr.rend(); it3 != it4; ++it3) {
std::cout << *it3 << std::endl;
}
return 0;
}
Реквизиты
ЮMoney (Yandex-деньги): 410011140483022
ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов