[C++知识库]C++常用STL

STL

• vector 变长数组，倍增的思想
• string 字符串，substr(), c_str() 返回str对应的字符数组的头指针
• queue 队列push() front() pop() back()
• priority_queue 优先队列，push(), top(), pop()
• stack 栈 push()，top(), pop()
• deque 双端队列 队头队尾都可以插入删除，支持随机访问
• set map multiset multimap 基于平衡二叉树（红黑树），动态维护有序序列
• unordered_set unordered_map unordered_multiset unordered_multimap 基于哈希表
• bitset 压位

vector

    // 初始化
    vector<int> a(10);  // 初始化长度为10的向量,默认元素为0
    vector<int> b(10,3);    // 长度为10，元素都为3
    
    // 所有容器都有size和empty，有个变量来存，时间复杂度O(1)
    a.size();       // 元素个数
    a.empty();      // 是否为空

    a.clear();      // 清空后元素个数为0
    a.front();		// 返回第一个数
    a.back();		// 返回最后一个数
    a.push_back(5);	// 在最后增加一个数
    a.pop_back();	// 弹出最后一个数
    a.begin(),a.end();  // 迭代器，第0个数a[0]，最后一个数的后面一个位置a[a.size()]

    b.erase(b.begin()+2,b.begin()+4);	// 删除中间的元素

[] —— 可以用数组下标访问vector元素

支持比较运算，按照字典序

三种遍历方式

// 数组下标
for(int i = 0;i<a.size();i++){
	cout<<a[i]<<' ';
}
// 迭代器
for(vector<int>::iterator i = a.begin();i!=a.end();i++){
    cout<<*i<<" ";
}
// c++增加
for(auto x:a)cout<<x<<" ";

pair

#include

pair<int,string>p;

• p.first ——第一个元素

• p.second —— 第二个元素

构造

    pair<int,string>pair1;      // 注意没有括号
    pair<int,string>pair2(1,"abc");
    pair<int,string>pair3 = make_pair(22,"zzz");
    pair<int,string>pair4 = {66,"No"};
    pair4.first = 66;		// 对first 和 second再进行修改
    pair4.second = "yes";
    pair4.first = 100;

比较

支持比较运算，按照字典序以first为第一关键字，second为第二关键字，先比较first，再比较second，两个均相同才相等

交换

swap(p1,p2);

扩展元素

pair<int,pair<int,int>>p;	// 用pair存储三个属性

排序

我们可以直接使用sort对pair进行排序，按照first排序

sort(p,p+N,cmp);
bool cmp(pair<int,int>p1,pair<int,int>p2){
	if(p1.first>p2.first){
		return true;
	}
	else if(p1.first==p2.first && p1.second >p2.second){
		return true;
	}
	else{
		return false;
	}
}

string

string str;
str.size();
str.empty();
str.clear();
str += "abc";
str +='a';
str.substr(1,2);	// 获取子串(begin,len);如果长度超过子串末尾，就只输出到末尾

printf字符串

对比：

    string str = "abc";
    char ch[] = "hello";
    printf("%s\n",str.c_str());
    printf("%s\n",ch);

queue

queue<int>q;
q.push(x);
q.front();
q.back();
q.pop();
q.size();
q.empty();
// 没有clear

遍历输出队列

queue<int>q;
q.push(1);
q.push(2);
q.push(999);
while(!q.empty()){
    cout<<q.front()<<" ";
    q.pop();
}

priority_queue

默认大根堆

push();		// 插入一个元素
top();	// 返回堆顶元素
pop();	// 弹出堆顶元素

priority_queue<int>heap;	// 定义一个大根堆

要实现小根堆：

• 插入原数的相反数，取出的时候也要取反

• 初始化增加两个参数

  priority_queue<int,vector<int>,greater<int>>heap;
  

stack

size();
empty();
// 没有clear()
push();
top();
pop();

deque 双端队列

支持再两端高效插入或删除元素的连续线性存储空间

• 在头部增删元素o(1)
• 支持随机访问

效率低

deque<int>dq;
dq[1];	// 
size();
empty();
clear();
front();
back();
push_back();	// 队尾入队
pop_back();		// 队尾出队
push_front();	// 队头入队
pop_front();	// 队头出队
begin()/end();	

set map multiset multimap

有序序列 ——自动按照键的大小进行排序 —— 存入的元素必须定义“小于号”运算符

• size()
• empty()
• clear()
• begin() / end() ++ – 返回前驱和后继

set+multiset

• set中不能有重复元素
• multiset 可以有重复元素

set 和 multiset: 所有操作是O(logn)

• begin()/end() —— 返回最小的元素/最大的元素的迭代器（前闭后开）

• insert(x)

• 查找

  • find(x) 如果不存在就返回end迭代器
  • lower_bound() 返回大于等于x中 最小的数的迭代器
  • upper_bound() 返回大于x中 最小的数的迭代器

• count(x) 返回某一个数的个数

• erase()

  • 输入是一个数x，删除所有x O(logn + k)
  • 输入一个迭代器，删除这个迭代器

#include<set>	// 包括set 和 multiset
set<int>s;
multiset<int>ms;

map+multimap

是一个键值对key-value的映射，内部是红黑树，key必须定义"小于号"运算符

• insert() 插入的数是一个pair
• erase() 输入的参数是pair或者迭代器
• find()
• [] 时间复杂度是o(logn) —— 如果不存在会新建一个二元组，value=空
• lower_bound() 返回大于等于x最小的数的迭代器
• upper_bound() 返回大于x最小的数的迭代器

