C++ STL（一）容器

1. STL简介

STL全称 Standard Template Library(标准模板库),是一个C++软件库。模板是C++的一个重要特征，而标准模板库正是基于此特征。总共有4个组件分别为

• 算法（algorithms）: 算法作用于容器。它们提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作。实质是函数模板。
• 容器（containers）: 容器是用来管理某一类对象的集合。C++ 提供了各种不同类型的容器，比如 deque、list、vector、map 等。实质是类模板。
• 函数对象（functions) ：STL中引入了函数对象，重载了运算符()的类，比常规函数灵活、快速（因为免去了值传递的开销）。
• 迭代器（iterators）: 迭代器用于遍历对象集合的元素。这些集合可能是容器，也可能是容器的子集。使用起来类似指针。

本次首先介绍一下容器

2.STL常用容器

STL容器有两类，一类是序列容器（Sequence containers）另一类是关系容器（Associative containers）。

参考博客

序列容器和关系容器区别在于元素的存储位置，

序列容器元素有固定位置，取决于插入的时间和地点。与元素值无关。

关系容器元素的位置取决于排序准则和元素值，与插入次序无关，与元素值有关。

2.1 序列容器

• vector 也称动态数组
• list 双向链表，STL中唯一支持事务语义
• forward_list list的单链表版本
• deque 双端队列
• array 只能在初始化时指定大小的数组，可以视为内置数组的封装

2.2 关系容器

传入的对象应该实现了==和<运算符,因为排序了，所以查找性能非常好。

• set 不重复元素的集合
• multiset 功能同set但允许重复的元素
• map 关联数组
• multimap 功能同map但允许重复的键值
• 

2.3 容器适配器

• stack 栈
• queue 队列
• priority_queue 有序队列

3.常见容器的使用

3.1 动态数组vector

#include<vector>
#include<iostream>
using namespace std;
int main(){
    //可以初始化，也可以不初始化使用
    vector<int> m;
    vector<int> n(10,0);//创建初始长度为10的动态数组并赋初值为0
    m.push_back(1);//向动态数组添加值
    // 类似于数组，vector也可以使用索引来访问
   	// 尾部增删速度很快,支持随机存储
    cout<<m[0]<<endl;
    m.pop_back();//动态数组删除一个值
    m.size();//size()返回动态数组的长度
    // 大多数时间访问时间是常数时间
    //注意不可以超出长度赋值
    return 0;
}

3.2 集合set

#include<set>
#include<iostream>
#include<string>
using namespace std;
int main(){
    set<string> s;// 存储string的集合
    s.insert("hello world");
    s.insert("one");
    s.insert("one");//插入两次"one"
    s.insert("me");
    cout<<"len:"<<s.size()<<endl;//3
    for(auto i : s){
        cout<<i<<endl;
    }
    //hello world
	//me
	//one
    set<string> t;
    t.insert("b");
    t.insert("a");
    t.insert("c");
    // 元素位置与其值有关，与插入顺序无关
    for(auto i:t){
        cout<<i<<endl;
    }
    //a
    //b
    //c
}

3.3 映射map

#include<map>
#include<string>
#include<iostream>
using namespace std;
int main(){
    // string -> int的映射
    map< string ,int> m;
    // insert以pair形式插入
    m.insert(make_pair("one",1));
    // 类似python dict方式插入
    m["two"]=2;
    // 值得一提的是, 只要被索引且并对应的value不存在的话，会自动创建
    m["zero"];
    for(auto i:m){
        cout<<i.first<<"->"<<i.second<<endl;
    }
    if (m.count("one")){// set 和 map支持count,map是对键值的计数字
        cout<<"one in m"<<endl;
    }
}

3.4 双向队列deque

// deque的同样支持随机存取,但速度仅次于vector，多了一个判断逻辑