c++ 高级部分 STL 容器

STL，英文全称 standard template library，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入/输出、数学计算等功能。

STL 最初由惠普实验室开发，于 1998 年被定为国际标准，正式成为 C++ 程序库的重要组成部分。值得一提的是，如今 STL 已完全被内置到支持 C++ 的编译器中，无需额外安装，这可能也是 STL 被广泛使用的原因之一。

从根本上说，STL 是一些容器、算法和其他一些组件的集合，所有容器和算法都是总结了几十年来算法和数据结构的研究成果，汇集了许多计算机专家学者经验的基础上实现的，因此可以说，STL 基本上达到了各种存储方法和相关算法的高度优化。

Vector 数组

数组的特征：只能保存相同类型的数据、内存连续，数据具备索引，根据索引查找快，增、删慢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int main() {
    cout << "STL 标准模版库 容器学习1 Vector" << endl;
    vector<int>vector1; // 创建数组
    vector<int>vector2(8); // 创建8个容量的数组
    vector<int>vector3(10, -1); // 创建10个容量的数组，且默认值都是 -1
    // 遍历
    int i = 0;
    for(i = 0; i < vector3.size(); i ++) {
        // 修改值
        vector3[i] = i;
        cout << "i:" << i << " value:" << vector3[i] << endl;
    }
    // 插入值
    // 从头部插入
    vector1.insert(vector1.begin(), 40);
    vector1.insert(vector1.begin(), 30);
    vector1.insert(vector1.begin(), 20);
    vector1.insert(vector1.begin(), 10);
    // 从尾部插入
    vector1.insert(vector1.end(), 99);
    
    // 使用迭代器遍历
    for(vector<int>::iterator ite = vector1.begin(); ite != vector1.end(); ite ++) {
        // 迭代器获取的是地址
        cout << "迭代器遍历" << *ite << endl;
    }
    
    // 因为vector2在构造函数中申明了容量为8，此时不能进行插入或者删除操作。会报错
//    vector2.insert(vector2.begin(), 22);
//    vector2.insert(vector2.end(), 33);
//    vector2.insert(vector2.begin(), 44);
//    vector2.insert(vector2.begin(), 44);
//    vector2.insert(vector2.begin(), 22);
//    vector2.insert(vector2.end(), 33);
//    vector2.insert(vector2.begin(), 44);
//    vector2.insert(vector2.begin(), 44);
    // 删除尾部
//    vector2.erase(vector2.end());
//    // 删除头部
//    vector2.erase(vector2.begin());
    //  迭代器自动推导类型 类似于kotlin
    for(auto iter = vector2.begin(); iter != vector2.end(); iter++) {
        *iter = 88;
        cout << "自动推导迭代器遍历" << *iter << endl;
    }
    return 0;
}

stack 栈

栈的数据特点：先进后出、后进先出，类似于方法栈进栈、出栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main() {
    cout << "STL stack 栈的学习" <<endl;
    // 初始化
    stack<int> stack1;
    // 压栈
    stack1.push(1);
    stack1.push(2);
    stack1.push(20);
    stack1.push(22);
    // 弹栈
    stack1.pop();
    cout << "栈顶元素:" << stack1.top() << endl;
    // 栈没有迭代器，也没有索引 这样遍历的话，会将栈内元素都弹出。
    while (!stack1.empty()) {
        cout << "遍历栈元素：" << stack1.top() << endl;
        stack1.pop();
    }
    return 0;
}

压栈、弹栈函数都是没有返回值的，
top函数获取栈顶元素

queue 队列

队列的数据特点： FIFO 先进先出，后进后出。与栈不同
队列内部可以使用数组实现、也可以使用链表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
    cout << "STL 三 队列queue学习" << endl;
    queue<int> que;
    que.push(1);
    que.push(2);
    que.push(3);
    
    cout << "队列队头元素：" << que.front() << endl;
    cout << "队列队尾元素" << que.back() << endl;
    // 队列也是没有迭代器的，只能采用与栈相同的方式遍历数据
    while (!que.empty()) {
        cout << "遍历 队列队头元素：" << que.front() << endl;
        que.pop();
    }
    return 0;
}

优先级队列

优先级队列是队列的一个子集，内部数据结构通过数组实现，而且是数据有序排练，默认是降序。
不论数据push的顺序，直接给你降序处理，可以设置成升序排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main() {
    cout << "STL 三 优先级队列priority_queue学习" << endl;
    // 默认是降序排列
//    priority_queue<int> que;
    // 设置成升序排列
    priority_queue<int, vector<int>, greater<int>>que;
    
    que.push(20);
    que.push(50);
    que.push(60);
    que.push(30);
    que.push(10);
    que.push(70);
    
    while (!que.empty()) {
        cout << "遍历 优先级队列队头元素：" << que.top() << endl;
        que.pop();
    }
    return 0;
}

