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

Question

I have an algorithm and I'd like to translate my code so instead of using arrays I'd like to use vectors.

How would you translate this: (the side of b + j and a)

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

where

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

into

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

It must be equivalent so calls like this return the same value as if I were using arrays:

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

Answer 1

A standard way would be to use iterator ranges instead:

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

This comes in handy, since you need to operate only on a section of a vector. You don't need to split the vector with this approach.

Improved signature based on SergeyA's comment:

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

You can also add another template parameter, or use std::iterator_traits to get the value_type, instead of having int.

Answer 2

Use a function template:

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

You can make it more general by using two types of iterators.

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

This allows you the flexibility of using std::vector<int> for a and an array of int for b, and vice versa.

Answer 3

Simply translate the vector<int> to an array, something like:

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

Answer 4

Replace vector<int> const& and int size with an array_view<const int>.

An array_view<T> is a class that stores a pair of pointers (b and e), and exposes [] and .size() and begin() and end() and front() and back() and empty(). It has implicit constructors from std::vector<T>&, std::vector<remove_const_T> const&, T(&)[N], std::array<T,N>&, std::array<remove_const_T,N>const&, and from T*, T* and T*, size_t.

Methods like array_view<T> without_front(size_t=1) and array_view<T> without_back(size_t=1) are also useful.

There is a std::experimental::array_view that also supports multi-dimensional arrays, or you can roll your own. Here is one I posted on stack overflow, where it solves a different problem. It doesn't have without_front, but that is easy to write (it depends on how safe you want it to be -- I'd go for fully safe, where it refuses to return a malformed array view and instead returns an empty one, because the check is cheap).

Use looks like:

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

which I find slick. If you want to pass raw arrays, just {arr, size} and it becomes an array_view. If you want to pass a vector, it implicitly converts.