map<string,int> a;
a["zzz"] = 1;
cout<<a["zzz"]<<endl;

遍历案例

	//创建一个空的 map 关联式容器，该容器中存储的键值对，其中键为 string 字符串，值也为 string 字符串类型
    map<string, string> mymap;
    //向 mymap 容器中添加数据
    mymap["http://c.biancheng.net/c/"] = "C语言教程";
    mymap["http://c.biancheng.net/python/"] = "Python教程";
    mymap["http://c.biancheng.net/java/"] = "Java教程";
    //使用 map 容器的迭代器，遍历 mymap 容器，并输出其中存储的各个键值对
    for (map<string, string>::iterator it = mymap.begin(); it != mymap.end(); ++it) {
        //输出各个元素中的键和值
        cout << it->first << " => " << it->second << '\n';
    }
    for(auto it:mymap){
         cout << it.first << " => " << it.second << '\n';
    }

自定义排序

    map<int,string>mymap = {{11,"zbc"},{22,"abc"},{15,"hhh"}};		// 默认从小到大
    map<int,string,less<int>>mymap2 = {{11,"zbc"},{22,"abc"},{15,"hhh"}};		// 从小到大
    map<int,string,greater<int>>mymap3 = {{11,"zbc"},{22,"abc"},{15,"hhh"}};		// 从大到小
    for(auto x:mymap){
        cout<<x.first<<" "<<x.second<<endl;
    }
    cout<<endl;
    for(auto x:mymap2){
        cout<<x.first<<" "<<x.second<<endl;
    }
    cout<<endl;
    for(auto x:mymap3){
        cout<<x.first<<" "<<x.second<<endl;
    }

迭代器

map 的迭代器是双向迭代器（bidirectional iterator）。这意味着，map 容器迭代器只能进行 ++p、p++、–p、p–、*p 操作，并且迭代器之间只能使用 == 或者 != 运算符进行比较。

find

int main() {
    //创建并初始化 map 容器
    std::map<std::string, std::string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},
                                             {"C语言教程","http://c.biancheng.net/c/"},
                                             {"Java教程","http://c.biancheng.net/java/"} };
    //查找键为 "Java教程" 的键值对
    auto iter = myMap.find("Java教程");
    //从 iter 开始，遍历 map 容器
    for (; iter != myMap.end(); ++iter) {
        cout << iter->first << " " << iter->second << endl;
    }
    return 0;
}

lower_bound 和 upper_bound -更多用于 multimap 容器，在 map 容器中很少用到

    map<int,string>mymap = {{11,"zbc"},{22,"abc"},{15,"hhh"}};
    for(map<int,string>::iterator it = mymap.lower_bound(15);it!=mymap.end();it++){	// 包含15
        cout<<it->first<<" "<<it->second<<endl;
    }
    for(map<int,string>::iterator it = mymap.upper_bound(15);it!=mymap.end();it++){	// 不包含15
        cout<<it->first<<" "<<it->second<<endl;
    }

equal_range- 更多用于 multimap 容器，在 map 容器中很少用到

    map<int,string,greater<int>>mymap = {{11,"zbc"},{22,"abc"},{15,"hhh"}};
    pair<map<int,string>::iterator,map<int,string>::iterator>ret = mymap.equal_range(15);
    for(auto x = ret.first;x!=ret.second;x++){
        cout<<x->first<<" "<<x->second<<endl;
    }

获取键对应值

• mymap[key] 可以返回value ——如果有就返回，没有就会创建，且value = 0
• mymap.at(key) 可以返回value ——如果有就返回，没有就会抛出异常

插入元素

• []

• insert

  • insert(pair1)
  • insert({1,"abc})
  • insert(first迭代器, last迭代器); ——插入其他map的内容

  返回值：pair<map<int,string>::iterator,bool> 迭代器表示插入的键值对的迭代器（如果原来存在相同的键，仍然指向原来的），bool表示是否插入成功

      map<int,string>mymap;
      pair<int,string>p1 = {1,"abz"};
      pair<map<int,string>::iterator,bool>ret;
  
      ret = mymap.insert(p1);
      cout<<ret.first->first<<" "<<ret.first->second<<" "<<ret.second<<endl;
  
      ret = mymap.insert({2,"zzz"});
      cout<<ret.first->first<<" "<<ret.first->second<<" "<<ret.second<<endl;
  
      ret = mymap.insert({2,"yes"});
      cout<<ret.first->first<<" "<<ret.first->second<<" "<<ret.second<<endl;
      for(auto x:mymap){
          cout<<x.first<<" "<<x.second<<endl;
      }
  

  1 abz 1
  2 zzz 1
  2 zzz 0		// 插入失败，指向原来的
  1 abz
  2 zzz
  

unordered_set unordered_map unordered_multiset unordered_multimap

和上面类似，增删改查的时间复杂度是o(1)

不支持和排序相关的操作，不支持lower_bound()、upper_bound()

bitset

占用的空间是布尔数组/8

bitset<10000>s;		// 大小为10000
~ & | ^
>>  <<
== !=
// --- 判断相关----    
[] // 取出某一位
count()		// 返回有多少个1
any() 	// 判断是否至少有一个1
none()	// 判断是否全为0
    
// --- 设置相关----
set()	// 把所有位置变成1
set(k,v)	//把第k位变成v
reset()		//把所有位置变成0
flip()		// 所有位取反，s = ~s
flip(k)		// 把第k位取反，s[k]^=1

这几个函数很像触发器：置位、清零、反转

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系