Searching lexicographically sorted vector<vector <int> > in c++

Question

I need to sort a vector<vector<int> > vecOfVectors; lexicographically.

So, my vecOfVectors before sorting lexicographically is:

((0,100,17,2),(2,3,1,3),(9,92,81,8),(0,92,92,91),(10,83,7,2),(1,2,3,3))

In order to do so I am using the following function:

std::sort(vecOfVectors.begin(),vecOfVectors.end(),lexicographical_compare);

So, my vecOfVectors after sorting lexicographically is now:

((0,92,92,91),(0,100,17,2),(1,2,3,3),(2,3,1,3),(9,92,81,8),(10,83,7,2))

Now given a vector I need to search its position in this sorted vecOfVectors -- somthing like binary search will work great. Is there some build in function in c++ stl that I can use to perform the binary search?

For example: the position of (0,92,92,91) is 0; position of (0,100,17,2) is 1; position of (1,2,3,3) is 2; position of (2,3,1,3) is 3; position of (9,92,81,8) is 4; position of (10,83,7,2) is 5.

Answer 1

There's no need to add lexicographical_compare, that's already how vectors are compared.

Depending on your exact use case you're looking for std::lower_bound or std::upper_bound, std::binary_search or std::equal_range- all of these operate on sorted vectors.

A complete example with your data and c++11 is below. It constructs your vector, sorts it (showing the order you mention), then finds a single value in the vector.

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

void print(const std::vector<int> & v) {
    std::cout<<"(";
    for(auto x=v.begin(); x!=v.end(); ++x) {
        std::cout<<*x<<",";
    }
    std::cout<<")";
}

void print(const std::vector<std::vector<int>> & v) {
    std::cout<<"(";
    for(auto x=v.begin(); x!=v.end(); ++x) {
        print(*x);
        std::cout<<",";
    }
    std::cout<<")"<<std::endl;
}

int main() {

    std::vector<std::vector<int>> v {
        {0,100,17,2},
        {2,3,1,3},
        {9,92,81,8},
        {0,92,92,91},
        {0,92,92,91},
        {10,83,7,2},
        {1,2,3,3}
    };

    print(v);

    std::sort(v.begin(), v.end());

    print(v);

    std::vector<int> key = { 0,100, 17, 2 };

    auto it = std::lower_bound(v.begin(), v.end(), key);
    if(it!=v.end() && key==*it) {
        std::cout<<"Found it"<<std::endl;
    } else {
        std::cout<<"Not found"<<std::endl;
    }

}

Answer 2

As I said in comments create a function:

bool compare(vector<int> A,vector<int> B)
{
  int i=0;
  while(i<(A.size()<B.size())?A.size():B.size())
    {
      if(A[i]<B[i])
        {
          return 1;
        }
      else if(A[i]==B[i])
        {
         i++;
        }
      else
        {
          return 0;
        }
      }
 return 0;
}