3

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

你会怎么翻译这个：（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);

它必须是等价的，所以像这样的调用返回与我使用数组相同的值：

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

4 回答 4

5

使用函数模板：

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>for和fora数组，反之亦然。intb

于 2015-10-05T19:13:41.837 回答
5

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

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.

于 2015-10-05T19:14:15.100 回答
2

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

Anarray_view<T>是一个类，它存储一对指针 ( band e)，并公开[]and .size()and begin()and and and end()and front()and back()and empty()。它具有来自std::vector<T>&, std::vector<remove_const_T> const&, T(&)[N], std::array<T,N>&,std::array<remove_const_T,N>const&和 from T*, T*and的隐式构造函数T*, size_t。

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

有一个std::experimental::array_view也支持多维数组，或者你可以自己滚动。 这是我在 stack overflow 上发布的一个，它解决了一个不同的问题。它没有without_front，但这很容易编写（这取决于你希望它有多安全——我会选择完全安全的，它拒绝返回格式错误的数组视图，而是返回一个空视图，因为支票很便宜）。

使用看起来像：

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. 如果你想传递一个向量，它会隐式转换。

于 2015-10-05T19:15:36.697 回答
0

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

vector<int> v;
vector<int> w;
// ...
find_kth(&v[0], &w[0] + j, i, w.size() - j, k - j);
于 2015-10-05T19:14:21.550 回答