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

The `+j` is basically defining where in the vector it should start. You can either create a new vector starting from `j`, or passing `j` to the function and use it internally. BTW, you wont need the size anymore. — wendelbsilva, Oct 05 '15 at 19:12
`int size_a, int size_b` are not needed as the vector stores its size. — NathanOliver, Oct 05 '15 at 19:12
Why are you trying to do this, I think you can use the `vector::data()` method and keep the function as it is. Or use [iterators](http://en.cppreference.com/w/cpp/iterator#iterator_categories). — Iharob Al Asimi, Oct 05 '15 at 19:13
I'm using sizes bcause it's an algorithm to find the k-th element so I the size isn't exactly the size but the size limit I want to explore — Daniel Roca Lopez, Oct 05 '15 at 19:13
I would recommend either passing `j` as an argument as wendelbsilva recommends, or to change the prototype to actually take raw pointers and use `b.data() + j` (the `data` function gives you the pointer to the data stored in the `vector`) — R_Kapp, Oct 05 '15 at 19:13

R Sahu · Answer 1 · 2015-10-05T19:19:27.410

5

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.

edited Oct 05 '15 at 19:19

answered Oct 05 '15 at 19:13

R Sahu

204,454
14
159
270

it worked! but as I asked to LogicStuff on the other reply, could him or you explain the use of template? I'd be very thankful! – Daniel Roca Lopez Oct 05 '15 at 19:28
2

@DanielRocaLopez, Take a look at [Iterator Concept](http://en.cppreference.com/w/cpp/concept/Iterator) and [the C++ algorithms library](http://en.cppreference.com/w/cpp/algorithm). Hopefully those pages will answer your questions. – R Sahu Oct 05 '15 at 19:33

LogicStuff · Accepted Answer · 2015-12-28T12:18:31.737

5

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.

edited Dec 28 '15 at 12:18

answered Oct 05 '15 at 19:14

LogicStuff

19,397
6
54
74

2

While I did upvote, you do not technically need two groups of iterators to be of the same type. And you want them to be specific iterators - forward iterators, for instance. So your find_kth could be improved :) – SergeyA Oct 05 '15 at 19:17
it worked! could you give me a little explain about what does template mean or does and why did I have to add it? it didn't work without adding template then adding it like you, it worked. I couldn't add iterator as a parameter otherwise. – Daniel Roca Lopez Oct 05 '15 at 19:27
1

Well, template here allows you to use this function with all kinds of `Iterator` types for which the code in it compiles. May you decide to use `vector` for example, you don't need to change the function. You should look up templates for more info... – LogicStuff Oct 05 '15 at 19:38
@SergeyA On that second part, do you mean SFINAE? What benefit comes from that? One can just document what minimum iterator type it requires (like STL implementations?) – LogicStuff Oct 05 '15 at 20:36
@LogicStuff, STL was designed done in 98 (or something). Now we do have concepts, don't we? – SergeyA Oct 05 '15 at 21:22
@SergeyA Check the updated answer. Is that what you wanted? – LogicStuff Oct 07 '15 at 20:07
1

@LogicStuff, I do like it. Though I already upvoted, so I can't upvote any more :) – SergeyA Oct 07 '15 at 20:28

score 2 · Answer 3 · edited May 23 '17 at 12:08

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.

score 0 · Answer 4 · answered Oct 05 '15 at 19:14

0

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

answered Oct 05 '15 at 19:14

Paul Evans

27,315
3
37
54

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

4 Answers4