list 链表

链表的数据特点，内存非连续，每个节点有下一个节点的指针，增删快，但查询慢，增加、删除都只能在表头操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int main(){
    cout << "STL 四 链表list学习" << endl;
    list<int> listArr;
    // push
    listArr.push_front(11); // 从链头添加一个值
    listArr.push_back(80); // 从链尾添加一个值
    // 插入
    listArr.insert(listArr.end(), 99); // 插入一个值到链尾
    listArr.insert(listArr.end(), 98); // 插入一个值到链尾
    listArr.insert(listArr.begin(), 20); // 插入一个值到链头
    listArr.insert(listArr.begin(), 22); // 插入一个值到链头
    
    // 删除
    listArr.erase(listArr.begin());
//    listArr.erase(listArr.end()); // 这一句在运行时报错，不知道为何
    
    // 使用迭代器遍历
    for(list<int>::iterator it = listArr.begin(); it != listArr.end(); it++) {
        cout << "链表迭代器遍历：" << *it << endl;
    }
    // 清除所有元素
    listArr.clear();
    cout << "clear" << endl;
    for(list<int>::iterator it = listArr.begin(); it != listArr.end(); it++) {
        cout << "链表迭代器遍历：" << *it << endl;
    }
    
    return 0;
}

set 红黑树

内部结构 红黑树 会对你存入的数据进行排序，但是绝对不允许元素相同

默认会升序排列，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int main() {
    cout << "STL 五 set 学习" << endl;
    set<int>setV;
    // 插入值
    // 默认会升序排列
    setV.insert(80);
    setV.insert(70);
    setV.insert(50);
    setV.insert(90);
    
    // 当插入已经存在的值时，会失败，因为不允许重复
    pair<set<int, less<int>>::iterator, bool> result = setV.insert(60);
    // 注意set的insert函数是有返回值的，first是迭代器 second是插入的结果
    if(result.second) {
        // 插入成功
        cout << "插入成功" << endl;
        // 注意此处取得的迭代器不是从begin开始，而是从插入的值60处开始的。
        for(; result.first != setV.end(); result.first ++) {
            cout << "插入结果迭代器遍历的值:" << * result.first << endl;
        }
    } else {
        cout << "插入失败" << endl;
    }
    
    // 迭代器遍历
    for(set<int>::iterator it = setV.begin(); it != setV.end(); it ++) {
        cout << "迭代器遍历的值:" << * it << endl;
    }
    return 0;
}

谓词

转自：https://www.cnblogs.com/xym4869/p/12250174.html

1.函数(function)谓词
通过传递函数名, 匹配二元谓词(binary predicates), 根据函数提供的策略, 输出值;

1
2
3
4
5
/*Function Predicate*/
bool isLarger (const std::string &s1, const std::string &s2) {
	return s1.size() > s2.size();
}
std::stable_sort(sv.begin(), sv.end(), isLarger);

2.函数指针(function pointer)谓词
建立一个函数指针, 传入算法, 使用指针代替函数名, 用法类似函数谓词.

1
2
3
bool (*pf) (const std::string &s1, const std::string &s2);
pf = &isLarger;
std::stable_sort(sv.begin(), sv.end(), *pf);

3.Lambda表达式(lambda expression)谓词
Lambda表达式格式: [capture list] (parameter list) -> return type { function body }
需要匹配谓词数, 一元(unary) 或 二元(binary), 也可以通过[capture list]传递函数的变量;

1
2
std::stable_sort(sv.begin(), sv.end(),
    [](const std::string& s1, const std::string& s2){ return s1.size()>s2.size(); });

4.函数对象(Function Object)谓词
类中重载函数的调用”()”, 使类可以被调用, 并且传入算法谓词中, 进行使用.

1
2
3
4
5
6
7
8
9
/*Function Object*/
class LargerString {
public:
	bool operator() (const std::string& a, const std::string& b) {
		return a.size() > b.size();
	}
};
......
std::stable_sort(sv.begin(), sv.end(), LargerString());

5、结构体谓词

1
2
3
4
5
6
7
8
9
10
11
12
13
// 真正的谓词
struct doCompareAction2 {
public:
    bool operator() (const Person& __x, const Person& __y) {
        return __x.id < __y.id;
    }
};

int main() {

    set<Person, doCompareAction2> setVar;
    return 0;
}

map

