Sirius' blog
Sirius0v0
2023-07-09
目录

CC++STL-常用容器

# C/C++：STL-常用容器

几个有用的网站：

# 基本概念

  • STL(Standard Template Library, 标准模板库)
  • STL广义上分为
    • 容器（container）
    • 算法（algorithm）
    • 迭代器（iterator）
  • 容器和算法之间通过迭代器进行无缝连接

# 六大组件

  • 容器（Containers）：各种数据结构，如vector、list、deque、set、map等；
  • 空间配置器【分配器】（Allocators）：负责空间的配置与管理；
  • 算法（Algorithms）：各种常用算法，如sort、find、copy、for_each等；
  • 迭代器（Iterators）：扮演了容器和算法之间的胶合剂；
  • 适配器（Adapters）：一种用来修饰容器或仿函数或迭代器接口的东西；
  • 仿函数（Functors）：行为类似函数，可作为算法的某种策略。

# 容器、算法、迭代器

  • 容器

    • 序列式容器
    • 关联式容器

  • 算法

    • 质变算法
    • 非质变算法

  • 迭代器

    种类 功能 支持运算
    输入迭代器 只读访问 只读，支持++、==、!=
    输出迭代器 只写访问 只写，支持==
    前向迭代器 读写操作，且能向前推进迭代器 读写，支持++、==、!=
    双向迭代器 读写操作，且能向前和向后推进迭代器 读写，支持++、--
    随机访问迭代器 读写操作，可以以跳跃的方式访问任意数据，功能最为强大 读写，支持++、--、[n]、-n、<、<=、>、>=

# std::string容器

# 基本概念

string类内部封装了char*，是char*型的容器

# 构造函数

string();
string(const char *s);
string(const string &str);
string(int n, char c);//使用n个字符c初始化

# 赋值操作

string& operator=(const char *s);
string& operator=(const string &s);
string& operator=(char c);

string& assign(const char *s);
string& assign(const char *s, int n);    // 取前n个字符
string& assign(const string &s);
string& assign(int n, char c);

# 字符串拼接

string& operator+=(const char *s);
string& operator+=(const string &s);
string& operator+=(char c);

string& append(const char *s);
string& append(const char *s, int n);    // 追加前n个字符
string& append(const string &s);
string& append(int n, char c);
string& append(const string &s, int pos, int n);	// 将字符s从pos开始的n个字符追加

# 查找与替换

// 从首个位置开始搜索
n = s.find("is");
// 从位置 5 开始搜索
n = s.find("is", 5);
// 寻找单个字符
n = s.find('a');
// 找不到则返回std::string::npos

// rfind与find类似，是从右往左找
n = s.rfind("is");

// 替换使用replace
string& replace(int pos, int n, const string &str);
string& replace(int pos, int n, const char *s);

# 字符串比较

// s1.compare(s2);
// == 则相等【比较主要用的是是否相等】
// <  则s1在s2前
// >  则s2在s1前
int compare(const string &s) const;
int compare(const char *s) const;

# 字符存取

char & operator[](int n);
char & at(int n);

# 插入和删除

string &insert(int pos, const char *s);
string &insert(int pos, const string &s);
string &insert(int pos, int n, char c);

// 删除从pos开始的n个字符
string &erase(int pos, int n = npos);

# 子串

string substr(int pos=0, int n = npos) const;

# std::vector容器

# 基本概念

vector与普通数组不同之处在于，数组是静态空间，而vector可以动态扩展

对vector索引常用的几个迭代器如下：

  • v.begin() （第一个）
  • v.end() （最后一个的后一个）
  • v.rend() （第一个的前一个）
  • v.rbegin() （倒数第一个）

# 构造函数

vector<T> v;
vector(v.begin(), v.end());	// 左闭右开
vector(n, elem);	// 将n个elem拷贝给本身
vector(const vector &vec);

# 赋值操作

vector & operator=(const vector &vec);
assign(beg, end);
assign(n, elem);

# 容量和大小

empty();	// 判断是否为空
capacity();	// 容器容量
size();		// 容器元素个数
resize(int num);	// 重新指定长度
resize(int num, elem); // 用elem填充

# 插入和删除

push_back(ele);
pop_back();
insert(const_iterator pos, ele);
insert(const_iterator pos, int count, ele);
erase(const_iterator pos);
erase(const_iterator start, const_iterator end);
clear();

# 数据存取

at(int idx);
operator[];
front();	// 第一个数据
back();		// 最后一个数据

# 互换容器

swap(vec);	// 元素互换

