IYATT-yx 的博客

ideology and talent - 引序

容器 – C++ STL 基础

By IYATT-yxPosted on Posted in C/C++, 所有
阅读量： 73

最近更新于 2024-05-06 07:59

环境

Debian 11（arm64）

编译器 g++ 10.2.1；编译标准 C++20；参数：-std=c++20 -no-pie -Wall -Werror=return-type -Werror=non-virtual-dtor -Werror=address -Werror=sequence-point -Werror=format-security -Wextra -pedantic -Wimplicit-fallthrough -Wsequence-point -Wswitch-unreachable -Wswitch-enum -Wstringop-truncation -Wbool-compare -Wtautological-compare -Wfloat-equal -Wshadow=global -Wpointer-arith -Wpointer-compare -Wcast-align -Wcast-qual -Wwrite-strings -Wdangling-else -Wlogical-op -Wconversion -g -O0

基本概念

STL 即 Standard Template Library（标准模板库）
STL 广义上分为三类：algorithm（算法）、container（容器）和 iterator（迭代器）
容器存放数据，算法通过迭代器访问容器解决问题
STL 涵盖的头文件：algorithm、deque、functional、iterator、vector、list、map、memory、numeric、queue、set、stack 和 utility

string

构造函数

#include <iostream>

int main()
{
    // 空字符串对象
    std::string s1;

    // 字符串常量初始化
    const char *cs = "hello";
    std::string s2(cs);
    std::string s3("world");

    // 拷贝
    std::string s4(s3);

    // 字符初始化
    std::string s5(5, 'a');

    std::cout << s2 << std::endl;
    std::cout << s3 << std::endl;
    std::cout << s4 << std::endl;
    std::cout << s5 << std::endl;
}

file

赋值

#include <iostream>

int main()
{
    std::string s1;
    s1 = "hello"; // 字符串常量

    std::string s2;
    s2 = s1; // 字符串对象

    std::string s3;
    s3 = 'A'; // 字符

    std::string s4;
    s4.assign("hello"); // 字符串常量

    std::string s5;
    s5.assign("hello", 3); // 前 3 个字符

    std::string s6;
    s6.assign(s5); // 字符串对象

    std::string s7;
    s7.assign(5, 'n'); // 重复 5 个字符

    std::cout << s1 << std::endl;
    std::cout << s2 << std::endl;
    std::cout << s3 << std::endl;
    std::cout << s4 << std::endl;
    std::cout << s5 << std::endl;
    std::cout << s6 << std::endl;
    std::cout << s7 << std::endl;
}

file

拼接

#include <iostream>

int main()
{
    std::string s;

    s += 'a'; // 字符
    s += "Hello"; // 字符串
    s.append("World"); // 字符串
    s.append("123abc", 3); // 前 3 个字符
    s.append(s); // 字符串对象
    s.append(s, 1, 3); // s 从下标 1 开始的 3 个字符

    std::cout << s << std::endl;
}

file

查找和替代

  • int find(const string &str, int pos = 0) const; // 从 pos 开始查找第一次出现 str 的位置

  • int find(const char *s, int pos = 0) const; // 从 pos 开始查找第一次出现 s 的位置

  • int find(const char *s, int pos, int n) const; // 从 pos 开始查找 s 的前 n 个字符第一次出现的位置

  • int find(const char c, int pos = 0) const; // 从 pos 开始查找 c 第一次出现的位置

  • int rfind(const string &str, int pos = npos) const; // 从 pos 开始逆向查找第一次出现 str 的位置

  • int rfind(const char *s, int pos = npos) const; // 从 pos 开始逆向查找第一次出现 s 的位置

  • t rfind(const char *s, int pos, int n) const; // 从 pos 开始逆向查找第一次出现 s 前 n 个字符的位置

  • int rfind(const char c, int pos = npos) const; // 从 pos 开始逆向查找 c 第一次出现的位置

  • string &replace(int pos, int n, const string &str); // 替换从 pos 开始的 n 个字符为 str

  • string &replace(int pos, int n, const char *s); // 替换从 pos 开始的 n 个字符为 s

比较

file

单个字符操作

file

插入和删除

file

获取子串

file

vector

构造函数

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v1; // 空容器
    std::vector<int> v2(5, 10); // 放入 5 个 10
    std::vector v3(v2); // 拷贝 v2
    std::vector v4(v3.begin(), v3.end()); // 拷贝 v3 第一个到最后一个之间的元素（前闭后开）

    for (auto i : v2)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    for (auto i : v3)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    for (auto i : v4)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

