cpp

Динамические массивы

В предыдущей главе мы научились создавать пользовательские шаблонные классы. Даже если вы не будете создавать свои шаблонные классы, то уж с вероятностью 100% будете пользоваться готовыми шаблонными классами, входящими в состав стандартной библиотеки шаблонов (STLStandard 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;
}

Учебник C++ (Qt Creator и MinGW)
Учебник C++ (Qt Creator и MinGW) в формате PDF

Реквизиты

ЮMoney (Yandex-деньги): 410011140483022

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов

cpp