合理利用互换容器可以达到收缩内存的目的：

    std::cout << "合理利用容器互换可以达到收缩内存的目的" << '\n';
    std::vector<int> v_big(300000);
    v_big[0] = 1;
    v_big.resize(10);
    std::cout << "----------\n";
    std::cout << "v的容量为:" << v_big.capacity() << '\n';
    std::cout << "v的元素个数为:" << v_big.size() << '\n';

    // 收缩内存
    std::vector<int>(v_big).swap(v_big);
    std::cout << "----------\n";
    std::cout << "v的容量为:" << v_big.capacity() << '\n';
    std::cout << "v的元素个数为:" << v_big.size() << '\n';

其中vector<int>(v)是匿名对象，注意，需要紧接着使用swap方法，否则会报错【匿名对象不能使用拷贝构造函数进行创建】。

创建的匿名vec对象与当前内存占用较大的vec对象将指向的地址进行互换，由于匿名对象会紧接着析构，因此会释放掉多余占用的空间。

# 预留空间

减少vector在动态扩展容量时的扩展次数。

reserve(int len);	// 预留len个长度，预留位置不初始化，不可访问

# 排序

std::sort(beg, end);

# std::deque容器

# 基本概念

双端队列，两端都可扩充。

内部工作原理：

deque内部有个中控器，存放着要维护的每一段缓冲区，缓冲区中放有数据。

# 构造函数

与vector类似

# 赋值操作

与vector类似

# 大小操作

与vector类似，无capacity()函数

# 插入和删除

与vector类似，多了push_front()和pop_front()

# 数据存取

与vector类似

# 排序

与vector类似

# std::stack容器

# 基本概念

栈容器，先入后出。栈不允许有遍历行为。

# 常用接口

构造函数、赋值操作、数据存取、大小操作

// 入栈
push(10);
// 出栈
pop();
// 返回栈顶
top();
// 是否为空
empty();
// 栈大小
size();

# std::queue容器

# 基本概念

队列，先进先出。队列容器也不允许有遍历行为。

# 常用接口

构造函数、赋值操作、数据存取、大小操作

push(elem);
pop();
back();
front();
empty();
size();

# std::list容器

# 基本概念

链表，数据存储不连续，数据元素的逻辑顺序是通过链表中的指针链接实现的。

链表由一系列结点组成，结点由存储数据元素的数据域与存储下一个结点地址的指针域构成。

由于链表存储方式不连续，因此链表list中的迭代器只支持前移和后移，是双向迭代器。

vector和list是最常用的两个容器，各自有优缺点，从list的视角加以总结：

list优点:

  • 动态存储分配，不会造成内存的浪费和溢出
  • 插入和删除操作十分方便，不需要大量移动元素
  • 插入操作和删除操作都不会造成原有list迭代器的失效，而vector不成立。

list缺点：

  • 空间（多余存储结点地址）和时间（遍历）额外耗费大

# 构造函数

与vector类似

# 赋值与交换

与vector类似

# 大小操作

与vector类似

# 插入和删除

与deque类似，多了一个remove(elem)方法，删除容器中所有与elem值匹配的元素。

# 数据存取

与vector类似，但因为不是随机访问迭代器，所以没有at和[]访问数据的操作，仅有back()和front()

# 反转和排序

reverse();	// 反转（成员函数）
sort(); 	// 排序（成员函数）

所有不支持随机访问迭代器的容器，不可以用标准算法，内部会提供对应的一些算法。

# std::set/multiset容器

# 基本概念

关联式容器，底层是二叉树实现的。所有元素在插入时自动被排序。

# 构造和赋值

set<T> st;
set(const set &st);

set& operator=(const set &st);

# 大小和交换

size();
empty();
swap(st);

# 插入和删除

insert(elem);
clear();
erase(pos);
erase(beg, end);
erase(elem);	// 类似list的remove

# 查找和统计

find(key);
count(key);

# set与multiset区别

  • set不允许有重复元素，multiset允许有重复元素

可以通过接收set在insert操作时的返回值查看是否插入成功

    std::set<int> st1;
    std::pair<std::set<int>::iterator, bool> res = st1.insert(10);
    if (res.second)
        std::cout << "第一次插入成功\n";
    else
        std::cout << "第一次插入失败\n";

    auto res2 = st1.insert(10);
    if (res2.second)
        std::cout << "第二次插入成功\n";
    else
        std::cout << "第二次插入失败\n";

    std::multiset<int> mst;
    mst.insert(10);
    mst.insert(10);

    for (auto it = mst.begin(); it != mst.end(); it++)
    {
        std::cout << *it << ' ';
    }
    std::cout << '\n';

# pair对组创建

成对的数据，可以返回两个数据。

创建方式

  • pair<type, type> p(val1, val2);
  • pair<type, type> p = make_pair(val1, val2);

# set的排序

在set中默认是升序排序，现在需要制定排序规则为降序，利用仿函数实现

