Check whether an element exists in a 2D vector

Question

I have inserted some elements in a 2D vector and want to know whether a given element is present in the 2D vector anywhere. Is there any quick way to find the presence of the element ?

The vector is declared as : vector < vector< int > > v;

Answer 1

If you don't have more information about the 2D vector (like somehow sorted), then the best way would be iterating over each row of the 2D vector and using find method to check if it exist or not.

You do something like the following:

bool does_exist(const vector< vector<int> >&  v, int item){

     vector< vector<int> >::const_iterator row;

    for (row = v.begin(); row != v.end(); row++) {
        if(find(row->begin(), row->end(), item) != row->end() )
            return true;
    }

    return false;
}

You can test it with the follwing code:

#include <iostream>
#include <vector>

using namespace std;

int main(){

    int item = 12;
    vector < vector <int> > v;
    vector <int> v1;

    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);

    vector <int> v2;

    v2.push_back(4);
    v2.push_back(5);
    v2.push_back(6);

    v.push_back(v1);
    v.push_back(v2);

    if( does_exist(v, item))
        cout << "Item " << item << " exist" << endl;
    else 
        cout << "Item " << item << " does not exist" << endl;
}

Answer 2

Not as elegant as I had hoped for. Given a 2D vector of int's:

std::vector<std::vector<int>> foo = {
    {{1, 2, 3}},
    {{5, 6, 7}},
    {{8, 9, 13, 15}}
};

you could do this to see if the 13 is present:

bool found =
    find_if(foo.begin(), foo.end(),
            [](const std::vector<int>& v) -> bool {
                return find(v.begin(), v.end(), 13) != v.end();
            }) != foo.end();

Answer 3

TL;DR

Use std::find().

In C++, please use the function from Standard Template Library (STL) if it has been provided.

Elaboration

Let's say you have an 2d vector

std::vector<std::vector<int> > matrix = {
   {1,2,3}, 
   {4,5,6},
   {7,8,9}
};

And if you want to iterate over all the elements in the 2d vector above.

I recommend you to use 2d iterator:

bool element_exist(const vector< vector<int> >&  input, int key){
    // 2d vector iterator
    vector< vector<int> >::iterator row_it; //iterate over each row(s)
    vector<int>::iterator col_it; //iterate over column(s)
    for (row_it = input.begin(); row_it != input.end(); row_it++) { // iterate each row(s)
        for (col_it = row_it->begin(); row_it != row_it->end(); col_it++) {
            if(find(row_it->begin(), row_it->end(), key) != row_it->end())
                return true;
        }
    }
}

and you can use another boolean variable to get the return value of the function key_exist

bool_var = element_exist(matrix, key);

Whole program

#include <vector>
#include <iostream>
using namespace std;

bool element_exist(const vector< vector<int> >&  input, int key){
    // 2d vector iterator
    vector< vector<int> >::const_iterator row_it; //iterate over each row(s)
    vector<int>::const_iterator col_it; //iterate over column(s)
    for (row_it = input.begin(); row_it != input.end(); row_it++) { // iterate each row(s)
        for (col_it = row_it->begin(); row_it != row_it->end(); col_it++) {
            if(find(row_it->begin(), row_it->end(), key) != row_it->end())
                return true;
        }
    }
}

int main() {
    // declaration
    bool bool_var = false; // default false
    std::vector<std::vector<int> > matrix = {{1,2,3}, {4,5,6},{7,8,9}};

    bool_var = element_exist(matrix,1);
    cout << "bool_var: " << bool_var << endl;

    return 0;
}

Result

bool_var: 1