Как скопировать данные, имеющие только два итератора?

Question

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

  template<class Iterator>
    void merge_sort(Iterator t_begin, Iterator t_end)
    {
      // Recursion ends when the sequence becomes 1
      if(std::distance(t_begin, t_end) < 2) {
        return;
      }

      // Combining two sorted sequences
      auto merge = [](Iterator begin, Iterator middle, Iterator end) {
        // Supposed, subarrays are sorted
        const std::deque<std::remove_reference_t<decltype(*begin)>> left {begin, middle}, right {middle, end};

        auto left_it = left.begin(), right_it = right.begin();

        // Merge two subarrays into one sorted
        for(Iterator itr = begin; itr != end; ++itr) {
          if(left_it == left.end()) {
            *itr = *right_it++;
          } else if(right_it == right.end()) {
            *itr = *left_it++;
          } else if(*left_it <= *right_it) {
            *itr = *left_it++;
          } else {
            *itr = *right_it++;
          }
        }
      };

      Iterator middle = t_begin + static_cast<std::size_t>((std::distance(t_begin, t_end) / 2));
      merge_sort(t_begin, middle);
      merge_sort(middle, t_end);
      merge(t_begin, middle, t_end);
    }

В качестве решения я использую явное объявление структуры данных очереди.

const std::deque<std::remove_reference_t<decltype(*begin)>> left {begin, middle}, right {middle, end};

Как два итератора могут копировать данные в другую переменную без привязки к конкретному контейнеру и использовать, например, тот, к которому этиитераторы принадлежат? Есть ли более элегантный способ сделать это?

Answer 1

То, что вы ищете, это не просто C ++, это алгоритмическая вещь. Для слияния, реализованного по умолчанию (и самым быстрым), требуется дополнительная временная память.

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