Checking if iterator is not assigned to item when there is no specific container

Question

I want to search for a value in two std::vector's. If it was found in one of them I want to return its iterator. If not, I want to return some value which indicates that it was not found.

In normal situation where only one std::vector is involved, I would return std::vector::end. What should I do in this situation?

Normal situation:

auto find_ten=[](const std::vector<int>& v){
    return std::find(v.cbegin(),v.cend(),10);
}

My situation:

auto find_ten=[](const std::vector<int>& v1,const std::vector<int>& v2){
    auto it1=std::find(v1.cbegin(),v1.cend(),10);
    if(it1==v1.cend()){
        auto it2=std::find(v2.cbegin(),v2.cend(),10);
        if(it2==v2.cend()){
             //What should I return here??
        }
        return it2;
    }
    return it1;
}

I want to return something that I can check it later to know that the number 10 was not found in any of them.

(Though a singular iterator may help you, you're allowed to do surprisingly little with one.) — Lightness Races in Orbit, Aug 06 '16 at 19:01
I would return the index in the array instead, or -1 if not found. This could be done by diffing the `begin()` and iterator pointers. But maybe that's lame. — Jean-François Fabre, Aug 06 '16 at 19:02
@Jean-FrançoisFabre returning index means that you have to return a clue to which vector its belong — Humam Helfawi, Aug 06 '16 at 19:03
If the caller is to remain blissfully unaware of the two vectors, then a sentinel is probably your best choice. Create a dummy vector that is part of your public interface and return its end(). — David Thomas, Aug 06 '16 at 19:07
To back up my earlier comment, be warned! [The "obvious" solution is not all it's cracked up to be.](http://stackoverflow.com/q/17198239/560648) — Lightness Races in Orbit, Aug 06 '16 at 19:07
You should be using `boost::join` to join ranges anyway. Then this is trivial. — Lightness Races in Orbit, Aug 06 '16 at 19:08

score 8 · Accepted Answer · answered Aug 06 '16 at 19:13

8

Since C++14 you are allowed to compare value-initialized iterators if they meet the ForwardIterator category or stronger (see [forward.iterators] paragraph 2). A value-initialized iterator is the equivalent of a null pointer, so you can use:

    if(it2==v2.cend()){
         return std::vector<int>::iterator{};
    }

And then the caller can do:

std::vector<int>::iterator not_found{};
auto find_ten = ...
if (find_ten != not_found)
{
  ...
}

answered Aug 06 '16 at 19:13

Jonathan Wakely

166,810
27
341
521

Thanks.. it seems exactly what I am looking for. But I can not use C++ 14 yet. – Humam Helfawi Aug 06 '16 at 19:19
In practice it will probably work with any version of C++ (except in iterator debugging modes), the C++14 standard just made it officially legal – Jonathan Wakely Aug 06 '16 at 19:52
Ah That is great then – Humam Helfawi Aug 06 '16 at 19:55
Until c++14, just declare a private vector foo and have not_found() return end(foo). This becomes your sentinel value – David Thomas Aug 06 '16 at 23:46
But are you allowed to actually compare a value-initialized iterator with a "normal" iterator (in the "found" case)? [N3644](http://wg21.link/N3644) actually says this is UB in the discussion ("The result of comparing a value-initialized iterator to an iterator with a non-singular value is undefined."). – T.C. Aug 07 '16 at 04:47
@T.C. Good point. That seems to severely limit the usefulness of the feature, so it's only useful in cases very similar to the ::begin() / A::end() example in N3644. Even if it remains undefined for the general case, it would be helpful if the standard containers supported such comparisons. – Jonathan Wakely Aug 15 '16 at 16:33

Jean-François Fabre · Answer 2 · 2016-08-06T19:08:55.360

1

auto find_ten=[](const std::vector<int>& v1,const std::vector<int>& v2){
    auto it1=std::find(v1.cbegin(),v1.cend(),10);
    if(it1==v1.cend()){
        auto it2=std::find(v2.cbegin(),v2.cend(),10);        
        return it2; // whether it's end or not
    }
    return it1;
}

when using, just test (rval != v2.end()) (rval is the returned iterator). I know, that's not very symmetric.

OR

Pass a boolean as out parameter

auto find_ten=[](const std::vector<int>& v1,const std::vector<int>& v2, bool &found){
    found = true; // suppose we will find it

    auto it1=std::find(v1.cbegin(),v1.cend(),10);
    if(it1==v1.cend()){
        auto it2=std::find(v2.cbegin(),v2.cend(),10);  
        found = it2 != v2.end();     // false if not in v1 or in v2
        return it2; // whether it's end or not
    }

    return it1;
}

edited Aug 06 '16 at 19:08

answered Aug 06 '16 at 19:05

Jean-François Fabre

137,073
23
153
219

1

Really? Is it well-defined to compare iterators from different containers? In my experience, `for (auto it = contA.begin(), end = contB.end(); it != end; ++it)` does not go well. – Lightness Races in Orbit Aug 06 '16 at 19:06
I agree this is not very academic, hence my alternate solution. – Jean-François Fabre Aug 06 '16 at 19:09

kfsone · Answer 3 · 2016-08-06T19:27:58.753

You could simply return the right-most vector's end iterator, this makes logical sense:

auto find_ten=[](const std::vector<int>& v1,const std::vector<int>& v2){
    auto it1=std::find(v1.cbegin(),v1.cend(),10);
    if(it1==v1.cend()){
        return std::find(v2.cbegin(),v2.cend(),10);
    }
    return it1;
}

auto it = find_ten(v1, v2);
if (it == v2.end()) // no luck

Or you could take an iterator argument:

auto find_ten=[](const std::vector<int>& v1,const std::vector<int>& v2, std::vector<int>::iterator endit){
    auto it1=std::find(v1.cbegin(),v1.cend(),10);
    if(it1==v1.cend()){
        auto it2=std::find(v2.cbegin(),v2.cend(),10);
        if(it2==v2.cend()){
             return endit;
        }
        return it2;
    }
    return it1;
}

These both, of course, depend on your use case: if you're going to use the returned iterator for more than just direct access to an element, you'll need to consider a different approach:

--- EDIT ---

If you need to use the iterator beyond just direct access to the offending element, you could use std::reference_wrapper to let you return a reference to the offending vector (or you could just return a pointer).

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>

using find_ten_t = std::pair<std::reference_wrapper<const std::vector<int>>, std::vector<int>::const_iterator>;

auto find_ten = [](const std::vector<int>& v1, const std::vector<int>& v2) -> find_ten_t {
    auto it1 = std::find(v1.cbegin(), v1.cend(), 10);
    if (it1 != v1.cend()) {
        return std::make_pair(std::ref(v1), it1);
    }
    auto it2 = std::find(v2.cbegin(), v2.cend(), 10);
    return std::make_pair(std::cref(v2), it2);
};

int main() {
    std::vector<int> v1{ 1, 2, 3 };
    std::vector<int> v2{ 3, 4, 10 };
    auto r = find_ten(v1, v2);
    std::cout << "r.first[0] = " << r.first.get()[0] << "\n";
}

Live demo: http://ideone.com/cNLJKg

@HumamHelfawi If you need more than direct access, see edit. — kfsone, Aug 06 '16 at 19:28

max66 · Answer 4 · 2016-08-06T19:41:55.310

Not really brilliant, I suppose, but... I propose returning a std::pair where the first element is an int (0 for "not found", 1 for "found in first" and 2 for "found in second") and the second is the iterator.

Something like

auto find_ten=[](const std::vector<int>& v1,const std::vector<int>& v2){
    auto it1=std::find(v1.cbegin(),v1.cend(),10);
    if(it1==v1.cend()){
        auto it2=std::find(v2.cbegin(),v2.cend(),10);
        if(it2==v2.cend()){
            return std::make_pair(0, v1.cend()); // or make_pair(0, v2.cend())
        }
        return std::make_pair(2, it2);
    }
    return std::make_pair(1, it1);
};

Or better: you could return a pair of iterator where the second is the cend() of the corresponding vector; something like

auto find_ten=[](const std::vector<int>& v1,const std::vector<int>& v2){
    auto it1=std::find(v1.cbegin(),v1.cend(),10);
    if(it1==v1.cend()){
       return std::make_pair(std::find(v2.cbegin(),v2.cend(),10), v2.cend());
    }
    return std::make_pair(it1, v1.cend());
};

I think it's important to return the cend() correspindig iterator because I suppose you want to use the iterator pointing to 10 and you could iterate it.

Obvioulsy, If you're only interested in knowing if 10 is present in v1 or in v2, I suppose you should returning a bool: true for "found", false otherwise; something like

auto find_ten=[](const std::vector<int>& v1,const std::vector<int>& v2){
    auto ret = v1.cend() != std::find(v1.cbegin(),v1.cend(),10);
    if ( ret == false )
       ret = v2.cend() != std::find(v2.cbegin(),v2.cend(),10);
    return ret;
};

p.s.: sorry for my bad English.

@Jarod42 - I imagine that the use `std::option` can be a solution but... can be my limit... I don't understand the usefulness of returning a const-iterator without informations regarding the container that is referenced. — max66, Aug 07 '16 at 11:53

Checking if iterator is not assigned to item when there is no specific container

4 Answers4