file

赋值

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v1, v2, v3;

    v1.assign(5, 10); // 存入 5 个 10
    v2 = v1; // 复制 v1
    v3.assign(v2.begin(), v2.end()); // 将 v2 第一个到最后一个之间的元素拷贝（前开后闭）

    for (auto i : v1)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    for (auto i : v2)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    for (auto i : v3)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

容量和大小

vector 中有容量和大小的概念，大小是实际存放的数据多少，容量是当前申请的内存可以放入多少数据。当再放入数据后的大小会超过容量时，就重新申请一块更大的内存，将原来的数据复制到新的内存空间，再释放掉原来的内存。这也是动态数据实现的基本原理。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v1;
    std::cout << v1.empty() << " " << v1.size() << " " << v1.capacity() << std::endl; // 是否为空；大小；容量
    for (int i = 0; i < 100; ++i)
    {
        v1.push_back(i);
    }
    std::cout << v1.empty() << " " << v1.size() << " " << v1.capacity() << std::endl;

    v1.resize(10); // 设置大小 - 设置的大小小于原来的就剪掉超出的部分，大于原来的就用默认值填充
    std::cout << v1.empty() << " " << v1.size() << " " << v1.capacity() << std::endl;

    v1.resize(12);
    std::cout << v1[11] << std::endl;

    v1.resize(15, 9); // 设置大小 - 不同之处是，大于原来的就用指定值填充，比如这里用 9 填充
    std::cout << v1[14] << std::endl;
}

file

插入和删除

#include <iostream>
#include <vector>

void print(std::vector<int> &v)
{
    for (int i : v)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::vector<int> v;
    for (int i = 0; i < 10; ++i)
    {
        v.push_back(i); // 尾部插入
    }
    v.pop_back(); // 尾部删除一个元素

    v.insert(v.begin() + 3, 100); // 下标 3 位置（迭代器）插入 100
    print(v);

    v.insert(v.begin() + 1, 5, 10); // 1 位置插入 5 个 10
    print(v);

    v.erase(v.end() - 1); // 删除最后一个位置的数据
    print(v);

    v.erase(v.begin() + 1, v.begin() + 6); // 删除 1-5 位置的数据
    print(v);

    v.clear(); // 清空
    std::cout << v.empty() << std::endl;
}

file

指定位置存取

#include <iostream>
#include <vector>

void print(std::vector<int> &v)
{
    for (int i : v)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::vector<int> v;
    for (int i = 0; i < 10; ++i)
    {
        v.push_back(i);
    }

    print(v);
    std::cout << v[5] << " " << v.at(5) << std::endl; // 取指定下标数据

    // 写指定下标数据
    v[5] = 99;
    v.at(6) = 100;
    print(v);

     // 首尾
    std::cout << v.front() << " " << v.back() << std::endl;
    v.front() = 9;
    v.back() = 0;
    print(v);
}

file

互换容器

#include <iostream>
#include <vector>

void print(std::vector<int> &v1, std::vector<int> &v2)
{
    for (int i : v1)
    {
        std::cout << i << " ";
    }
    std::cout << " - ";
    for (int i : v2)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::vector<int> v1, v2;

    for (int i = 0; i < 10; ++i)
    {
        v1.push_back(i);
    }
    for (int i = 99; i > 88; --i)
    {
        v2.push_back(i);
    }

    print(v1, v2);

    v1.swap(v2); // 交换

    print(v1, v2);
}

file

预留空间

设置预留空间即修改 vector 容量大小，但是改成小于当前容量的操作无任何行为，只能改大。

#include <iostream>
#include <vector>

template<typename T>
void print(T &v)
{
    std::cout << "大小："  << v.size() << " 容量: " << v.capacity() << std::endl;
}

int main()
{
    std::vector<int> v;
    print(v);
    for (int i = 0; i < 5; ++i)
    {
        v.push_back(i);
        print(v);
    }

    v.reserve(3);
    print(v);

    v.reserve(20);
    print(v);
}

file

遍历

#include <iostream>
#include <vector>

void print(int &num) // 用于给遍历算法调用，打印输出
{
    std::cout << num << " ";
}

