相当于 C++ 中 vector 的 int[] + k

Question

我有一个算法，我想翻译我的代码，所以我不想使用数组，而是想使用向量。

你会怎么翻译这个：（b + j 和 a 的边）

find_kth(a, b + j, i, size_b - j, k - j);

其中

int find_kth(int a[], int b[], int size_a, int size_b, int k);

进入

int find_kth(const vector<int>& a, const vector<int>& b, int size_a, int size_b, int k);

它必须是等效的，所以像这样调用 return 与我使用数组时相同的值：

min(a[0], b[0]);

Answer 1

使用函数模板：

template <typename Iterator>
int find_kth(Iterator a, Iterator b, int size_a, int size_b, int k)
{
  ...
}

您可以使用两种类型的迭代器使其更通用。

template <typename IteratorA, typename IteratorB>
int find_kth(IteratorA a, IteratorB b, int size_a, int size_b, int k)
{
  ...
}

这使您可以灵活地将 std::vector<int> 用于 a，将 int 的数组用于 b，反之亦然。

Answer 2

标准方法是使用迭代器范围代替：

template <typename Iterator>
int find_kth(
    Iterator a_begin,
    Iterator a_end,
    Iterator b_begin,
    Iterator b_end,
    int k);

这会派上用场，因为您只需要对向量的一部分进行操作。您不需要使用这种方法拆分向量。

根据 SergeyA 的评论改进了签名：

template <typename T>
using is_fwd_it = std::is_base_of<
    std::forward_iterator_tag,
    typename std::iterator_traits<T>::iterator_category>;

template <typename A_It, typename B_It,
    typename = typename std::enable_if<
        is_fwd_it<A_It>::value && is_fwd_it<B_It>::value>::type>
int find_kth(
    A_It a_begin,
    A_It a_end,
    B_It b_begin,
    B_It b_end,
    int k);

您还可以添加另一个模板参数，或使用 std::iterator_traits 来获取 value_type，而不是使用 int.

Answer 3

只需将 vector<int> 转换为数组，例如：

vector<int> v;
vector<int> w;
// ...
find_kth(&v[0], &w[0] + j, i, w.size() - j, k - j);

Answer 4

将 vector<int> const& 和 int size 替换为 array_view<const int>。

一个array_view<T>是一个class，存储一对指针（b和e），并公开[]和.size()、begin()、end()、front()、back()、empty()。它具有来自 std::vector<T>&、std::vector<remove_const_T> const&、T(&)[N]、std::array<T,N>&、std::array<remove_const_T,N>const& 以及 T*, T* 和 T*, size_t 的隐式构造函数。 =38=]

array_view<T> without_front(size_t=1) 和 array_view<T> without_back(size_t=1) 等方法也很有用。

有一个std::experimental::array_view也支持多维数组，你也可以自己滚。 Here is one I posted on stack overflow，它解决了一个不同的问题。它没有 without_front，但这很容易编写（这取决于您希望它有多安全——我会选择完全安全，它拒绝 return 格式错误的数组查看，而不是 return 一张空的，因为支票很便宜）。

使用看起来像：

int find_kth(array_view<int const> a, array_view<int const> b, int k){
  // ...
  find_kth(a, b.without_front(j), k-j);
  // ...
}

我觉得它很漂亮。如果你想传递原始数组，只需 {arr, size}，它就会变成 array_view。如果你想传递一个向量，它会隐式转换。

相当于 C++ 中 vector 的 int[] + k

equivalent of int[] + k on vector in c++

c++

arrays

pointers

vector

array-view