C/C++教程

C++容器笔记

本文主要是介绍C++容器笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

C++容器

通用特性

所有容器都具有的一个基本特性:它保存元素采用的是“值”(value)语义。

也就是说,容器里存储的是元素的拷贝、副本,而不是引用。

代价:开销大,性能降低。

解决方法:

1. 尽量为元素实现转移构造和转移赋值函数

在加入容器的时候使用 std::move() 来“转移”,减少元素复制的成本:

Point p;                        // 一个拷贝成本很高的对象

v.push_back(p);                // 存储对象,拷贝构造,成本很高
v.push_back(std::move(p));    // 定义转移构造后就可以转移存储,降低成本

**2. 使用 C++11 为容器新增加的 emplace 操作函数 **

它可以“就地”构造元素,免去了构造后再拷贝、转移的成本,不但高效,而且用起来也很方便:

v.emplace_back(...);            // 直接在容器里构造元素,不需要拷贝或者转移

3、容器里存放元素的指针,间接保存元素

缺点:不能利用容器自动销毁元素的特性。得手动管理元素的生命周期,容易出错,可能造成内存泄漏。

具体特性

一种分类是依据元素的访问方式,分成顺序容器、有序容器和无序容器三大类别

顺序容器

顺序容器就是数据结构里的线性表,一共有 5 种:array、vector、deque、list、forward_list。

按照存储结构,这 5 种容器分成(数组和链表)结构

​ 1. 连续存储的数组:array、vector 和 deque;

​ 2. 指针结构的链表:list 和 forward_list。

array 和 vector 直接对应 C 的内置数组,内存布局与 C 完全兼容,所以是开销最低、速度最快的容器。

区别:能否动态增长。array 是静态数组,大小在初始化的时候就固定;vector 是动态数组,虽然初始化的时候设定了大小,但可以在后面随需增长,容纳任意数量的元素。

array<int, 2> arr;                // 初始一个array,长度是2
assert(arr.size() == 2);        // 静态数组的长度总是2

vector<int> v(2);              // 初始一个vector,长度是2
for(int i = 0; i < 10; i++) {
    v.emplace_back(i);          // 追加多个元素
}
assert(v.size() == 12);          // 长度动态增长到12

deque和vector的差异:

共同点:都是动态增长的数组,连续存储的,在中间插入删除效率较低。

不同点:deque是可以在两端高效率插入删除元素的。vector只能用push_back在末端追加元素。

deque<int> d;                  // 初始化一个deque,长度是0
d.emplace_back(9);              // 末端添加一个元素
d.emplace_front(1);              // 前端添加一个元素
assert(d.size() == 2);          // 长度动态增长到2

链表的缺点是查找效率低,只能沿着指针顺序访问。

list和forward_list区别:

​ list 是双向链表,可以向前或者向后遍历,而 forward_list,顾名思义,是单向链表,只能向前遍历,查找效率就更低了。

链表结构和数组结构的比较:

​ 链表存储成本略高,因为必须要为每个元素附加一个或者两个的指针,指向链表的前后节点。

​ 链表的缺点是查找效率低,只能沿着指针顺序访问。

​ 数组中间插入删除效率较低。

vector/deque 和 list/forward_list 都可以动态增长来容纳更多的元素。

vector每次都是2倍扩容,短时间内插入大量数据的时候效果较好。代价是每次扩容的时候进行元素的拷贝或者移动代价成本很大,尽量预估好空间,使用reserve提前分配足够的空间。

deque\list的扩容按指定字节数去扩容。

首选容器 array 和 vector

速度最快、开销最低,数组的形式也令它们最容易使用,搭配算法也可以实现快速的排序和查找。

deque、list 和 forward_list 则适合对插入删除性能比较敏感的场合,如果还很在意空间开销,那就只能选择非链表的 deque 了

有序容器

特点:顺序容器是按插入顺序,访问元素按照最初插入的顺序。

有序容器则不同,它的元素在插入容器后就被按照某种规则自动排序,所以是“有序”的。

结构:树结构,通常是红黑树——有着最好查找性能的二叉树。

标准库里一共有四种有序容器:set/multiset 和 map/multimap。set 是集合,map 是关联数组(在其他语言里也叫“字典”)。

有 multi 前缀的容器表示可以容纳重复的 key,也可以认为只有两种有序容器。

如何正确理解有序?

也就是说,容器是如何判断两个元素的“先后次序”

有序容器与顺序容器的另一个根本区别,在定义容器的时候必须要指定 key 的比较函数

只不过这个函数通常是默认的 less,表示小于关系,不用特意写出来:

template<
    class T                          // 模板参数只有一个元素类型
> class vector;                      // vector

template<
    class Key,                      // 模板参数是key类型,即元素类型
    class Compare = std::less<Key>  // 比较函数
> class set;                        // 集合

template<
    class Key,                      // 第一个模板参数是key类型
    class T,                        // 第二个模板参数是元素类型
    class Compare = std::less<Key>  // 比较函数