int main()
{
    std::vector<int> v1;
    for (int i = 0; i < 50; ++i)
    {
        v1.push_back((i + 1) * 5);
    }

    // 遍历一
    {
        // 迭代器
        std::vector<int>::iterator begin = v1.begin(); // 指向第一个元素
        auto end = v1.end(); // 指向最后一个元素的下一个位置；auto 可以自动推导类型
        while (begin != end) // 遍历
        {
            std::cout << *begin++ << " ";
        }
        std::cout << std::endl;
    }

    // 遍历二
    for (std::vector<int>::iterator begin = v1.begin(); begin != v1.end(); ++begin)
    {
        std::cout << *begin << " ";
    }
    std::cout << std::endl;

    // 遍历三 - STL 遍历算法
    for_each(v1.begin(), v1.end(), print); // 遍历范围；调用自定义的打印输出函数
    std::cout << std::endl;

    // 遍历四
    for (auto i : v1)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

存放自定义数据类型

#include <iostream>
#include <vector>

typedef struct
{
    std::string name;
    int age;
} Person;

int main()
{
    std::vector<Person> v;
    v.push_back({"小明", 20});
    v.push_back({"小红", 19});
    v.push_back({"小张", 21});
    v.push_back({"小强", 20});

    for (auto i : v)
    {
        std::cout << i.name << " " << i.age << std::endl;
    }

    std::cout << "--------------------" << std::endl;

    for (auto begin = v.begin(); begin != v.end(); ++begin) // 迭代器本质上是指针，下面两种访问方式等价
    {
        std::cout << begin->name << " " << begin->age << std::endl;
        std::cout << (*begin).name << " " << (*begin).age << std::endl;
    }
}

file

嵌套 – 多维数组

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v1;
    std::vector<int> v2;
    std::vector<int> v3;

    for (int i = 1; i < 5; ++i)
    {
        v1.push_back(i * 2);
        v2.push_back(i * 3);
        v3.push_back(i * 4);
    }

    std::vector<std::vector<int>> v;
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);

    for (auto i : v)
    {
        for (auto j : i)
        {
            std::cout << j << " ";
        }
        std::cout << std::endl;
    }
}

file

deque

双端队列
vector 在头部插入数据时，所有数据都要往后挪动，如果数据量很大，效率就非常低。而 deque 在头部插入数据则是直接插入，效率更高。

拷贝构造

#include <deque>

int main()
{
    std::deque<int> dq1; // 默认构造
    std::deque dq2(dq1.begin(), dq1.end()); // 拷贝迭代器范围内的元素
    int a = 10;
    std::deque dq3(5, a); // 拷贝 5 个 a
    std::deque dq4(dq1); // 拷贝构造
}

赋值

#include <deque>

int main()
{
    std::deque<int> dq1; // 默认构造
    std::deque dq2(dq1.begin(), dq1.end()); // 拷贝迭代器范围内的元素
    int a = 10;
    std::deque dq3(5, a); // 拷贝 5 个 a
    std::deque dq4(dq1); // 拷贝构造
}

容量和大小

  • dque.empty() 判断容器是否为空
  • deque.size() 容器中元素的个数
  • deque.resize(num) 重新设定容器的大小，大于当前长度用默认值填充，小于则删除多余的
  • deque.resize(num, elem) 同上，只是大于容器大小使用 elem 进行填充

插入和删除

  • push_back(elem) 尾部插入一个数据

  • pop_back() 尾部删除一个元素

  • push_front(elem) 头部插入一个数据

  • pop_front() 头部删除一个元素

  • insert(pos, elem) 在 pos 位置插入一个 elem

  • insert(pos, n, elem) 在 pos 位置插入 n 个 elem

  • insert(pos, beg, end) 在 pos 插入迭代器 [beg,end) 之间的数据

  • clear() 清空容器所有数据

  • erase(beg, end) 删除迭代器 [beg,end) 间的数据

  • erase(pos) 删除 pos 位置的数据

指定位置存取

  • at(idx) 操作 idx 位置
  • [idx] 操作 idx 位置
  • front() 操作头元素
  • back() 操作尾元素

stack

栈
先进后出的数据结构，可以以弹夹为例来理解，子弹一颗一颗放入，最先放入的在最底部，打枪的时候从最顶部的子弹开始打出去，每次打的都是最顶部的子弹，然后下面一颗被顶上来。
因此，这种结构决定栈不能遍历，只能访问最顶部的元素，要访问下一个元素就得把最顶部的元素移除出去。
C 语言的简单实现可以参考：https://blog.iyatt.com/?p=8400

#include <iostream>
#include <stack>

