在c ++中搜索按字典顺序排序的向量<vector <int >>

Question

我需要按vector<vector<int> > vecOfVectors;字典顺序排序.

所以,在按字典顺序排序之前,我的vecOfVectors是:

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

为了做到这一点,我使用以下功能:

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

因此,按字典顺序排序后,我的vecOfVectors现在是:

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

现在给出一个向量,我需要在这个排序的vecOfVectors中搜索它的位置 - 像二进制搜索这样的东西会很好用.在c ++ stl中是否有一些函数可用于执行二进制搜索？

例如:(0,92,92,91)的位置为0; (0,100,17,2)的位置是1; (1,2,3,3)的位置是2; (2,3,1,3)的位置是3; (9,92,81,8)的位置是4; (10,83,7,2)的位置是5.

Answer 1

没有必要添加lexicographical_compare,已经是如何比较矢量.

根据您的具体使用情况,你正在寻找std::lower_bound或std::upper_bound,std::binary_search或std::equal_range-所有这些对排序的向量操作.

下面是您的数据和c ++ 11的完整示例.它构造你的向量,对它进行排序(显示你提到的顺序),然​​后在向量中找到一个值.

#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;
    }

}