массивы — эквивалент int [] + k для вектора в переполнении стека
У меня есть алгоритм, и я хотел бы перевести мой код, поэтому вместо массивов я бы хотел использовать векторы.
Как бы вы перевели это: (сторона 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]);
Решение
Стандартный способ — использовать диапазоны итераторов:
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,
Другие решения
Используйте шаблон функции:
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, и наоборот.
замещать vector<int> const& а также int size с array_view<const int>,
array_view<T> это класс, который хранит пару указателей (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,
Методы как array_view<T> without_front(size_t=1) а также array_view<T> without_back(size_t=1) также полезны.
Eсть std::experimental::array_view это также поддерживает многомерные массивы, или вы можете свернуть свои собственные. Вот один, который я отправил на переполнение стека, где это решает другую проблему. Не имеет 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, Если вы хотите передать вектор, он неявно преобразует.
Просто переведите vector<int> в массив, что-то вроде:
vector<int> v;
vector<int> w;
// ...
find_kth(&v[0], &w[0] + j, i, w.size() - j, k - j);