现代C++实战篇(一)—泛型实现容器插入元素的自动排序

如果想要在容器中保存有序的字符串，往往需要我们自己手动排序。今天就实现一种可以在插入数据时就自动进行排序的方法。下面先来看下现在对vector元素排序的实现方法：

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

int main()
{
    std::vector<std::string> vRes={"gdb","online","is","an","online","compiler","and","debugger","tool",
    "for"};
    std::cout<<"排序前:"<<std::endl;
    for(auto it :vRes){
        std::cout<<it<<" ";
    }
    std::cout<<std::endl;
    std::sort(vRes.begin(),vRes.end());
     std::cout<<"排序后:"<<std::endl;
    for(auto it :vRes){
        std::cout<<it<<" ";
    }
    std::cout<<std::endl;
    return 0;
}

如上代码段，在向vector容器中初始化随机字符串后，经过编译器编译运行输出排序前后的字符串。输出结果如下：

排序前:
gdb online is an online compiler and debugger tool for 
排序后:
an and compiler debugger for gdb is online online tool

也就是说，上面的代码中，如果想要对容器中元素保持有序，就需要在容器插入元素完成后再进行排序，但实际上，我们有时候并不希望这样，而是想要在元素插入时就同时保持容器内元素有序。要想实现这个功能，我们要借助一个C++的新特性，如下所示：

std::lower_bound

std::lower_bound定义在头文件中，有两种定义形式，如下：

//比较函数使用默认的
template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                               const T& val);
//可以字定义比较函数
template <class ForwardIterator, class T, class Compare>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                               const T& val, Compare comp);

lower_bound在实际使用时会返回[first,last]区间内的满足比较函数的元素的迭代器指针。现在我们就用该方法实现元素的实时插入排序，实现方法如下：

void my_sort_insert(std::vector<std::string> &v,const std::string &str)
{
    auto it = lower_bound(v.begin(),v.end(),str);
    v.insert(it,str);
}

使用上面的方法既可以实现vector实时插入字符串并自动排序，示例代码如下：

void my_sort_insert(std::vector<std::string> &v,const std::string &str)
{
    auto it = lower_bound(v.begin(),v.end(),str);
    v.insert(it,str);
}
int main()
{
    std::vector<std::string> vRes={"gdb","online","is","an","online","compiler","and","debugger","tool",
    "for"};
    std::sort(vRes.begin(),vRes.end());
    my_sort_insert(vRes,"kill");
    my_sort_insert(vRes,"zip");
     std::cout<<"排序后:"<<std::endl;
    for(auto it :vRes){
        std::cout<<it<<" ";
    }
    return 0;
}

上面代码实现了向已经有序的vector中继续插入字符串并实现自动排序的功能，代码运行结果如下：

排序后:
an and compiler debugger for gdb is kill online online tool zip

由上，在新插入的"kill"和"zip"字符串在容器中都进行了自动排序。不过上面的代码实现有个限制，即在新插入元素时如果容器不为空，需要先确保vector元素有序。

既然我们说的是现代C++，那么就离不开泛型，不妨再进一步，将上面有序插入的方法实现其泛型方式。现在，我们只需要对我们的方法稍微进行改进一下。

template <typename T,typename arg>
void my_sort_insert(T &v,const arg &str)
{
    auto it = lower_bound(std::begin(v),std::end(v),str);
    v.insert(it,str);
}

再次进行验证，可以看出，得出的结果和上面是一样的。

读到这里，可能大家会有很多想法，既然vector能这么实现，那么set、deque、list是不是也可以使用上面的泛型呢？答案是:可以！而且set有自己的lower_bound方法，效率还会更快！list有自己的排序方法，所以如果想要使用上面的代码实现list的有序插入需要修改一行代码。如下所示：

int main()
{
    std::list<std::string> vRes={"gdb","online","is","an","online","compiler","and","debugger","tool","for"};
    //std::sort(vRes.begin(),vRes.end());
    vRes.sort();
    my_sort_insert(vRes,"kill");
    my_sort_insert(vRes,"zip");
     std::cout<<"排序后:"<<std::endl;
    for(auto it :vRes){
        std::cout<<it<<" ";
    }
    return 0;
}

运行上面代码后，和之前的输出结果一致。到此，我们本文的内容也分享完毕，欢迎大家在下面分享评论。谢谢！

本文由哈喽比特于2年以前收录，如有侵权请联系我们。
文章来源：https://mp.weixin.qq.com/s/1eRRn30q64oLpYgwJkjvUw