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

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};

如何让两个迭代器在不绑定(bind)到特定容器的情况下将数据复制到另一个变量，并使用例如这些迭代器所属的容器？有没有更优雅的方法来做到这一点？

Answer 1

您正在寻找的不仅仅是 C++ 的东西，它是算法的东西。以默认(也是最快的)方式实现的归并排序需要额外的临时内存。

有一些方法可以避免这种情况，称为就地合并排序或简称为就地合并。虽然这非常重要，但四处搜索，您会发现多种算法可以做到这一点。