C++ STL

C++ STL

概述

STL主要有container , algorithm和iterator三大部分构成

• 容器用于存放数据对象
  
• 算法用于操作容器中的数据对象
  
• 迭代器是算法和容器之间的中介
  

STL容器

STL容器是一种数据结构，例如链表、栈和队列等

STL常用数据结构和头文件：

使用STL需要引入命名空间: std

STL算法

STL算法是用来操作容器中数据的模板函数，大概提供了100个实现算法的模板函数。

使用泛型设计，STL算法有很好的通用性

STL算法主要由头文件<algorithm>、<numeric> 和<functional>组成

• <algorithm>是所有STL头文件中最大的一个，由一大堆模板函数组成，涉及容器元素的比较，排序，查找，遍历，复制，删除，修改等等
• <numeric> 体积很小，只包含几个简单的数学运算的模板函数
• <functional>中定义了一些模板类，用于声明关系函数对象

STL迭代器

STL迭代器用于访问容器中的数据对象。

每个容器都有自己的迭代器，只有容器自己知道如何访问自己的元素。算法通过迭代器来定位和操作容器中的元素

迭代器操作符：

• ++ 递增迭代器，访问下一个数据对象
• – 递减迭代器
• *返回迭代器所指的元素值

常用迭代器

• iterator
  指向容器中存放元素的迭代器，用于正向遍历容器中的元素
  
• const_iterator
  指向容器中存放元素的常量迭代器，只能读取元素
  
• reverse_iterator
  指向容器中存放元素的反向迭代器，反向遍历元素
  
• const_revserse_iterator
  指向容器中存放元素的常量反向迭代器，只能读取元素
  

常用的STL容器

每一个容器都是一个类模板

大致分类为顺序容器、关联容器、适配器容器

• 顺序容器
  按照线性次序的位置存储数据，有: vector, string, deque, list
  
• 关联容器
  每一个元素有一个key,通过key 来存储和读取元素，与元素在容器中的位置无关，所以关联容器不提供front(), push_front() ,back()…
  
• 适配器容器
  基于其他容器实现的容器，适配器容器包含另一个容器作为其底层容器，在底层容器的基础上实现适配器容器的功能。
  

vector向量容器

相当于数组，存储具有相同数据类型的一组元素。

可以随机访问元素，但是插入、删除元素较慢。

可以动态增加大小 --> 通常按照两倍大小扩展

定义

vector<int> v1; 
vector<int> v2(10);  // 初始大小为10
vector<int> v3(10,1); // 初始大小为10，每个元素的初始值为1
vector<int> v4(a,a+5); // 用数组a[0..4] 共5个元素初始化v4

成员函数

• empty() 判断是否为空
• size() 实际元素的个数
• [] 返回指定下标的元素
• reserve(n) 为当前vector预分配n个元素的存储控件
• capacity() 返回容量
• resize(n) 调整大小
• push_back() 向尾部添加一个元素
• insert(pos,elem) 在pos位置添加一个元素
• front() 获取第一个元素
• back() 获取最后一个元素
• erase() 删除某个迭代器或者迭代器区间指定的元素
• clear() 清空
• begin() 引用容器的第一个元素
• end() 引用容器的最后一个元素后面的位置
• rbegin() 引用容器的最后一个元素
• rend() 返回容器第一个元素前面的一个位置

string 字符串容器

保存字符序列的容器，所有元素为字符类型， 类似vector<char>

定义

string(); // 建立一个空的字符串
string(const string & str) ; // 用字符串str建立当前的字符串
string(const string & str,size_type str_idx); // 用字符串str起始于str_idx的字符建立当前字符串
string(const string & str,size_type str_idx,size_type str_num); // 用字符串str起始于str_idx 的str_num 个字符建立当前字符串
string(const char * cstr); // 用c字符串cstr建立当前字符串
string(const char * cstr,size_type chars_len); // 用c字符串cstr开头的chars_len 个字符建立当前字符串
string(size_type num,char c); // 用num个字符c建立当前字符串

成员函数

