C++ STL

简介: C++ STL

C++ STL

概述

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

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

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

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

数据结构 说明 头文件
向量vector 连续存放数据,底层为数组,支持快速随机访问 <vector>
字符串string 字符串 <string>
双端队列deque 连续存储的指向不同元素的指针所组成的数组。支持首尾元素快速删除,也支持随机访问 <deque>
链表list 由节点组成的链表,每个节点包含着一个元素。底层结构为双向链表,支持结点的快速删除。 <list>
栈stack 先进后出 <stack>
队列queue 先进先出 <queue>
优先队列priority_queue 元素的进出队顺序由关系函数决定。底层结构一般为vector或者deque <queue>
集合set/ 多重集合multiset 结点组成的红黑树,每个节点包含一个元素,set中的所有元素有序但是不重复,multiset中的所有关键字有序但是可以重复 <set>
映射map/多重映射multimap 由键值对组成的集合,底层数据结构为红黑树,map中的所有关键字有序但是不重复,multimap中的所有关键字有序但是可以重复 <map>

使用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. 自定义关系函数,需要重载() 运算符,也需要指定底层容器。
相关文章
|
2月前
|
存储 算法 C++
C++ STL 初探:打开标准模板库的大门
C++ STL 初探:打开标准模板库的大门
112 10
|
4天前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构,适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码,读者可以更好地理解如何使用这些接口。最后,作者总结了`list`的特点和适用场景,并预告了后续关于`list`模拟实现的文章。
20 7
|
21天前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器,包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组,能够根据需要自动调整大小,提供了丰富的操作接口,如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后,还展示了如何使用`vector`创建字符串数组,体现了`vector`在实际编程中的灵活性和实用性。
47 4
|
23天前
|
C语言 C++ 容器
【c++丨STL】string模拟实现(附源码)
本文详细介绍了如何模拟实现C++ STL中的`string`类,包括其构造函数、拷贝构造、赋值重载、析构函数等基本功能,以及字符串的插入、删除、查找、比较等操作。文章还展示了如何实现输入输出流操作符,使自定义的`string`类能够方便地与`cin`和`cout`配合使用。通过这些实现,读者不仅能加深对`string`类的理解,还能提升对C++编程技巧的掌握。
48 5
|
23天前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色,它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作,帮助读者更好地理解和掌握`string`类的应用。
36 2
|
28天前
|
存储 算法 Linux
【c++】STL简介
本文介绍了C++标准模板库(STL)的基本概念、组成部分及学习方法,强调了STL在提高编程效率和代码复用性方面的重要性。文章详细解析了STL的六大组件:容器、算法、迭代器、仿函数、配接器和空间配置器,并提出了学习STL的三个层次,旨在帮助读者深入理解和掌握STL。
46 0
|
7天前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理,并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表,使用三个迭代器(指针)来维护数组,分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码,帮助读者更好地理解和掌握 `vector` 的实现细节。
18 0
|
2月前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
58 2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
|
2月前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
79 5
|
2月前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
70 1