C++ STL库的介绍和使用（下）-阿里云开发者社区

C++ STL库的介绍和使用（上）：https://developer.aliyun.com/article/1459450

set/multiset

set的特性是：所有元素都会根据元素的键值自动排序。set元素不像map那样可以同时拥有键和值，set元素既是键又是值。set不允许两个元素拥有同样的键值。

set不可以通过迭代器修改set的值，set的值也是键，关系到set元素的排序规则。

multiset的特性和用法和set完全相同，唯一不同的是multiset允许键值重复。set和multiset的底层实现是红黑树，红黑书是平衡二叉树的一种。

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
void print(const set<int> &ll)
{
    for(auto & a : ll)
    {
        cout << a << " ";
    }
    cout << endl;
    fflush(stdout);
}
class Compare
{
public:
    bool operator()(const int& p1,const int& p2) const//一定要定义为常函数，且参数需要限定为const
    {
        return p1 > p2;
    }
};
void print(const set<int, Compare> &ll)
{
    for(auto & a : ll)
    {
        cout << a << " ";
    }
    cout << endl;
    fflush(stdout);
}
void test()
{
    set<int> ss;
    ss.insert(2);
    ss.insert(3);
    ss.insert(45);
    ss.insert(10);
    ss.insert(2);
    print(ss);
    cout << ss.size() << endl;
    ss.erase(3);
    print(ss);
    cout << ss.count(2) << endl;
    multiset<int> ss2;
    ss2.insert(2);
    ss2.insert(3);
    ss2.insert(45);
    ss2.insert(10);
    ss2.insert(2);
    ss2.erase(3);
    cout << ss2.count(2) << endl;
    auto it = ss.find(5);
    it != ss.end()? cout << "找到了" << endl : cout << "没有找到" << endl;
    auto it1 = lower_bound(ss.begin(), ss.end(), 10);
    auto it2 = upper_bound(ss.begin(), ss.end(), 10);
    auto mm = ss.equal_range(30);
}
void test01()
{
    set<int, Compare> ss;
    ss.insert(2);
    ss.insert(6);
    ss.insert(8);
    print(ss);
}
int main(int argc, char* argv[])
{
    test01();
    return 0;
}

注意： set存放自定义数据类型的时候必须指定排序规则。

pair

对组是将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公有属性first和second进行访问。

