时间戳

首页 > 解决方案 > 两个随机访问迭代器上的随机访问迭代器

c++ - 两个随机访问迭代器上的随机访问迭代器

问题描述

假设我有一个表示键的随机访问迭代器（另请参见相关类型特征），以及一个表示值的随机访问迭代器（不一定是单个值，请注意！）。是否可以将它们组合成一个新的随机访问迭代器来执行，比如说，同时排序std::sort（按键，但同时置换键和值）？std::sort只接受一个迭代器。以及如何仅使用核心 C++ 来做到这一点？

我试图在引用元组上指定一个新的迭代器，但问题是如何使交换与右值一起工作（使用一些代理？）？

而且，这两个序列非常大，所以我不能复制它们的值来创建对，甚至不能分配引用的数据结构。事实上，你可以尝试看看你不能对参考对的向量进行排序（想想operator=在这种情况下的行为）。因此，此代码将失败（除非std::sort决定swap仅使用）：

  int arr1[] = {3, 2, -100, 5, 6, -200, 4, 0, -1, 2, 11, 12, -3, -4, -15};
  int arr2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};

  std::vector<std::tuple<int&, int&>> pairs;
  for (int i = 0; i < len; ++i) {
    pairs.push_back(std::tie(arr1[i], arr2[i]));
  }
  std::sort(pairs.begin(), pairs.end(), [](auto lhs, auto rhs) {return std::get<0>(lhs) < std::get<1>(rhs);});

arrays print outs:
-15 -15 -15 -15 -15 -15 -15 -15 -15 -15 -15 -15 -15 -15 -15
14 14 14 14 14 14 14 14 14 14 14 14 14 14 14

到目前为止，我发现了这个： https ://web.archive.org/web/20120422174751/http://www.stanford.edu/~dgleich/notebook/2006/03/sorting_two_arrays_simultaneou.html 。但是，此解决方案使用 boost，并且不兼容交换。

更新：我能够通过在引用元组上创建一个包装器来解决交换问题。但现在我有一个移动问题。std::sort提取和分配值。但是我该如何做参考呢？（请参阅上面的损坏代码）。

标签： c++iterator

解决方案

受此线程的启发，我似乎能够通过tuple像这样编写自定义包装器来解决该问题：

template <typename ...Ts>
struct references_holder {
  using tuple_references = std::tuple<Ts&...>;
  using tuple_values = std::tuple<Ts...>;

  references_holder(tuple_references data)
    : data{data}
  {}

  operator tuple_references() {
    return data;
  }

  tuple_references& as_tuple() {
    return data;
  }

  operator tuple_values() {
    return data;
  }

  references_holder& operator=(tuple_values val) {
    data = val;
    return *this;
  }

  tuple_references data;
};

template <typename ...Ts>
void swap(references_holder<Ts...> th1, references_holder<Ts...> th2) {
  return std::swap(th1.data, th2.data);
}

template<int N, typename ...Ts>
auto get(references_holder<Ts...>& th) -> decltype(std::get<N>(th.data)){
  return std::get<N>(th.data);
}

在我的复合迭代器中：

template <typename KeyIterator, typename ValueIterator>
class CompositeIterator {
public:  
  using key_iterator_value_type =
    typename std::iterator_traits<KeyIterator>::value_type;
  using value_iterator_value_type =
    typename std::iterator_traits<ValueIterator>::value_type;

  using value_type = std::tuple<
    key_iterator_value_type,
    value_iterator_value_type>;
  using reference = references_holder<
    key_iterator_value_type,
    value_iterator_value_type>;
...

它肯定假设依赖于模板的类型具有reference = value_type&. 其余的基于value_type和实现reference。

推荐阅读