class MyCompare
{
public:
    bool operator()(int v1, int v2) const
    { // 降序，即前一个数>后一个数
        return v1 > v2;
    }
};

class PersonCompare
{ // 年龄降序排序
public:
    bool operator()(const Person &p1, const Person &p2) const
    {
        return p1.m_age > p2.m_age;
    }
};

# std::map/multimap容器

# 基本概念

  • map/multimap属于关联式容器
  • map中所有元素都是pair
  • 所有元素会根据元素的键值自动排序

# 构造与赋值

map<T1,T2> mp;
map(const map &mp);

map& operator=(const map &mp);

# 大小和交换

size();
empty();
swap(st);

# 插入和删除

insert(elem);
mp[key]=value;	// 存在会覆盖原值
clear();
erase(pos);
erase(beg, end);
erase(elem);	// 类似list的remove

# 查找和统计

find(key);
count(key);

# 排序

依然与set类似

# std::optional 容器

有些函数，本来要返回T类型，但是由于某些原因可能失败：比如做除法时除数为0时应当返回计算失败，最一般的做法就是指定一个操作状态标志来确定是否正常返回，非常麻烦。

推荐使用 std::oprtional<T> 容器，成功时直接返回T，当失败时，只需返回 std::nullopt 即可。

std::optional<float> mysqrt(float x)
{
  if (x >= 0.0f){
    return std::sqrt(x);
  } else {
    return std::nullopt;
  }
}

int main()
{
  auto ret = mysqrt(3.0f);
  if (ret.has_value())
  {
    std::cout << ret.value();
  }
  else
  {
    std::cout << "失败！";
  }
}

# 判断是否成功返回与取值

可以通过 .has_value() 判断是否成功返回，通过 .value() 方法获得返回的值。其实，if条件表达式中，可以直接写 if (ret) 进行判断，它和 if (ret.has_value()) 等价。

除了使用 .value() 获取 optional 容器中的值，还可以使用 *ret 获取容器中的值。需要注意的是，.value() 方法会检测容器内是否为空，空则会抛出异常，然而*ret 不会检测是否 has_value()，也不会抛出异常，更加高效，但是需要注意安全

还有一个方便的方法指定一个缺省值：ret.value_or(3)，它等价于 ret.has_value() ? ret.value() : 3 。

# std::variant 容器

更安全的 union，存储多个不同类型的值中的一个。

std::variant<int, float> v = 3;

# 从容器中获取值

std::variant<int, float> v = 3;

std::cout << std::get<int>(v);
std::cout << std::get<0>(v);  // 表示获取variant列表第0个类型

v = 3.14f;

std::cout << std::get<float>(v);
std::cout << std::get<int>(v);  // 运行时会报错

# 判断当前是哪个类型？

使用 std::holds_alternative

void print(std::variant<int,float> const &v)
{
  if (std::holds_alternative<int> (v))
    std::cout << std::get<int>(v);
  else if (std::holds_alternative<float>(v))
    std::cout << std::get<float>(v);
}

使用 .index() 获取当前是参数列表的第几个类型

void print(std::variant<int,float> const &v)
{
  if (v.index() == 0)
    std::cout << std::get<int>(v);
  else if (v.index() == 1)
    std::cout << std::get<float>(v);
}

# 使用 std::visit 批量匹配variant

如果 if-else 分支长得都差不多，如上述例子，可以考虑使用 std::visit。他会自动用相应的类型，调用lambda来操作。

这里的lambda参数带有auto，利用了多次编译的特性，实现多个分支的效果。

void print(std::variant<int,float> const &v)
{
    std::visit([&](auto const &t){
        std::cout << t << '\n';
    }, v);
}

当有多个variant作为参数，为了让参数匹配，若variant有n个类型，则会被编译次，编译可能会变慢。

auto add(variant<int,float> const7 v1, variant<int,float> const7 v2)
{
  variant<int,float> ret;
  std::visit([&](auto const &t1, auto const &t2){
    ret = t1+t2;
  }, v1,v2);
  return ret;
}

或（lambda有返回值的形式）：

auto add(variant<int,float> const7 v1, variant<int,float> const7 v2)
{
  return std::visit([&](auto const &t1, auto const &t2)
    -> std::variant<int,float> {
    return t1+t2;
  }, v1,v2);
}
编辑 (opens new window)
#Cpp
上次更新: 2023/08/16, 16:01:49
CC++模板
CC++STL-函数对象

← CC++STL-函数对象→

最近更新
01
ipopt优化库配置及使用
07-21
02
ubuntu离线安装包的方法
07-21
03
其它控件的使用
03-05
更多文章>
Theme by Vdoing | Copyright © 2020-2024 Sirius0v0 | MIT License