如何复制只有两个迭代器的数据？

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 ++，而且是算法。以默认方式（最快）实施的Mergesort需要额外的临时内存。

有避免这种情况的方法，称为in-place mergesort或简称为[[in-place merging。不过，这非常简单，四处搜寻，您会发现有多种算法可以做到这一点。