> class map;                        // 关联数组

除了基本类型int , string等,自定义的类型是没有默认的比较函数的,要作为容器的key就有点麻烦。

解决这个问题有两种办法:一个是重载“<”,另一个是自定义模板参数。

比如说我们有一个 Point 类,它是没有大小概念的,但只要给它重载“<”操作符,就可以放进有序容器里了:

bool operator<(const Point& a, const Point& b)
{
    return a.x < b.x;            // 自定义比较运算
}

set<Point> s;                    // 现在就可以正确地放入有序容器
s.emplace(7);
s.emplace(3);

另一种方式是编写专门的函数对象或者 lambda 表达式,然后在容器的模板参数里指定。这种方式更灵活,而且可以实现任意的排序准则:

set<int> s = {7, 3, 9};           // 定义集合并初始化3个元素

for(auto& x : s) {                // 范围循环输出元素
    cout << x << ",";              // 从小到大排序,3,7,9
}   

auto comp = [](auto a, auto b)  // 定义一个lambda,用来比较大小
{   
    return a > b;                // 定义大于关系
};  

set<int, decltype(comp)> gs(comp)  // 使用decltype得到lambda的类型

std::copy(begin(s), end(s),          // 拷贝算法,拷贝数据
          inserter(gs, gs.end()));  // 使用插入迭代器

for(auto& x : gs) {                // 范围循环输出元素
    cout << x << ",";                // 从大到小排序,9,7,3
}  

有序容器使用法则:

集合关系就用 set,关联数组就用 map。

注意:,因为有序容器在插入的时候会自动排序,所以就有隐含的插入排序成本,当数据量很大的时候,内部的位置查找、树旋转成本可能会比较高。

需要实时插入排序,那么选择 set/map 是没问题的。如果是非实时,那么最好还是用 vector,全部数据插入完成后再一次性排序,效果肯定会更好。

无序容器unordered(无序)

无序容器也有四种,名字里也有 set 和 map,只是加上了 unordered(无序)前缀,分别是 unordered_set/unordered_multiset、unordered_map/unordered_multimap。

用法与有序容器几乎一样。

区别:内部数据结构不同。

内部数据结构:它不是红黑树,而是散列表(也叫哈希表,hash table)。

例子:

using map_type =                    // 类型别名
    unordered_map<int, string>;      // 使用无序关联数组

map_type dict;                      // 定义一个无序关联数组

dict[1] = "one";                      // 添加三个元素
dict.emplace(2, "two");
dict[10] = "ten";

for(auto& x : dict) {                // 遍历输出
    cout << x.first << "=>"           // 顺序不确定
         << x.second << ",";          // 既不是插入顺序,也不是大小序
} 

无序容器对key的要求比有序容器”苛刻“点:

第一个是因为散列表的要求,只有计算 hash 值才能放入散列表;

第二个则是因为 hash 值可能会冲突,所以当 hash 值相同时,就要比较真正的 key 值。

举例:

template<
    class Key,                          // 第一个模板参数是key类型
    class T,                            // 第二个模板参数是元素类型
    class Hash = std::hash<Key>,        // 计算散列值的函数对象
    class KeyEqual = std::equal_to<Key> // 相等比较函数
> class unordered_map; 

要把key放入容器必须实现 一下这两个函数:

==”函数比较简单,可以用与“<”函数类似的方式,通过重载操作符来实现:

bool operator==(const Point& a, const Point& b)
{
    return a.x == b.x;              // 自定义相等比较运算
}

散列函数就略麻烦一点,你可以用函数对象或者 lambda 表达式实现,内部最好调用标准的 std::hash 函数对象,而不要自己直接计算,否则很容易造成 hash 冲突:

auto hasher = [](const auto& p)    // 定义一个lambda表达式
{
    return std::hash<int>()(p.x);  // 调用标准hash函数对象计算
};

把一个自定义类型放入无序容器中时,容器必须支持相等函数和散列函数。

unordered_set<Point, decltype(hasher)> s(10, hasher);

s.emplace(7);
s.emplace(3);

有序和无序容器的选择:

如果只想要单纯的集合、字典,没有排序需求,就应该用无序容器,没有比较排序的成本,它的速度就会非常快。

// 定义一个lambda表达式

{
    return std::hash<int>()(p.x);  // 调用标准hash函数对象计算
};

把一个自定义类型放入无序容器中时,容器必须支持相等函数和散列函数。

unordered_set<Point, decltype(hasher)> s(10, hasher);

s.emplace(7);
s.emplace(3);

有序和无序容器的选择:

如果只想要单纯的集合、字典,没有排序需求,就应该用无序容器,没有比较排序的成本,它的速度就会非常快。

实战小技巧: 多用类型别名,不要写死容器定义。 因为大部分接口相同,所以只要变动别名定义,就能够随意改换不同的容器。

这篇关于C++容器笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!