C++ returning invalid iterator

Question

My task is:

Write a function that takes a pair of iterators to a vector and an int value. Look for that value in the range and return iterator to requested element.

My implementation for the above task is:

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

using data = vector<int>;
using iter = data::const_iterator;

iter contains(const data, iter, iter, int);

int main() {
    data numbers{1, 2, 5, 7, 9, 14, 18};
    iter b_iter = numbers.begin() + 2;
    iter e_iter = numbers.end();
    iter found = contains(numbers, b_iter, e_iter, 13);

    if (found == numbers.end())
        cout << "not found" << endl;
    else
        cout << *found << endl;

    return 0;
}

iter contains(const data container, iter b_iter, iter e_iter, int num) {
    while (b_iter != e_iter) {
        if (*b_iter == num)
            return b_iter;
        b_iter++;
    }

    return container.end();
}

As you see, I am iterating from beginning to the end and return if searched value is found. Otherwise, function return iterator to one pass the last element (container.end()). But this program outputs 0 to the console, where I expect not found. When updating my function's fist argument to reference to data rather than value like so:

iter contains(const data&, iter, iter, int);

Function works as expected and not found is printed to the terminal. Why passing data by value doesn't work as expected?

Iterators are related to a specific instance (object) of a container. When you pass the vector by value, the function receives a *copy* of the vector, a copy which is unrelated to the iterators you pass. — Some programmer dude, Jul 08 '21 at 08:20
when passed by value, `data` would be a copy, and you return end iterator of another range. — Jarod42, Jul 08 '21 at 08:20
BTW, it is more [`std::find`](https://en.cppreference.com/w/cpp/algorithm/find) than contain that you wrote. and you can return `e_iter` if not found and get rid of container parameter. — Jarod42, Jul 08 '21 at 08:22
[Prefer](https://stackoverflow.com/questions/24901/is-there-a-performance-difference-between-i-and-i-in-c) pre-increment to post-increment. — Evg, Jul 08 '21 at 09:28

songyuanyao · Accepted Answer · 2021-07-08T09:30:01.427

3

When container is passed by value, it's a new vector copied from the argument. Then for return container.end();, the returned iterator belongs to container but has nothing to do with the original vector numbers.

You should just return the e_iter directly, and no need to pass the vector, just like STL algorithms do.

iter contains(iter b_iter, iter e_iter, int num) {
    while (b_iter != e_iter) {
        if (*b_iter == num)
            return b_iter;
        b_iter++; // or ++b_iter; for efficiency
    }

    return e_iter;
}

And check the result by comparing to e_iter too.

iter found = contains(b_iter, e_iter, 13);

if (found == e_iter)
    cout << "not found" << endl;
else
    cout << *found << endl;

edited Jul 08 '21 at 09:30

answered Jul 08 '21 at 08:20

songyuanyao

169,198
16
310
405

thanks for the answer, but `e_iter` doesn't have to be iterator to one pass the last element necessarily. Requirement is `takes a pair of iterators to a vector`. So I think passing vector with reference is better option. – Elgin Cahangirov Jul 08 '21 at 08:24
@ElginCahangirov Answer revised. You're passing a range, and `e_iter` is always the one passing the last element in the range. How the range is defined depends on you. – songyuanyao Jul 08 '21 at 08:27
@ElginCahangirov the "not found iterator" is not necessarily the `end` of the whole container, but the `end` of the range you pass to `contains`. Suppose you only have two iterators (not the container), one pointing to the being the other to the end of the range, then if `contains` returns the second, you know element wasnt found – 463035818_is_not_an_ai Jul 08 '21 at 08:28
@463035818_is_not_a_number what if searched element is exactly equal the last element in the range? – Elgin Cahangirov Jul 08 '21 at 08:33
@ElginCahangirov the last element in the range is `e_iter -1`. You stop the loop when `b_iter == e_iter`. The iterator `e_iter` is not part of the range. It is common convention to use half open ranges, ie `begin` included, `end` not included. Its the same always, whether `e_iter` is the containers `end` or not – 463035818_is_not_an_ai Jul 08 '21 at 08:35
@ElginCahangirov Suppose you want to search the first two elements of the `vector`, then you pass `numbers.begin()` and `numbers.begin() + 2`, the 2nd element matches, then `numbers.begin() + 1` is returned. If the 1st element matches then `numbers.begin()`, if not found then `numbers.begin() + 2` is returned. Is that your intent? – songyuanyao Jul 08 '21 at 08:36
1

@ElginCahangirov maybe the detail you were missing is: `numbers.end()` is not an iterator to the last element in the container. It is an iterator to the element one past the last element, thats why we can use it to indicate "not found". (and it works the same when the range is not the whole container) – 463035818_is_not_an_ai Jul 08 '21 at 08:38
@songyuanyao I thought to include `e_iter` also in my function. But excluding it is better design I see now, as it also conforms to standard library implementations. – Elgin Cahangirov Jul 08 '21 at 08:39
@ElginCahangirov Yes, it should be one passing the last element as 463035818_is_not_a_number said. – songyuanyao Jul 08 '21 at 08:41
`b_iter++;` -> `++b_iter;` – Evg Jul 08 '21 at 09:27
@Evg For efficiency? – songyuanyao Jul 08 '21 at 09:28
[Yes](https://stackoverflow.com/questions/24901/is-there-a-performance-difference-between-i-and-i-in-c). – Evg Jul 08 '21 at 09:28

C++ returning invalid iterator

1 Answers1