• empty()
• size()
• length()
• [idx] 返回索引idx位置上的字符
• at(idx)
• compare(const string& str) 返回比较结果，相等返回0
• append(str) 在字符串的末尾添加一个字符串str
• insert(size_type idx,const string & str) 在当前字符串idx处插入一个字符串str
• find(string & s, size_type pos) 从pos位置开始查找字符串s的第一个位置，没有返回-1
• replace(size_type idx,size_type len,const string & str) 将字符串起始于idx的len个字符用一个字符串str替换
• replace(iterator beg,iterator end,const string& str) 将当前字符串中有迭代器beg和end指向区间的所有字符用一个字符串str替换
• substr(size_type idx) 返回当前字符串起始于idx的子串
• substr(size_type idx,size_type len) 返回当前字符串起始于idx的长度为len 的子串
• clear()
• erase() 删除所有字符串
• erase(size_type idx) 删除从idx开始的所有字符
• erase(size_type idx,size_type len) 删除从下标idx开始的len个字符

deque双端队列

块内连续，块间不连续

定义

deque<int> dq;
deque<int> dq(10);
deque<int> dq(10,1); // 10个元素，每个元素的初值都是1
deque<int> dq(dq1.begin(),dq1.end())  // 使用dq1的元素初始化dq

成员函数

• empty()
• size()
• push_front(elem)
• push_back(elem)’
• pop_front()
• pop_back()
• erase()
• clear()
• begin()
• end()
• rbegin()
• rend()

list链表容器

定义

list<int> l1;
list<int> l2(10);
list<int> l3(10,1);
list<int> l4(a,a+5); // 使用数组a[0..4] 共5个元素初始化l4

成员函数

• empty()
• size()
• push_back()
• pop_back()
• remove() 删除链表容器中所有指定值的元素
• remove_if(cmp) 删除链表容器中满足条件的元素
• erase()
• unique() 删除链表容器中相邻的重复元素
• clear()
• insert(pos,elem)
• insert(pos,n,elem) 在pos位置插入n个elem
• insert(pos,pos1,pos2) 在迭代器pos处插入[pos1,pos2)的元素
• reverse() 反转链表
• sort() 排序
• begin()
• end
• rbegin()
• rend()

STL提供的sort() 算法主要用于支持随机访问的容器，list容器不支持随机访问，为此list容器提供了sort() 成员函数用于元素排序

set 集合/ multiset多重集合容器

• set中的关键字是唯一的
  在插入元素时，如果已经存在则不插入
  
• multiset 中的关键字可以不唯一
  允许存在相同关键字的元素，删除时会将相同关键字的元素都删除，并返回删除个数
  

默认情况下会对元素按照关键字自动进行升序排列,同时支持交，差，并等集合运算

成员函数

• empty()
• size()
• insert()
• erase()
• clear()
• count(k) 返回容器中关键字k出现额次数
• find(k) 如果存在关键字k的元素，返回该元素的迭代器，否则返回end()值
• upper_bound() 返回一个迭代器，指向关键字大于k的第一个元素
• lower_bound()
• begin()
• end()
• rbegin()
• rend()

map映射/multimap多重映射容器

实现关键字与值映射，可以使用一个关键字key来访问响应的数据值

map/multimap中的key和value是一个pair类结构

struct pair{
    T first;
    T second;
}

map/multimap 可以根据key快速找到与之对应的value( 时间复杂度 O(log2(n)) )

• map中不允许key重复，支持[]运算符
• multimap允许key重复， 但是不支持[] 运算符

成员函数

• empty()
• size()
• map[key] 返回关键字为key的元素的引用，如果不存在这样的关键字，则以key作为关键字插入一个元素( 不适合multimap )
• insert(elem) 插入一个元素并返回该元素的位置
• clear()
• find()
• count() 容器中指定关键字的元素个数，map中只有1 和 0
• begin()
• end()
• rbegin()
• rend()

map<char,int> mymap;
mymap['a'] = 1;

stack 栈容器

后进先出

默认底层是deque容器，也可以指定底层容器

