Класс forward_list: односвязный список

Класс forward_list реализует односвязный список, элементы которого хранят указатель только на следующий элемент (в списках класса list элементы хранят указатели и на предыдущий, и на последующий элементы). Вставка и удаление элементов происходит быстро, достаточно изменить ссылку, но получить доступ к элементу списка по индексу нельзя, т. к. элементы могут быть расположены в разных местах памяти. Перебирать элементы можно только в прямом направлении: от первого элемента до последнего (в списках класса list элементы можно перебирать в обоих направлениях). В некоторых случаях списки класса forward_list могут быть эффективнее списков класса list, но они менее универсальны. Прежде чем использовать класс, необходимо в начало программы добавить инструкцию:

#include <forward_list>

Создание объекта

Объявление класса forward_list:

template<typename _Tp, typename _Alloc = allocator<_Tp> >
   class forward_list : private _Fwd_list_base<_Tp, _Alloc>;

Создать экземпляр класса forward_list можно следующими способами (полный список конструкторов смотрите в документации):

  • объявить переменную без инициализации. Для этого перед названием переменной указывается название класса, а после названия внутри угловых скобок задается тип данных. В этом случае список не содержит элементов. Пример объявления без инициализации:
std::forward_list<int> arr;
  • указать внутри круглых скобок количество элементов. Пример:
std::forward_list<int> arr(5);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 0 0 0 0 0

Все элементы будут иметь значения по умолчанию для типа. Например, для типа int все элементы будут содержать значение 0. Указать другое значение можно во втором параметре. Пример создания списка из 5 элементов со значением 1:

std::forward_list<int> arr(5, 1);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 1 1 1 1
  • перечислить значения через запятую внутри фигурных скобок:
std::forward_list<int> arr1{1, 2, 3};
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
std::forward_list<int> arr2 = {4, 5, 6};
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 4 5 6
  • указать объект класса forward_list внутри круглых скобок или после оператора = (доступны конструкторы копирования и перемещения):
std::forward_list<int> arr1 = {1, 2, 3};
// Создание копии
std::forward_list<int> arr2(arr1);
arr2.front() = 55;
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 55 2 3
// Перемещение элементов
std::forward_list<int> arr3(std::move(arr1));
for (int &el : arr3) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
// В классе forward_list нет метода size() !!!
std::cout << std::distance(arr1.begin(), arr1.end())
          << std::endl; // 0
  • указать диапазон внутри контейнера с помощью итераторов. В первом параметре передается итератор, указывающий на начало диапазона, а во втором параметре — итератор, указывающий на конец диапазона:
std::forward_list<int> arr1 = {1, 2, 3};
std::forward_list<int> arr2(arr1.begin(), arr1.end());
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Вместо итератора можно передать указатель. Создадим список, содержащий копии элементов из обычного массива:

const int ARR_SIZE = 3;
int arr[ARR_SIZE] = {1, 2, 3};
std::forward_list<int> arr2(arr, arr + ARR_SIZE);
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Над двумя объектами класса forward_list определены операции ==, !=, <, <=, > и >=. Пример сравнения двух объектов:

std::forward_list<int> arr1 = {1, 2, 3};
std::forward_list<int> arr2(arr1.begin(), arr1.end());
if (arr1 == arr2) {
   std::cout << "arr1 == arr2" << std::endl;
}

Кроме того, один объект можно присвоить другому объекту. В этом случае выполняется поэлементное копирование (оператор копирования) или перемещение элементов (оператор перемещения). Пример:

std::forward_list<int> arr1 = {1, 2, 3}, arr2, arr3;
// Создание копии
arr2 = arr1;
arr2.front() = 55;
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 55 2 3
// Перемещение элементов
arr3 = std::move(arr1);
for (int &el : arr3) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
std::cout << std::distance(arr1.begin(), arr1.end())
          << std::endl; // 0

Доступно также присваивание элементов из списка инициализации:

std::forward_list<int> arr;
arr = {1, 2, 3};
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Вместо оператора = для присваивания значения можно воспользоваться методом assign(). Прототипы метода:

void assign(size_type count, const value_type &val);
template<typename _InputIterator>
   void assign(_InputIterator first, _InputIterator last);
void assign(initializer_list<value_type> list);

Первый прототип удаляет существующие элементы, а затем вставляет count элементов val. Второй прототип удаляет существующие элементы, а затем вставляет элементы из диапазона, ограниченного итераторами first и last. Третий прототип удаляет существующие элементы, а затем вставляет элементы из списка инициализации. Пример:

std::forward_list<int> arr1 = {1, 2, 3}, arr2 = {4, 5};
arr1.assign(3, 0);
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 0 0 0
arr1.assign(arr2.begin(), arr2.end());
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 4 5
arr1.assign({6, 7, 8});
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 6 7 8

Пример присваивания элементов из обычного массива:

const int ARR_SIZE = 3;
int arr[ARR_SIZE] = {1, 2, 3};
std::forward_list<int> arr2;
arr2.assign(arr, arr + ARR_SIZE);
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Вставка элементов

Вставить элементы позволяют следующие методы:

  • push_front() — добавляет элемент в начало списка (доступно копирование и перемещение значения):
std::forward_list<int> arr = {2, 3};
arr.push_front(1);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
  • emplace_front() — создает объект, передавая конструктору указанные через запятую значения, а затем добавляет объект в начало списка. Начиная со стандарта C++17, метод возвращает ссылку на созданный объект:
class C {
public:
   int x, y;
   C(int a, int b) : x(a), y(b) { }
};
// ... Фрагмент опущен ...
std::forward_list<C> arr;
arr.push_front(C(20, 20));
arr.emplace_front(10, 40);
for (C &el : arr) std::cout << el.x << ' ';
std::cout << std::endl;     // 10 20
  • insert_after() — вставляет один или несколько элементов после позиции pos, заданной с помощью итератора. Прототипы метода:
iterator insert_after(const_iterator pos, const value_type &val);
iterator insert_after(const_iterator pos, value_type &&val);
iterator insert_after(const_iterator pos, size_type count,
                      const value_type &val);
template<typename InputIterator>
   iterator insert_after(const_iterator pos, InputIterator first,
                         InputIterator last);
iterator insert_after(const_iterator pos,
                      initializer_list<value_type> list);

Первые два прототипа вставляют элемент после позиции pos, на которую указывает итератор и возвращают итератор, ссылающийся на вставленный элемент. Обратите внимание: итераторы односвязных списков не поддерживают операторы +, - и --, для перемещения итератора нужно использовать оператор ++ или функцию advance():

std::forward_list<int> arr = {10};
arr.insert_after(arr.before_begin(), 0); // В начало
std::forward_list<int>::iterator it = arr.begin();
std::advance(it, 1);                     // Перемещаем итератор
arr.insert_after(it, 55);                // В позицию 2
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl;                  // 0 10 55

Обратите внимание: в этом примере вместо метода begin(), мы воспользовались методом before_begin(), который возвращает итератор, ссылающийся на позицию перед первым элементом списка.

Простого способа добавить элемент в конец односвязного списка нет. Метод end() вернет итератор, ссылающийся на позицию после последнего элемента, а вернуться назад нельзя, т. к. итератор односвязного списка не поддерживает операторы - и --. Сначала придется вычислить позицию последнего элемента:

std::forward_list<int> arr = {1, 2, 3};
auto it1 = arr.begin(), it2 = arr.end();
while (std::next(it1) != it2) ++it1;
std::cout << *it1 << std::endl;          // 3
arr.insert_after(it1, 4);                // В конец списка
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl;                  // 1 2 3 4

Если нужно добавить несколько элементов в конец списка, то можно сохранить итератор, возвращаемый методом insert_after() после вставки, и использовать его для следующей операции:

std::forward_list<int> arr;
auto it = arr.before_begin();
it = arr.insert_after(it, 1);            // В начало списка
it = arr.insert_after(it, 2);            // В конец списка
arr.insert_after(it, 3);                 // В конец списка
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl;                  // 1 2 3

Третий прототип вставляет count копий элемента val после позиции pos, на которую указывает итератор:

std::forward_list<int> arr = {1, 2, 3};
arr.insert_after(arr.before_begin(), 3, 0);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 0 0 0 1 2 3

Четвертый прототип вставляет элементы из диапазона, ограниченного итераторами first и last, после позиции pos, на которую указывает итератор:

std::forward_list<int> arr1 = {1, 2, 3}, arr2 = {4, 5, 6};
arr2.insert_after(arr2.before_begin(), arr1.begin(), arr1.end());
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5 6

Пример вставки элементов из обычного массива:

int arr1[] = {1, 2, 3};
std::forward_list<int> arr2 = {4, 5, 6};
arr2.insert_after(arr2.before_begin(), arr1, arr1 + 3);
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5 6

Пятый прототип вставляет элементы из списка инициализации после позиции pos, на которую указывает итератор:

std::forward_list<int> arr = {4, 5, 6};
arr.insert_after(arr.before_begin(), {1, 2, 3});
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5 6
  • emplace() — создает объект, передавая конструктору указанные через запятую значения во втором и последующих параметрах, а затем добавляет объект после позиции, заданной в первом параметре. Метод возвращает итератор, ссылающийся на вставленный элемент. Добавим один объект в начало списка и два объекта в конец списка:
std::forward_list<C> arr;
auto it = arr.before_begin();
it = arr.emplace_after(it, 10, 20);
it = arr.emplace_after(it, 30, 40);
arr.emplace_after(it, 50, 60);
for (C &el : arr) std::cout << el.x << ' ';
std::cout << std::endl; // 10 30 50
  • swap() — меняет элементы двух списков местами:
std::forward_list<int> arr1 = {1, 2, 3}, arr2 = {4, 5, 6};
arr1.swap(arr2);
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 4 5 6
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Вместо метода swap() можно воспользоваться одноименной функцией:

std::forward_list<int> arr1 = {1, 2, 3}, arr2 = {4, 5, 6};
std::swap(arr1, arr2);
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 4 5 6
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Определение и изменение количества элементов

В классе forward_list отсутствует метод для определения количества элементов списка. Для получения количества элементов можно воспользоваться функцией distance(), которой в первом параметре передаем итератор, ссылающийся на начало списка, а во втором параметре — итератор, ссылающийся на конец списка:

std::forward_list<int> arr = {1, 2, 3};
std::cout << std::distance(arr.begin(), arr.end())
          << std::endl; // 3

Для определения и изменения количества элементов списка предназначены следующие методы:

  • empty() — возвращает значение true, если список не содержит элементов, и false — в противном случае. Прототип метода:
bool empty() const noexcept;

Пример:

std::forward_list<int> arr1 = {1, 2, 3}, arr2;
std::cout << std::boolalpha;
std::cout << arr1.empty() << std::endl; // false
std::cout << arr2.empty() << std::endl; // true
  • max_size() — возвращает максимальное количество элементов, которое теоретически может содержать список. Прототип метода:
size_type max_size() const noexcept;

Пример:

std::forward_list<int> arr = {1, 2, 3};
std::cout << arr.max_size() << std::endl;
// 1152921504606846975
  • resize() — задает количество элементов, равное числу new_size. Если указанное количество элементов меньше текущего количества, то лишние элементы будут удалены. Если количество элементов необходимо увеличить, то в параметре val можно указать значение, которое заполнит новое пространство. Прототипы метода:
void resize(size_type new_size);
void resize(size_type new_size, const value_type &val);

Пример:

std::forward_list<int> arr = {1, 2, 3};
arr.resize(2);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl;                        // 1 2
arr.resize(5, 0);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl;                        // 1 2 0 0 0

Удаление элементов