int main()
{
    std::stack<int> s1; // 默认构造
    std::stack s2(s1); // 拷贝构造

    s2 = s1; // 重载等号赋值

    for (int i = 0; i < 10; ++i)
    {
        s1.push(i); // 压入数据
    }

    for (int i = 0; i < 10; ++i)
    {
        std::cout << s1.top() << " "; // 获取顶部元素
        s1.pop(); // 移除顶部元素
    }
    std::cout << std::endl;

    // 是否为空；栈的大小
    std::cout << s1.empty() << " " << s1.size() << std::endl;
}

file

queue

队列
先进先出的数据结构，可以以单向隧道为例，只能从一边进，另一边出，先进去的就先出去。
队列只能访问队头和队尾的元素，数据只能从尾部插入，从头部移除。即不支持遍历

#include <iostream>
#include <queue>

int main()
{
    std::queue<int> q1; // 默认构造
    std::queue q2(q1); // 拷贝构造

    q1 = q2; // 赋值重载

    for (int i = 0; i < 10; ++i)
    {
        q1.push(i); // 队尾插入
    }
    std::cout << q1.back() << std::endl; // 访问队尾元素

    for (int i = 0; i < 10; ++i)
    {
        std::cout << q1.front() << " "; // 访问队头元素
        q1.pop(); // 移除队头元素
    }
    std::cout << std::endl;

    // 队列是否为空；队列的大小
    std::cout << q1.empty() << " " << q1.size() << std::endl;
}

file

list

双向链表容器

构造函数

list<T> lst 默认构造
list(beg,end) 使用迭代器构造
list(n.elem) 使用 n 个 elem 构造
list(const list &lst) 拷贝构造

赋值和交换

assign(beg,end) 使用迭代器赋值
assign(n,elem) 使用 n 个 elem 赋值
= 重载的等号赋值
swap(lst) 将自身和 lst 中的元素互换

容量和大小

size() 容器中元素的个数
empty() 判断容器是否为空
resize(num) 重设大小，大于原容量使用默认值填充，小于则删掉
resize(num,elem) 同上，只是填充使用指定值

插入和删除

push_back(elem) 尾部插入元素
pop_back() 尾部删除一个元素
push_front(elem) 头部插入一个元素
pop_front() 头部删除一个元素

insert(pos,elem) pos 位置插入一个元素
insert(pos,n,elem) pos 位置插入 n 个 elem
insert(pos,beg,end) pos 位置插入[beg.end) 范围的元素

clear() 删除容器中所有元素
erase(beg,end) 删除[beg,end) 范围的元素
erase(pos) 删除 pos 位置的元素
remove(elem) 删除 elem 元素

指定位置存取

front() 操作第一个元素
back() 操作最后一个元素

反转和排序

reverse() 反转链表
sort() 排序

set/multiset

关联式容器，基于二叉树实现（红黑树），插入时就会对数据排序

set 容器内不允许重复的元素，multiset 可以存放重复的元素

set<T> st 默认构造
set(const set &st) 拷贝构造函数

= 赋值重载实现

size() 容器中元素的个数
empty() 容器是否为空

swap(st) 交换两个容器

insert(elem) 插入元素
clear() 清空容器
erase(pos) 删除指定迭代器的元素
erase(beg,end) 删除 [beg,end) 区间的元素
erase(elem) 删除指定值的元素

find(key) 查找值并发挥迭代器
count(key) 容器中 key 的个数

## pair

对组
用于存放成对的数据

```cpp
#include 

int main()
{
    std::pair p("小明", 23);
    p.first = "小红";
    std::cout << p.first << " " << p.second << std::endl;

    std::pair pp = std::make_pair("小强", 18);
    p.swap(pp);
    std::cout << p.first << " " << p.second << std::endl;
}

file

map/multimap

关联式容器，用二叉树实现（红黑树）
map 中的元素是 pair，pair 第一个元素为 key，用作索引，第二个元素为 value，用于存放数据
插入的元素会根据 key 自动排序，map 不支持重复的 key，multimap 支持重复的 key

map mp 默认构造
map(const map &mp) 拷贝构造

= 赋值重载

size() 容器中元素的个数
empty() 判断容器是否为空
swap(mp) 交换两个容器

insert(elem) 在容器中插入元素
clear() 清除所有元素
erase(pos) 删除迭代器指向的元素
erase(beg,end) 删除[beg,end) 范围的元素
erase(key) 删除指定 key 的元素

find(key) 查找 key，返回迭代器
count(key) 统计 key 元素个数
容器 – C++ STL 基础
Scroll to top