// 指定底层容器为vector, 第二个参数指定底层容器
stack<string,vector<string>> myst;

stack容器只有一个出口–>栈顶，可以在栈顶插入，删除元素，不允许顺序遍历

成员函数

• empty()
• size()
• push(elem)
• top() 返回栈顶元素
• pop()

queue队列容器

先进先出

不允许顺序遍历

成员函数

• empty()
• size()
• front() 返回队头元素
• back() 返回队尾元素
• push(elem) 入队
• pop() 出队

priority_queue优先队列容器

优先队列中元素，出队将按照优先级的高低。

成员函数

• empty()
• size()
• push(elem) 元素进队
• top() 获取队头元素
• pop() 出队

优先队列中优先级的高低由队列中数据元素的关系函数(比较运算符) 确定

• 默认的关系函数-> 对于内置数据类型，默认关系函数是值越大优先级越高 --> 大根堆
  
• 可以重载自定义关系函数

//1. 重载“<”操作符来定义优先级
//定义结构体
struct info{
    string name;
    float score;
    //重载< 操作符，指定优先级规则(排序规则)
    bool operator < (const info & a)const{
    //按从小到大排序(原本是< ,现在的功能是>)
       return score > a.score;
    }
};
// priority_queue<info> pq;

//2. 重载“()”操作符来定义优先级
/重载()
struct myComp{
    bool operator () (const int &a,const int& b){
    //由小到大
        return a>b;
    }
};
//定义优先队列,显式说明内部结构是vector
//priority_queue<int,vector<int>,myComp> pq;

STL的使用

stack的使用

判断一个含有(), [],{} 3中类型的表达式中所有的括号是否匹配

分析：所有的右括号都是和前面最近的左括号匹配

#include <iostream>
#include <stack>
using namespace std; 
// 判断str中的括号是否匹配
bool solve(string str){
    stack<char> st;
    int i = 0;
    while(i < str.length()){
    if(str[i] == '(' || str[i] == '{' || str[i] == '['){
      st.push(str[i]);
        }else if(str[i] == ')'){
            if(st.top() != '('){
        return false;
            }else{
                st.pop();
            }
        }else if(str[i] == '}'){
      if(st.top()!='{'){
                return false;
            }else{
        st.pop();
            }
      }else if(str[i] == ']'){
          if(st.top()!='['){
        return false;
            }else{
                st.pop();
            }
        }
      i++;
    }
    
  if(st.empty()){
    return true;
    }else{
        return false;
    }
}

排序

对于list 容器中的元素可以使用成员函数sort()

对于数组或者vector等具有随机访问特定的容器可以使用STL算法sort()

内置数据类型排序

sort() 默认以less<T>小于关系函数作为关系函数实现递增排序。

为了实现递减排序需要调用<functional> 头文件中定义的greater类模板

// 递减排序
sort(myv.begin(),myv.end(),greater<int>());

less<T> ，greater<T> 均属于STL关系函数对象，分别支持对象之间的小于，大于比较，返回布尔值。

包含在functional头文件中

自定义数据类型排序

• 重载 < 运算符，以实现按指定成员的递增或者递减排序

// 递增
bool operator <(const Stud& s) const {
    return no<s.no;
}

• 自定义关系函数，实现按照指定成员的递增或者递减排序

重载() 运算符

struct Cmp{
  bool operator()(const Stud &s,const Stud&t) const{
        return s.no < t.no;
    }
}
sort(myv.begin(),myv.end(),Cmp()); // 使用Cmp中的()运算符进行排序

堆

可以采用STL的优先队列来实现堆

优先队列的优先级高低由队列中数据元素的关系函数确定 --> 确定关系

内置数据类型

默认使用less<T> 作为关系函数，值越大优先级越高

可以改为greater<T> 作为关系函数

自定义类型

1. 在声明的结构体类型中重载<运算符，指定优先级
2. 在声明结构体中重载 > 运算符，此时需要指定优先级队列的底层容器和greater<T>
3. 自定义关系函数，需要重载() 运算符，也需要指定底层容器。