0

For a coding test, I have the following function:

static bool exists (int ints[], int size, int k)

The goal is to return true if k is in ints else return false.

Using the std library, one could do this:

static bool exists (int ints[], int size, int k) {
    return std::binary_search(std::begin(ints), std::end(ints), k);
}

However, std::begin() only works with C-style arrays if the size is known to the compiler, from what I've been able to gather. I'm not sure why that is the case though.

Is there a way to achieve what I want without writing a custom iterator to handle it? Is it even possible to write such an iterator?

Using std::vector instead is not an option, since I can't change the function definition. Copying the array to a std::vector before calling std::binary_search() also seems like a waste of CPU time.

Improve this question
5
  • 6
    Do you have to use std::begin and std::end? You can have this effect with std::binary_search(ints, ints + size, k);. Or with std::array/std::vector. Commented May 8, 2021 at 20:04
  • 1
    Wow it didn't occur to me that you could do std::binary_search(ints, ints + size, k); Thanks for the answer. Commented May 8, 2021 at 20:07
  • 1
    That's the way we used to do it before std::begin and std::end existed. Commented May 8, 2021 at 20:08
  • 2
    Array type function arguments are a big lie inherited from C. They are actually just a pointer to the first element. This is one of the reasons there is often confusion between pointers and arrays. As you've noticed std::begin and std::end don't work with pointers. But a pointer is a valid kind of iterator, so you can use pointers instead of std::begin and std::end as long as those pointers refer to a contiguous range of elements. So you can use ints as the begin iterator and ints + size as the end iterator. Commented May 8, 2021 at 20:12
  • also note that std::binary_search is only valid if ints[] is sorted, which you did not mention in the question. Commented Aug 21, 2022 at 12:33

1 Answer 1

Reset to default
3

You cannot use std::begin() or std::end() as you want to because, as Andrieux pointed out in a comment, what appears to be an array-type in the function's argument-list is just a pointer. This is confirmed by the fact that the second argument to the function is the number of elements. Such an argument would not be necessary if the information needed by std::end() were present in ints[].

As each of the first four comments that I saw at the time of this writing indicated, however, the pointer that is passed in is an iterator. In fact, an ordinary pointer has all of the properties of a random-access iterator.

So, yes, you don't need to come up with your own kind of iterator. Just use the passed-in pointer as the commenters indicated.

static bool exists (int ints[], int size, int k) {
  return std::binary_search(ints, ints + size, k);
}

However, calling std::binary_search() is the right thing to do only if the elements of ints[] be ordered so that std::binary_search() will work. You did not state that in your post.

As to whether it be possible to write an iterator like what you might want, the answer is "yes," but it is unnecessary because a pointer is already the right kind of iterator to input to std::binary_search().

You are right that using std::vector in the body would be a waste of time.

You could have done exactly as you originally wanted if both the input-array were ordered, and the signature of the function had instead been

template<int size> bool exists (int (&ints)[size], int k);
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Note that the template<int size> solution is great but only works if size is a compile-time constant.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.