现代C++实战篇(一)—泛型实现容器插入元素的自动排序
现代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_boundstd::lower_bound定义在<algorithm>头文件中，有两种定义形式，如下：
//比较函数使用默认的
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;
}运行上面代码后，和之前的输出结果一致。到此，我们本文的内容也分享完毕，欢迎大家在下面分享评论。谢谢！
- EOF -