Разбор теста по STL (std::list)

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

Предсказуемо, проваливают чаще всего 6 вопрос — ответ на него отличается для C++11 и C++98. Причем, в новом стандарте функция стала работать хуже.

В тесте Вам предлагалось оценить корректность и вычислительную сложность 6 разных решений одной и той же задачи:

Дан список Х целых чисел и два, принадлежащих ему итератора А и Б.
Необходимо переместить элементы, расположенные между А и Б, в новый список Y.
В исходном списке N элементов, а между итераторами — M (используется при оценке вычислительной сложности).

пример 1:
Х = 1 2 3 4 5 6 7 8
      А     Б
результат:
Х = 1 6 7 8
У = 2 3 4 5

пример 3:
Х = 1 2 3 4 5 6 7 8
      А             Б
результат:
Х = 1 
У = 2 3 4 5 6 7 8

Первый вариант решения мог бы написать какой-нибудь школьник или студент-первокурсник:

list<int> first(list<int>& source, 
                list<int>::iterator& a, 
                list<int>::iterator& b) {
  list<int> result;

  if (b != source.end())
    b = next(b);

  for (auto it = a; it != b;) {
    result.push_back(*it);
    it = source.erase(it, next(it));
  }

  return result;
}

Тут создается новый (изначально пустой) список, в который последовательно добавляются элементы, размещенные между итераторами [a, b]. Из старого списка просмотренные элементы удаляются. При этом, если итератор b указывает на source.end() — то перемещать соответствующей ему элемент не нужно, иначе — выполняется сдвиг b вправо (b = next(b)). Этот код прекрасно работает за O(M), так как операции push_back и erase выполняются за O(1). Про оценку сложности алгоритмов можно подробнее прочитать в статье «Анализ сложности алгоритмов. Примеры«.

Человек, читавший «Эффективное использование STL» знает что не стоит писать вручную алгоритмы, которые уже есть в библиотеке. Цикл с операцией push_back можно заменить алгоритмом std::copy, а удалить элементы между итераторами — встроенной функцией list::erase — так мы приходим ко второму варианту решения:

list<int> second(list<int>& source,
                 list<int>::iterator& a,
                 list<int>::iterator& b) {
  list<int> result;

  if (b != source.end())
    b = next(b);

  std::copy(a, b, inserter(result, result.begin()));
  source.erase(a, b);

  return result;
}

Мы лишь отрефакторили первый вариант — это решение тоже работает. Трудоемкость используемой версии алгоритма std::copy — O(M), также как у list::erase.

Какой-нибудь программист мог бы открыть документацию и увидеть алгоритм std::remove_copy_if. О! — да он умеет что-то копировать и удалять (как раз то, что нам надо). Прочитав краткое описание он могу бы написать третий вариант решения:

list<int> third(list<int>& source, 
                list<int>::iterator& a, 
                list<int>::iterator& b) {
  list<int> result;

  if (b != source.end())
    b = next(b);

  remove_copy_if(a, b,
                 inserter(result, result.begin()),
                 [](int num) { return false; });
  return result;
}

Программист, неверное, хотел обработать элементы между нашими итераторами, при этом вставив все элементы в список result. Лямбда возвращает false, потому что копируются «все кроме тех элементов, которые удовлетворяют определенному условию». Программа будет работать некорректно, так как (вопреки нашим ожиданиям) алгоритм std::remove_copy_if ничего не удаляет из source. Начинающий программист легко ошибется. Поведение этого алгоритма почти не отличается от copy_if. Если вы задумываетесь о чистоте кода и пишите с использованием STL — то вряд-ли будете применять std::remove_copy_if. Тем не менее, исправить проблему можно явным вызовом list::erase:

list<int> fourth(list<int>& source, 
                 list<int>::iterator& a, 
                 list<int>::iterator& b) {
  list<int> result;

  if (b != source.end())
    b = next(b);

  remove_copy_if(a, b,
                 inserter(result, result.begin()),
                 [](int num) { return false; });

  source.erase(a, b);
  return result;
}

Код стал значительно сложнее, а работать программа стала медленнее — алгоритм std::copy выполняет лишь копирование, в то время как remove_copy_if — для каждого элементы дополнительно вызовет нашу лямбду.

Погодите, но нужно ведь не скопировать и удалить элементы, а переместить их — для этого существует стандартный алгоритм std::move, принимающий 3 итератора — два первых задают диапазон элементов для перемещения, а третий — начало диапазона для вставки. Зная все это программист мог бы написать такой код:

list<int> fifth(list<int>& source, 
                list<int>::iterator& a, 
                list<int>::iterator& b) {
  list<int> result;

  if (b != source.end())
    b = next(b);

  move(a, b, inserter(result, result.begin()));

  return result;
}

Код не будет работать, так как алгоритм std::move не удаляет элементы из исходного списка. Работает он почти также как std::copy, за тем исключением, что для каждого обрабатываемого элемента выполняется не копирование а «перемещение значения»:

  while (first!=last) {
    *result = std::move(*first);
    ++result; ++first;
  }

Это значит, что в новом контейнере окажутся нужные значения, но из старого они удалены не будут. При этом, в отличии от std::copy — они будут не будут скопированы, а перемещены, то есть в старом списке могут оказаться уже другие значения:

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

Более подробно про перемещение объектов можно прочитать в статье «Перемещающий конструктор и семантика перемещения«.

Таким образом, код будет работать неправильно, решить проблему можно вызовом list::erase как это было сделано в примерах выше.

Последний вариант решения — использование функции list::splice, специально созданной для нашей задачи:

list<int> sixth(list<int>& source, 
                list<int>::iterator& a, 
                list<int>::iterator& b) {
  list<int> result;

  if (b != source.end())
    b = next(b);

  result.splice(result.begin(), source, a, b);

  return result;
}

Это, безусловно, лучшее решение. Подвох заключается в том, что и эта функция работает за O(M) в С++11, но работала за O(1) в C++98. Из стандартного списка C++ сейчас действительно невозможно ни удалить кусок, ни переместить его куда-либо за O(1). Мы могли бы легко решить поставленную задачу для своего собственного двусвязного списка, описанного скажем структурой типа:

template<typename T>
struct Node {
  T value;
  Node* left;
  Node *right;
};

Достаточно изменить 4 указателя, а значит алгоритм отработает за O(1). Принцип выполнения показан на рисунке:

Однако, в стандарте С++11 было фиксировано, что трудоемкость функции size должна быть константной для любого типа контейнера. Этого нельзя добиться иначе как за счет хранения внутри списка поля-счетчика количества элементов — при добавлении одного элемента выполняется его инкремент, а удалении — декремент. Однако, оказалось что теперь нет способа реализовать функцию splice, работающую за O(1), ведь мы не знаем сколько элементов находится между итераторами, а значит — не знаем на сколько изменить счетчик. Однако, если перемещение элементов происходит внутри одного и того же списка — то такая операция все-таки отработает за O(1), ведь в этом случае счетчик изменять не требуется.

Итог: STL — прекрасный инструмент, но имеет очень высокий порог вхождения. Первое время вы неизбежно будете использовать неправильные функции, так как их имена очень часто плохо отражают суть (std::remove_copy_if ничего не удаляет, std::move не просто оставляет элементы в старом контейнере, но может изменить их значения). Стоит очень внимательно смотреть на асимптотическую оценку сложности алгоритмов. Далеко не всегда самое простое решение хуже более сложного — начиная знакомство с STL пишите как можно проще, при необходимости вы всегда сможете улучшить код позже.

Добавить комментарий