map: key value键值对容器，默认会对key进行排序，所以不能存在重复的key，会添加失败 value可以重复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int main(){
    cout << "STL 六 map学习" << endl;
    map<int, string>mapVar;
    // 插入值 需要借助 std::pair
    mapVar.insert(pair<int, string>(1, "justin"));
    mapVar.insert(pair<int, string>(5, "justinA"));
    mapVar.insert(pair<int, string>(3, "justin"));
    // 使用迭代器遍历
    for(map<int, string>::iterator it = mapVar.begin(); it != mapVar.end(); it++) {
        cout << "key:" << it->first << " value:" << it->second <<endl;
    }
    // 获取插入值的结果
    pair<map<int,string>::iterator, bool> result = mapVar.insert(pair<int, string>(4, "novia"));
    if(result.second) {
        cout << "插入值成功" << endl;
        // 因为有排序，只会遍历从4以及4以后的元素
        for(; result.first != mapVar.end(); result.first ++) {
            cout << "key:" << result.first->first << " value:" << result.first->second <<endl;
        }
    } else {
        cout << "插入值失败" << endl;
    }
    // 查询 是根据key查询的
    map<int, string>::iterator findResult = mapVar.find(3);
    if(findResult != mapVar.end()) {
        cout << "已找到" << findResult -> first << ", " << findResult->second.c_str() << endl;
    } else {
        cout << "查找key失败" << endl;
    }
    
    return 0;
}

multimap

multimap 属于 map下的子集
// 1.key可以重复， 2.key重复的数据可以分组, 3.key会排序， 4.value不会排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int main(){
    cout << "STL 七 multimap学习" << endl;
    multimap<int, string>multimapVar;
    
    multimapVar.insert(make_pair(10, "justin"));
    multimapVar.insert(make_pair(10, "novia"));
    multimapVar.insert(make_pair(10, "justin"));
    
    multimapVar.insert(make_pair(20, "justin"));
    multimapVar.insert(make_pair(20, "novia"));
    multimapVar.insert(make_pair(20, "coco"));
    
    multimapVar.insert(make_pair(30, "justin1"));
    multimapVar.insert(make_pair(30, "justin2"));
    multimapVar.insert(make_pair(30, "justin3"));
    
    for(multimap<int, string>::iterator it = multimapVar.begin(); it != multimapVar.end(); it++) {
        cout << it->first << ", " << it -> second << endl;
    }
    
    // TODO 核心功能是分组
    int result;
    cout << "请输入你要查询的key，为int类型:" << endl;
    cin >> result;

    multimap<int, string>::iterator iteratorVar = multimapVar.find(result);
    while (iteratorVar != multimapVar.end()) {
        cout << iteratorVar->first << "," << iteratorVar->second << endl;
        // 需要自己做逻辑控制，不然有问题
        iteratorVar++;
        if (iteratorVar->first != result) {
            break;; // 循环结束
        }
        // 严谨性
        if (iteratorVar == multimapVar.end()) {
            break;; // 循环结束
        }
    }
    
    return 0;
}

防函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class TestForEach{
public:
    int size = 0;
    void _size() {
        cout << "size：" << size << endl;
    }
    void operator()(int content) {
        cout << "自定义防函数" << content << endl;
        size++;
    }
};

void fake(int content) {
    cout << "自定义函数" << content << endl;
}

int main(){
    cout << "防函数学习" << endl;
    TestForEach forEach;
    
    set<int>setVar;
    setVar.insert(10);
    setVar.insert(20);
    setVar.insert(500);
    setVar.insert(40);
    setVar.insert(30);
    setVar.insert(50);
    setVar.insert(60);
    
    // set 红黑树本身没有没有记录size，我们可以通过防函数记录
    // for_each是有返回值的，返回值是 防函数本身
    for_each(setVar.begin(), setVar.end(), fake);
    forEach = for_each(setVar.begin(), setVar.end(), forEach);
    forEach._size();
    
    return 0;
}

在源码中有很多防函数的使用，其实我们自己可以手动实现一个防函数，并替换源码中的 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 自定义加法
template<typename T>
struct plus_d
{
    T operator() (const T & x, const T & y){
        return x + y;
    }
};

int main(){
    cout << "自定义实现算法" << endl;
    // 使用系统自带的加法
    plus<int>sum_int;
    cout << "int相加" << sum_int(1,2) << endl;
    plus<string>sum_str;
    cout << "字符相加" << sum_str("AAA","BBB") << endl;
    
    // 接下来自己实现加法
    plus_d<float>sum_flo;
    cout << "自定义 float相加" << sum_flo(1.78f, 2.56f) << endl;
    
    plus_d<string>sum_s;
    cout << "自定义 字符相加" << sum_s("justin ", "and novia") << endl;
    
    return 0;
}

关于模版函数

1
2
3
4
5
6
7
// 定义模版 Params1 第一个参数类型 Params2 第二个参数类型 ReturnType 返回值类型
template<typename Params1, typename Params2, typename ReturnType>
struct binary_function{
    typedef Params1 first_argument_type; // 第一个参数的别名
    typedef Params2 second_argument_type; // 第二个参数的别名
    typedef ReturnType result_type; // 返回值别名
};