#include <iostream>
#include <algorithm>
using namespace std;
void test()
{
    pair<int, int> pp(1, 2);
    cout << pp.first << " " << pp.second << endl;
    pair<int, int> pp1 = make_pair(1, 2);
    cout << pp1.first << " " << pp1.second << endl;
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

map/multimap

map的特性是所有元素会根据元素的键值自动排序。map所有的元素都是pair，同时拥有实值和键值，pair的第一个元素是键值，第二个元素被视为实值，map不允许两个元素有相同的键值。

map的键值不可变，实值是可变的。

multimap和map的操作类似，唯一的区别就是multimap键值可重复。map和multimap都是以红黑树为底层实现机制。

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
void print(const map<int, int> &ll)
{
    for(auto & a : ll)
    {
        cout << a.first << " " << a.second << " " << endl;
    }
    fflush(stdout);
}
void test()
{
    int a = 10;
    int &b = a;
    a = 20;
    cout << a << endl;
    cout << b << endl;
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

容器的使用时机

	典型的存储结构	可随机存取
vector	单端数组	是
deque	双端数组	是
list	双向列表	否
set/multiset	红黑树	否
map/multimap	红黑树	否(针对于ke)

	元素查询	元素插入删除
vector	慢	尾部
deque	慢	两端
list	非常慢	任何位置
set/multiset	快
map/multimap	快

函数对象（仿函数）

重载函数调用操作符的对象，其对象常称为函数对象，即他们是行为类似于函数的对象，也叫仿函数，其实就是重载了"()"操作符，使得对象可以像函数那样调用。

注意：

函数对象是一个类，不是一个函数。
函数对象重载了"()"操作符，使他可以像函数一样调用。

分类：

如果一个函数重载了"()"且需要一个参数，则称为一元仿函数
如果一个函数重载了"()"且需要两个参数，则称为二元仿函数

总结：

函数对象通常不定义构造函数和析构函数，所以在构造和析构的时候不会发生任何问题，避免了函数调用的运行时问题。
函数对象超出了普通函数的概念，函数对象可以有自己的状态
函数对象可以内联编译，性能好。用函数指针几乎不可能
模板函数对象使得函数对象具有通用性，这就是他的优势之一

谓词

指的是普通函数或者是仿函数的返回值是bool类型的函数对象。

如果operator接受一个参数，则叫一元谓词，如果接受2个参数则称为二元谓词。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool findBigThan10(int a)
{
    return a > 10;
}
class Find20
{
public:
    bool operator()(int v)
    {
        return v > 20;
    }
};
void test()
{
    vector<int> vv;
    vv.push_back(10);
    vv.push_back(20);
    vv.push_back(30);
    vv.push_back(40);
    vv.push_back(50);
    vv.push_back(60);
    auto ret = find_if(vv.begin(), vv.end(), findBigThan10);
    auto ret1 = find_if(vv.begin(), vv.end(), Find20());
    cout << *ret << endl;
    cout << *ret1 << endl;
}
bool compare(int left, int right)
{
    return left > right;
}
class Compare
{
public:
    bool operator()(int left, int right)
    {
        return left < right;
    }
};
void test02()
{
    vector<int> vv;
    vv.push_back(10);
    vv.push_back(20);
    vv.push_back(30);
    vv.push_back(40);
    vv.push_back(50);
    vv.push_back(60);
    sort(vv.begin(), vv.end(), compare);
    for_each(vv.begin(), vv.end(), [](int val){
        cout << val << " ";
    });
    cout << endl;
    sort(vv.begin(), vv.end(), Compare());
    for_each(vv.begin(), vv.end(), [](int val){
        cout << val << " ";
    });
    cout << endl;
}
int main(int argc, char* argv[])
{
    test02();
    return 0;
}

内建函数对象

STL内建了一些函数对象，分为：算数类函数对象，关系运算类函数对象，逻辑运算类仿函数。这些仿函数所产生的对象，用法和一般函数完全相同，当然我们还可以产生无名的临时对象来履行函数功能。

下面列出一些简单的例子。如果想要查看内建的函数，可以到对应的文件内查看对应的函数原型。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool findBigThan10(int a)
{
    return a > 10;
}
class Find20
{
public:
    bool operator()(int v)
    {
        return v > 20;
    }
};
void test()
{
    plus<int> p;
    cout << p(10, 20) << endl;
    cout << plus<int>()(50, 20) << endl;
    minus<int> p1;
    cout << p1(10, 20) << endl;
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

适配器

bind2nd和bind1st

#define _HAS_AUTO_PTR_ETC 1
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
void print(int a, int b)
{
    cout << a << " " << b << " " << endl;
}
class Print : public binary_function<int, int, void>
{
public:
    void operator()(int a, int b) const
    {
        cout << a << " " << b << " " << endl;
    }
};
void test()
{
    vector<int> vv;
    vv.push_back(10);
    vv.push_back(20);
    vv.push_back(30);
    vv.push_back(40);
    for_each(vv.begin(), vv.end(), bind1st(Print(), 5));
    for_each(vv.begin(), vv.end(), bind2nd(Print(), 5));
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

not1 和 not2 mem_fun_ref和ptr_fun

这里列出标题，不做代码展示

算法

算法主要是由头文件组成，是所有stl头文件中最大的一个，其中常用的功能涉及到比较，交换，查找，遍历，修改，翻转，排序，合并等。体积很小，只包括在几个序列容器上进行的简单运算的模板函数，定义了一些模板类，用以声明函数对象。

常用的遍历算法

for_each
transform

#define _HAS_AUTO_PTR_ETC 1
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
int mvTransform(int a)
{
    return a;
}
class Print : public binary_function<int, int, void>
{
public:
    void operator()(int a, int b) const
    {
        cout << a << " " << b << " " << endl;
    }
};
void test()
{
    vector<int> vv;
    vv.push_back(10);
    vv.push_back(20);
    vv.push_back(30);
    vv.push_back(40);
    vector<int> bb;
    bb.resize(vv.size());
    transform(vv.begin(), vv.end(), bb.begin(), mvTransform);
    for_each(bb.begin(), bb.end(), bind2nd(Print(), 5));
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

常用的查找算法

find
find_if
adjacent_find 查找相邻的重复元素
binary_find 二分查找，前提是容器必须有序
count 统计元素出现次数
count_if 按照条件统计次数

#define _HAS_AUTO_PTR_ETC 1
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
class Person
{
public:
    Person(int a) : age(a) {}
    int age;
};
bool operator==(const Person &left, const Person &right)
{
    return left.age == right.age;
}
void test()
{
    vector<int> vv;
    vv.push_back(10);
    vv.push_back(10);
    vv.push_back(20);
    vv.push_back(30);
    vv.push_back(30);
    auto it = adjacent_find(vv.begin(), vv.end());
    if(it != vv.end())
    {
        cout << *it << endl;
    }
    vector<Person> vp;
    vp.push_back(50);
    vp.push_back(50);
    auto itP = adjacent_find(vp.begin(), vp.end());
    if(itP != vp.end())
    {
        cout << itP->age << endl;
    }

}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

其他

merge
sort
random_shuffle 打乱
reverse 反转
copy
replace
replace_if
swap 交换函数

#define _HAS_AUTO_PTR_ETC 1
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
void test()
{
    vector<int> vv;
    vv.push_back(10);
    vv.push_back(10);
    vv.push_back(20);
    vv.push_back(20);
    vv.push_back(30);
    vv.push_back(30);
    vv.push_back(40);
    vv.push_back(40);
    vector<int> v2;
    v2.push_back(10);
    v2.push_back(30);
    vector<int> v3;
    v3.resize(vv.size() + v2.size());
    merge(vv.begin(), vv.end(), v2.begin(), v2.end(), v3.begin());
    for_each(v3.begin(), v3.end(), [](int a){
        cout << a << " ";
    });
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

算数生成算法

accumulate 累加求和
fill

#define _HAS_AUTO_PTR_ETC 1
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <numeric>
using namespace std;
void test()
{
    vector<int> vv;
    vv.push_back(10);
    vv.push_back(10);
    int sum = accumulate(vv.begin(), vv.end(), 0);
    cout << sum << endl;
    fill(vv.begin(), vv.end(), 20);
    for_each(vv.begin(), vv.end(), [](int a){ cout << a << endl; });
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

集合算法

set_intersection 求交集

#define _HAS_AUTO_PTR_ETC 1
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <numeric>
using namespace std;
void test()
{
    vector<int> vv;
    vv.push_back(10);
    vv.push_back(20);
    vv.push_back(30);
    vv.push_back(40);
    vector<int> v2;
    v2.push_back(30);
    v2.push_back(40);
    v2.push_back(50);
    v2.push_back(60);
    vector<int> v3;
    v3.resize(4);
    auto it = set_intersection(vv.begin(), vv.end(), v2.begin(), v2.end(), v3.begin());
    int size = 4 - (v3.end() - it);
    v3.resize(size);
    for_each(v3.begin(), v3.end(), [](int a){ cout << a << endl;});
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

set_union 求交集

#define _HAS_AUTO_PTR_ETC 1
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <numeric>
using namespace std;
void test()
{
    vector<int> vv;
    vv.push_back(10);
    vv.push_back(20);
    vv.push_back(30);
    vv.push_back(40);
    vector<int> v2;
    v2.push_back(30);
    v2.push_back(40);
    v2.push_back(50);
    v2.push_back(60);
    vector<int> v3;
    v3.resize(8);
    auto it = set_union(vv.begin(), vv.end(), v2.begin(), v2.end(), v3.begin());
    int size = 8 -(v3.end() - it);
    v3.resize(size);
    for_each(v3.begin(), v3.end(), [](int a){ cout << a << endl;});
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

set_difference 求差集

#define _HAS_AUTO_PTR_ETC 1
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <numeric>
using namespace std;
void test()
{
    vector<int> vv;
    vv.push_back(10);
    vv.push_back(20);
    vv.push_back(30);
    vv.push_back(40);
    vector<int> v2;
    v2.push_back(30);
    v2.push_back(40);
    v2.push_back(50);
    v2.push_back(60);
    vector<int> v3;
    v3.resize(4);
    auto it = set_difference(vv.begin(), vv.end(), v2.begin(), v2.end(), v3.begin());
    int size = 4 -(v3.end() - it);
    v3.resize(size);
    for_each(v3.begin(), v3.end(), [](int a){ cout << a << endl;});
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

C++ STL库的介绍和使用（下）