Реализация С++ <algorithm>

Когда мне нравится знать, как можно реализовать алгоритм в стандартной библиотеке С++, я всегда смотрю http://en.cppreference.com/w/cpp/algorithm, что является отличный источник. Но иногда я не понимаю детали реализации, и мне нужно объяснение, почему что-то сделано именно так. Например, при реализации std::copy_n, почему первое назначение выполняется вне цикла, и поэтому цикл начинается с 1?

template< class InputIt, class Size, class OutputIt>
OutputIt copy_n(InputIt first, Size count, OutputIt result)
{
    if (count > 0) {
        *result++ = *first;
        for (Size i = 1; i < count; ++i) {
            *result++ = *++first;
        }
    }
    return result;
}

Дополнительно: знаете ли вы сайт, на котором объясняются возможные варианты реализации алгоритма?

Ответы

Ответ 1

Сравните это с наивной реализацией:

template< class InputIt, class Size, class OutputIt>
OutputIt copy_n(InputIt first, Size count, OutputIt result)
{
  for (Size i = 0; i < count; ++i) {
    *result++ = *first++;
  }
  return result;
}

Эта версия делает еще одно приращение first!

  • count==0, оба делают 0 приращения first.

  • count==1, их версия имеет нулевые приращения first. Вышеприведенная версия делает 1.

  • count==2, их версия делает один шаг first. В приведенной выше версии 2.

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

Здесь - ошибка, которая возникает, если вы используете наивную реализацию, а Здесь документация, которая утверждает: "Фактическая операция чтения выполняется, когда итератор увеличивается, а не когда он разыменован".

Я еще не проследил главу и стих о существовании разыменованных и неинкрементных входных итераторов. По-видимому, стандартная информация о том, сколько раз copy_n разыгрывает итераторы ввода/вывода, но не указывает, сколько раз она увеличивает входной итератор.

Наивная реализация увеличивает входной итератор еще раз, чем не-наивная реализация. Если у нас есть однопроходный итератор ввода, который читает на ++ с недостаточным пространством, copy_n может бесполезно блокировать дальнейший ввод, пытаясь прочитать данные за конец входного потока.

Ответ 2

Это просто реализация. Реализация в GCC 4.4 отличается (и концептуально проще):

template<typename InputIterator, typename _Size, typename _OutputIterator>
_OutputIterator
copy_n(_InputIterator __first, _Size __n,
     _OutputIterator __result)
{
  for (; __n > 0; --__n)
{
  *__result = *__first;
  ++__first;
  ++__result;
}
  return __result;
}

[С небольшим количеством ручной работы, поскольку я только предоставил реализацию, когда входной итератор является итератором ввода, существует другая реализация для случая, когда итератор является итератором с произвольным доступом]. В этой реализации есть ошибка в том, что она увеличивает входной итератор на один раз больше, чем ожидалось.

Реализация в GCC 4.8 немного запутана:

template<typename _InputIterator, typename _Size, typename _OutputIterator>
_OutputIterator
copy_n(_InputIterator __first, _Size __n,
     _OutputIterator __result)
{
  if (__n > 0)
{
  while (true)
    {
      *__result = *__first;
      ++__result;
      if (--__n > 0)
    ++__first;
      else
    break;
    }
}
  return __result;
}

Ответ 3

При наивной реализации вы увеличиваете входной итератор n раз, а не только n - 1 раз. Это не просто потенциально неэффективно (поскольку итераторы могут иметь произвольные и произвольно дорогие пользовательские типы), но это также может быть совершенно нежелательным, если входной итератор не поддерживает значимое "прошлое" состояние.

Для простого примера рассмотрим возможность чтения элементов n из std::cin:

#include <iostream>    // for std:cin
#include <iterator>    // for std::istream_iterator


std::istream_iterator it(std::cin);
int dst[3];

При наивном решении программа блокирует окончательное приращение:

int * p = dst;

for (unsigned int i = 0; i != 3; ++i) { *p++ = *it++; }   // blocks!

Стандартный алгоритм библиотеки не блокируется:

#include <algorithm>

std::copy_n(it, 3, dst);    // fine

Обратите внимание, что стандарт фактически не говорит об увеличении итератора. Он только говорит (25.3.1/5), что copy_n(first, n, result) имеет

Эффекты: для каждого неотрицательного целого i < n выполняется *(result + i) = *(first + i).

В 24.2.3/3 есть только примечание:

[input-iterator] алгоритмы могут использоваться с istreams в качестве источника ввода данных через шаблон класса istream_iterator.

Ответ 4

Из-за начальной проверки

if (count > 0)

мы знаем, что count > 0, поэтому автор этого кода чувствовал, что ему не нужно было снова проверять счетчик, пока не достигнет значения 1. Помните, что "для" выполняет условный тест в начале каждого итерации, а не в конце.

Size count = 1;
for (Size i = 1; i < count; ++i) {
    std::cout << i << std::endl;
}

ничего не печатает.

Таким образом, код исключает условную ветвь, и если Size равен 1, это исключает необходимость увеличения/настройки "первым" - следовательно, это предварительный приращение.