Для удаления элементов предназначены следующие методы:

  • pop_front() — удаляет первый элемент. Прототип метода:
void pop_front();

Пример:

std::forward_list<int> arr = {1, 2, 3};
arr.pop_front();
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 2 3
  • erase_after() — удаляет один элемент или элементы из диапазона. Прототипы метода:
iterator erase_after(const_iterator pos);
iterator erase_after(const_iterator before, const_iterator last);

Первый прототип удаляет один элемент, расположенный после элемента на который указывает итератор. Обратите внимание: удаляет не текущий элемент, а следующий за ним. Второй прототип удаляет элементы из диапазона, ограниченного итераторами before и last, не удаляя элементы, на которые ссылаются итераторы:

std::forward_list<int> arr = {1, 2, 3, 4, 5};
arr.erase_after(arr.begin()); // Удаляем второй элемент
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl;       // 1 3 4 5
std::forward_list<int>::iterator it1 = arr.begin();
std::forward_list<int>::iterator it2 = arr.begin();
std::advance(it1, 1);         // Перемещаем итератор
std::advance(it2, 3);         // Перемещаем итератор
arr.erase_after(it1, it2);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl;       // 1 3 5
  • clear() — удаляет все элементы. Прототип метода:
void clear() noexcept;

Пример:

std::forward_list<int> arr = {1, 2, 3, 4, 5};
arr.clear();
std::cout << std::distance(arr.begin(), arr.end())
          << std::endl; // 0
  • remove() — удаляет все элементы, имеющие значение val. Прототип метода:
void remove(const value_type &val);

Пример:

std::forward_list<int> arr = {0, 1, 1, 1, 2, 1};
arr.remove(1);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 0 2
  • remove_if() — удаляет элементы, для которых унарный функтор pred вернул значение true. Прототип метода:
template<typename _Predicate>
   void remove_if(_Predicate pred);

Удалим все элементы, значения которых меньше двух:

std::forward_list<int> arr = {0, 1, 1, 1, 2, 1, 3, 4};
arr.remove_if( [](int a){ return a < 2; } );
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 2 3 4
  • unique() — удаляет повторяющиеся элементы. Прототипы метода:
void unique();
template<typename _BinaryPredicate>
   void unique(_BinaryPredicate pred);

Первый прототип удаляет повторяющиеся элементы, расположенные рядом. Чтобы список состоял только из уникальных элементов необходимо предварительно отсортировать список. Второй прототип передает два элемента бинарному функтору. Если функтор вернет значение true, то элемент будет удален. Пример:

std::forward_list<int> arr = {0, 1, 1, 1, 2, 1, 1, 1};
arr.unique();
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 0 1 2 1
arr = {0, 1, 1, 1, 2, 1, 1, 1};
arr.unique( [](int a, int b){ return a == b; } );
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 0 1 2 1

Доступ к элементам

Для доступа к элементам списка предназначены следующие методы (обратите внимание: получить доступ к элементу списка по индексу нельзя и перебор элементов возможен только в прямом направлении):

  • front() — возвращает ссылку на первый элемент. Метод позволяет как получить значение, так и изменить его. Прототипы метода:
reference front();
const_reference front() const;

Пример:

std::forward_list<int> arr = {1, 2, 3};
arr.front() = 55;
std::cout << arr.front() << std::endl; // 55
  • before_begin() и cbefore_begin() — возвращают обычный или константный итератор ссылающийся на позицию перед первым элементом списка. Используются для вставки элементов в начало списка и удаления элементов из начала списка. Разыменовывать эти итераторы нельзя. Прототипы методов:
iterator before_begin() noexcept;
const_iterator before_begin() const noexcept;
const_iterator cbefore_begin() const noexcept;

Пример вставки элемента в начало списка:

std::forward_list<int> arr = {10};
arr.insert_after(arr.before_begin(), 0); // В начало
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl;                  // 0 10
  • begin(), end(), cbegin() и cend() — возвращают итераторы (см. разд. 16.1.1). Обратите внимание: методы rbegin(), rend(), crbegin() и crend() в других классах возвращающие обратные итераторы в классе forward_list отсутствуют. Перебирать элементы можно только в прямом направлении. Изменим и выведем значение первого элемента:
std::forward_list<int> arr = {1, 2, 3};
std::forward_list<int>::iterator it = arr.begin();
std::cout << *it << std::endl; // 1
*it = 0;
std::cout << *it << std::endl; // 0

Вместо методов begin() и end() можно воспользоваться одноименными функциями. Выведем значение первого элемента:

std::forward_list<int> arr = {1, 2, 3};
std::forward_list<int>::iterator it = std::begin(arr);
std::cout << *it << std::endl; // 1

Обратите внимание: итераторы односвязных списков не поддерживают операторы +, - и --, для перемещения итератора нужно использовать оператор ++ или функцию advance(). Пример доступа к третьему элементу списка:

std::forward_list<int> arr = {1, 2, 3, 4, 5};
std::forward_list<int>::iterator it = arr.begin();
std::advance(it, 2);
std::cout << *it << std::endl; // 3

Перебор элементов

Перебрать все элементы можно с помощью цикла for each, итераторов и алгоритма for_each(). Обратите внимание: перебор элементов возможен только в прямом направлении. Пример использования цикла for each:

std::forward_list<int> arr(3);
// Заполняем список значениями
int n = 1;
for (int &el : arr) {
   el = n++;
}
// Выводим значения
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Пример перебора элементов с помощью итераторов и цикла for:

std::forward_list<int> arr = {1, 2, 3};
std::forward_list<int>::iterator it1, it2;
for (it1 = arr.begin(), it2 = arr.end(); it1 != it2; ++it1) {
   std::cout << *it1 << ' ';
}
std::cout << std::endl; // 1 2 3

Пример перебора элементов с помощью итераторов и цикла while:

std::forward_list<int> arr = {1, 2, 3};
auto it1 = arr.begin(), it2 = arr.end();
while (it1 != it2) {
   std::cout << *it1++ << ' ';
}
std::cout << std::endl; // 1 2 3

С помощью алгоритма for_each() умножим значение каждого элемента списка на 2, а затем выведем все значения в окно консоли:

// #include <algorithm>
std::forward_list<int> arr = {1, 2, 3};
// Умножаем все элементы на 2
std::for_each( arr.begin(), arr.end(),
               [](int &a) { a *= 2; } );
// Выводим значения всех элементов
std::for_each( arr.begin(), arr.end(),
               [](int &a){ std::cout << a << ' '; } );
std::cout << std::endl; // 2 4 6

Сортировка списка

Для сортировки списка предназначен метод sort(). Прототипы метода:

void sort();
template<typename Compare> void sort(Compare comp);

Первый прототип производит сортировку по умолчанию (в пользовательских классах должен быть перегружен оператор <, иначе получите ошибку при компиляции):

std::forward_list<int> arr = {4, 5, 3, 2, 6, 1};
arr.sort(); // Сортировка в прямом порядке
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5 6

Второй прототип позволяет указать пользовательский способ сравнения элементов. Функтор comp принимает два параметра и должен возвращать значение true, если первое значение меньше второго, и false — в противном случае. Отсортируем список в прямом и обратном порядке:

std::forward_list<int> arr = {4, 5, 3, 2, 6, 1};
// Сортировка в прямом порядке
arr.sort( [](int &a, int &b) {return a < b;} );
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5 6
// Сортировка в обратном порядке
arr.sort( [](int &a, int &b) {return a > b;} );
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 6 5 4 3 2 1

Переворачивание списка

Для изменения порядка следования элементов на противоположный предназначен метод reverse(). Обратите внимание на то, что метод переворачивает список, а не сортирует его. Элементы будут следовать в обратном порядке относительно исходного списка. Прототип метода:

void reverse() noexcept;

Пример:

std::forward_list<int> arr = {4, 5, 3, 2, 6, 1};
arr.reverse();
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 6 2 3 5 4

Перенос элементов из одного списка в другой

Выполнить перенос элементов из одного списка в другой позволяет метод splice_after(). Прототипы метода:

void splice_after(const_iterator pos, forward_list &x) noexcept;
void splice_after(const_iterator pos, forward_list &&x) noexcept;
void splice_after(const_iterator pos, forward_list &x,
                  const_iterator it) noexcept;
void splice_after(const_iterator pos, forward_list &&x,
                  const_iterator it) noexcept;
void splice_after(const_iterator pos, forward_list &x,
                  const_iterator before, const_iterator last) noexcept;
void splice_after(const_iterator pos, forward_list &&x,
                  const_iterator before, const_iterator last) noexcept;

Первые два прототипа переносят все элементы из списка x в текущий список, и вставляют их после позиции pos, на которую указывает итератор. Пример переноса элементов в начало текущего списка:

std::forward_list<int> arr1 = {1, 2, 3}, arr2 = {4, 5, 6};
arr2.splice_after(arr2.before_begin(), arr1);
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl;                // 1 2 3 4 5 6
std::cout << std::distance(arr1.begin(), arr1.end())
          << std::endl; // 0

Третий и четвертый прототипы переносят один элемент следующий за элементом, на который указывает итератор it, из списка x в текущий список и вставляют его после позиции pos, на которую указывает итератор. Перенесем второй элемент из списка arr2 в начало списка arr1:

std::forward_list<int> arr1 = {1, 2, 3}, arr2 = {4, 5, 6};
arr1.splice_after(arr1.before_begin(), arr2, arr2.begin());
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl;                // 5 1 2 3
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl;                // 4 6

Пятый и шестой прототипы переносят элементы, входящие в диапазон, ограниченный итераторами before и last (не включая элементы, на которые ссылаются итераторы), из списка x в текущий список и вставляют их после позиции pos, на которую указывает итератор. Перенесем все элементы, начиная со второго, из списка arr2 в начало списка arr1:

std::forward_list<int> arr1 = {1, 2, 3}, arr2 = {4, 5, 6};
arr1.splice_after(arr1.before_begin(), arr2,
                  arr2.begin(), arr2.end());
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl;                // 5 6 1 2 3
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl;                // 4

Объединение упорядоченных списков

Метод merge() предназначен для объединения упорядоченных списков. Результатом выполнения метода является упорядоченный текущий список. Для объединения не отсортированных списков можно использовать метод splice_after() (см. разд. 17.2.9). Прототипы метода merge():

void merge(forward_list &x);
void merge(forward_list &&x);
template<typename Compare> void merge(forward_list &x, Compare comp);
template<typename Compare> void merge(forward_list &&x, Compare comp);

Первые два прототипа переносят все элементы списка x в текущий список (в пользовательских классах должен быть перегружен оператор <, иначе получите ошибку при компиляции):

std::forward_list<int> arr1 = {3, 5, 1}, arr2 = {4, 2};
arr1.sort(); // 1 3 5
arr2.sort(); // 2 4
arr1.merge(arr2);
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl;                // 1 2 3 4 5
std::cout << std::distance(arr2.begin(), arr2.end())
          << std::endl;                // 0

Третий и четвертый прототипы позволяют дополнительно указать пользовательский способ сравнения элементов. Функтор comp принимает два параметра и должен возвращать значение true, если первое значение меньше второго, и false — в противном случае. Произведем объединение списков, отсортированных в обратном порядке:

std::forward_list<int> arr1 = {3, 5, 1}, arr2 = {4, 2};
arr1.sort( [](int &a, int &b) {return a > b;} ); // 5 3 1
arr2.sort( [](int &a, int &b) {return a > b;} ); // 4 2
arr1.merge(arr2, [](int &a, int &b) {return a > b;});
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl;                // 5 4 3 2 1
std::cout << std::distance(arr2.begin(), arr2.end())
          << std::endl;                // 0

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

Помощь сайту

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

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