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

Итак, решаемая в тесте задача сформулирована следующим образом:

дан вектор целых чисел, необходимо вставить значение «0» перед каждым нечетным числом. Пусть, у нас уже есть такая функция:

bool is_odd(int value) {
  return value % 2;
}

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

Про оценку трудоемкости алгоритмов я рекомендую прочитать в этих статьях:
Анализ сложности алгоритмов и Примеры анализа сложности алгоритмов. В документации по C++ для ряда алгоритмов в качестве оценки указывается «амортизированное время» — это средняя оценка в наихудшем случае (от анализа среднего случая отличается тем, что последний является вероятностным).

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

test_stl_results_1
распределение баллов
test_stl_results_2
Статистика второго вопроса
test_stl_results_3
Статистика пятого вопроса

Эти картинки хорошо показывают как легко в С++ ошибиться (да и в любом другом языке тоже). Притом, что подавляющее большинство респондентов искренне интересовались С++ (были найдены в тематических сообществах).

Первый вариант решения:

void first(std::vector<int>& vec) {
  std::vector<int> temp;
  for (size_t i = 0; i < vec.size(); ++i) {
    if (is_odd(vec[i])) {
      temp.push_back(0);
    }
    temp.push_back(vec[i]);
  }
  std::swap(vec, temp);
}

Такой код вполне мог бы написать человек, услышавший кое-что про вектора на лекции, но не задумывающийся о том, как это работает внутри. Вариант не самый плохой — он работает, кроме того, вставка элемента в конец вектора-копии выполняется за амортизированное \(O(1)\), хотя в отдельных случаях — за \(O(n)\). Тем не менее, наиболее правильная оценка трудоемкости всего алгоритма — амортизированное \(O(n)\).

Второй вариант решения:

void second(std::vector<int>& vec) {
  for (size_t i = 0; i < vec.size(); ++i) {
    if (is_odd(vec[i])) {
      vec.insert(vec.begin()+i, 0);
      ++i;
    }
  }
}

Этот вариант решения вполне мог бы получиться у человека, кое-что прочитавшего про STL. В самом деле, нужно вставить элементы — это делает функция insert, значит мы можем обойтись без явного копирования вектора. После вставки изменится размер вектора, однако следующий вызов функции size вернет новое значение. Конструкция vec.begin()+i также является совершенно корректной, т.к. вектор предоставляет итераторы произвольного доступа, для которых определены, помимо прочего, операторы + и -. Кстати, в книге Леена Аммерааля «STL для программистов на С++» рекомендуется заменять такую конструкцию на vec[i], однако в этом случае работать такая замена не будет. Остается не забыть, что при вставке новый элемент помещается перед заданным итератором, а значит нужно не забыть ++i.

В процессе выполнения будет выполнено порядка n операций вставки, каждая из которых для вектора имеет трудоемкость \(O(n)\), т.к. даже если не потребуется реаллокация, для вставки нужно сдвинуть элементы, находящиеся справа от текущего итератора. Результирующая трудоемкость — \(O(n^2)\).

Третий вариант решения:

void third(std::vector<int>& vec) {
  auto beg = vec.begin();
  for (size_t i = 0; i < vec.size(); ++i) {
    if (is_odd(vec[i])) {
      vec.insert(beg+i, 0);
      ++i;
    }
  }
}

Такой вариант мог получиться у криворукого программиста при попытке оптимизации предыдущего. В самом деле, зачем на каждой итерации цикла вызывать функцию begin()? (ну ладно size() — размер-то у нас меняется…). Тем не менее, такая функция через раз будет приводить к неопределенному поведению (обработать ошибку по-человечески не получится). Дело в том, что после вызова insert становятся нерабочими все итераторы справа от добавленного элемента, а в случаях если необходима реаллокация (новое значение size больше чем capacity) — невалидными становятся все итераторы, в том числе begin.

Четвертый вариант решения:

void fourth(std::vector<int>& vec) {
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (is_odd(*it)) {
      vec.insert(it, 0);
    }
  }
}

Ну а что, если не использовать индексы и все эти (begin() + i), а попробовать обойтись только итераторами? Инкрементировать итератор после вставки не требуется, т.к. вставка происходит перед it. Однако работать это не будет — после вставки it становится невалидным, т.к. находится справа от добавляемых элементов. Хотя, такой код прекрасно работал бы для std::list (но об этом будет следующий тест).

Пятый вариант решения:

void fifth(std::vector<int>& vec) {
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (is_odd(*it)) {
      it = vec.insert(it, 0);
      ++it;
    }
  }
}

Тут мы также как в предыдущем варианте пробуем использовать итераторы, однако исправляем ошибки. Вспоминаем, что insert вернет валидный итератор нового элемента… Оценка трудоемкости аналогична рассмотренной выше для функции second.

Шестой вариант решения:

void sixth(std::vector<int>& vec) {
  for (auto it = vec.begin();
      (it = std::find_if (it, vec.end(), is_odd)) != vec.end();
       ++it) {
    it = vec.insert(it, 0);
    ++it;
  }
}

Зачем нам вручную перебирать все элементы, если нам нужно найти лишь определенные? — а это умеет делать стандартный алгоритм find_if. Мы находим первый нечетный элемент, выполняем вставку и ищем дальше (главное — не забыть инкремент итератора). Если же такого элемента нет — алгоритм find_if вернет нам end().

Каждый элемент вектора будет обработан алгоритмом find_if единственный раз, а трудоемкость алгоритма составит \(O(n^2)\).

Кстати, выглядит такая функция не очень хорошо. Компилятор выдает предупреждение

variable ‘it’ is incremented both in the loop header and in the loop body

В качестве дополнительного задания можно попробовать переписать этот фрагмент более «чисто», при этом подсчитав сколько раз вы отстрелите ногу.

Седьмой вариант решения:

void seven(std::vector<int>& vec) {
  std::vector<int> temp;
  auto odd_count = std::count_if(vec.begin(), vec.end(), is_odd);
  temp.reserve(vec.size() + odd_count);

  for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (is_odd(*it)) {
      temp.push_back(0);
    }
    temp.push_back(*it);
  }
  std::swap(vec, temp);
}

Наконец, лучший из приведенных вариантов. Основная проблема всех предыдущих была в том, что при выполнении вставки может выполниться реаллокация. С одной стороны, это опасно (выше приведена куча вариантов ошибиться), а с другой — медленно. Даже амортизированная трудоемкость \(O(1)\) операции push_back — это не очень хорошо если без особого труда можно получить честное \(O(1)\). Всего-то нужно заранее выделить память под элементы вектора. Итак, обработка теперь ведется в два прохода. Трудоемкость всего алгоритма \(O(n)\).

Однако, этот алгоритм можно еще улучшить, причем в различных направлениях:

  1. если нечетных элементов мало, то можно более эффективно копировать куски старого массива в новый;
  2. можно обойтись без вспомогательного массива, выполнив reserve для уже имеющегося, а чтобы снизить трудоемкость операции вставки — обрабатывать элементы массива с конца.
  3. может быть есть и другие варианты (был бы рад увидеть).

Свои варианты можно выкладывать на форум.

Если вы провалили тест — рекомендую посмотреть книги по STL (Майерса и Аммерааля).

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *