现代C++之容器

现代C++之容器

本节将深入学习现代C++实战30讲中的第4节与第5节容器所提到的内容。正文中的一些文字直接引用自上面。

1.string

string 是模板 basic_string 对于 char 类型的特化,可以认为是一个只存放字符 char 类型数据的容器。“真正”的容器类与 string 的最大不同点是里面可以存放任意类型的对象。

string 当然是为了存放字符串。和简单的 C 字符串不同:

  • string 负责自动维护字符串的生命周期
  • string 支持字符串的拼接操作(如之前说过的 + 和 +=)
  • string 支持字符串的查找操作(如 find 和 rfind)
  • string 支持从 istream 安全地读入字符串(使用 getline)
  • string 支持给期待 const char* 的接口传递字符串内容(使用 c_str)
  • string 支持到数字的互转(stoi 系列函数和 to_string)
  • 等等

在原文中比较重要的几句话来了:

  • 推荐你在代码中尽量使用 string 来管理字符串
  • 对于对外暴露的接口,则不建议。

不建议在接口中使用const string&,除非确知调用者已经持有 string:如果函数里不对字符串做复杂处理的话,使用 const char* 可以避免在调用者只有 C 字符串时编译器自动构造 string,这种额外的构造和析构代价并不低。

反过来,如果实现较为复杂、希望使用 string 的成员函数的话,那就应该考虑下面的策略:

  • 如果不修改字符串的内容,使用 const string& 或 C++17 的 string_view 作为参数类型。后者是最理想的情况,因为即使在只有 C 字符串的情况,也不会引发不必要的内存复制。
  • 如果需要在函数内修改字符串内容、但不影响调用者的该字符串,使用 string 作为参数类型(自动拷贝)。
  • 如果需要改变调用者的字符串内容,使用 string& 作为参数类型(通常不推荐)。

2.vector

2.1 异常安全性

vector 通常保证强异常安全性,如果元素类型没有提供一个保证不抛异常的移动构造函数,vector 通常会使用拷贝构造函数。

因此,对于拷贝代价较高的自定义元素类型,我们应当定义移动构造函数,并标其为 noexcept,或只在容器中放置对象的智能指针。

例如:

#include <iostream>
#include <vector>

using namespace std;

class Obj1 {
public:
  Obj1()
  {
    cout << "Obj1()\n";
  }
  Obj1(const Obj1&)
  {
    cout << "Obj1(const Obj1&)\n";
  }
  Obj1(Obj1&&)
  {
    cout << "Obj1(Obj1&&)\n";
  }
};

class Obj2 {
public:
  Obj2()
  {
    cout << "Obj2()\n";
  }
  Obj2(const Obj2&)
  {
    cout << "Obj2(const Obj2&)\n";
  }
  Obj2(Obj2&&) noexcept
  {
    cout << "Obj2(Obj2&&)\n";
  }
};

int main()
{
  vector<Obj1> v1;
  v1.reserve(2);
  v1.emplace_back();
  v1.emplace_back();
  v1.emplace_back();

  vector<Obj2> v2;
  v2.reserve(2);
  v2.emplace_back();
  v2.emplace_back();
  v2.emplace_back();
}

输出:

Obj1()
Obj1()
Obj1()
Obj1(const Obj1&)
Obj1(const Obj1&)
Obj1()
Obj2()
Obj2()
Obj2()
Obj2(Obj2&&)
Obj2(Obj2&&)

头两个在已有空间上成功构造。第三个时发现空间不足,系统会请求更大的空间,大小由实现决定(比如两倍)。有了足够的空间后,就会在新空间的第三个的位置构造(第三个obj1),成功之后再把头两个拷贝或移动过来。

如果调用改为:

vector<Obj1> v1;
v1.emplace_back();
v1.emplace_back();
v1.emplace_back();
v1.emplace_back();

输出就变为:

Obj1()
Obj1()
Obj1(const Obj1&)
Obj1()
Obj1(const Obj1&)
Obj1(const Obj1&)
Obj1()

第一个emplace_back后,容量为1,第二个emplace_back后,构造第二个obj1的时候,容量不够了,分配新的空间,此时空间为原来两倍,在新的空间构造第2个位置构造obj1,再把第一个拷贝或移动到新的空间上。进入第三个v1.emplace_back后,此时容量为2,容量不够了,再次分配重复前面操作,容量变为4,在新容量的第3个位置构造obj1,再把前面两个拷贝到新分配空间。最后一次v1.emplace_back,容量充足,直接构造即可。

vector 的一个主要缺陷是大小增长时导致的元素移动。如果可能,尽早使用 reserve 函数为 vector 保留所需的内存,这在 vector 预期会增长很大时能带来很大的性能提升。

2.2 resize与reserve

两者区别

vector 的reserve增加了vector的capacity,但是它的size没有改变!而resize改变了vector的capacity同时也增加了它的size!

区别1:

(1)reserve是容器预留空间,但在空间内不真正创建元素对象。所以在没有添加新的对象之前,不能引用容器内的元素。加入新的元素时,要调用push_back()/insert()函数。

(2)resize是改变容器的大小,且在创建对象。因此,调用这个函数之后,就可以引用容器内的对象了。因此当加入新的元素时,用operator[]操作符,或者用迭代器来引用元素对象。此时再调用push_back()函数,是加在这个新的空间后面的。

区别2:

两个函数的参数形式也有区别的:

void reserve(size_type __n)
void resize(size_type __new_size, const value_type& __x)
void resize(size_type __new_size)

reserve函数一个参数,即需要预留容器的空间;

resize函数可以有两个参数,第一个参数是容器新的大小, 第二个参数是要加入容器中的新元素,如果这个参数被省略,那么就调用不带第二个参数的resize函数。

例如:

vector<int> myVec;
myVec.reserve( 100 );     // 新元素还没有构造,
                                       // 此时不能用[]访问元素
for (int i = 0; i < 100; i++ )
{
     myVec.push_back( i ); //新元素这时才构造
}
myVec.resize( 102 );      // 用元素的默认构造函数构造了两个新的元素
myVec[100] = 1;           //直接操作新元素
myVec[101] = 2;

3.list与forward_list

list 是双向链表,从 C++11 开始,前向列表 forward_list 成了标准的一部分。为什么会需要这么一个阉割版的 list 呢?

原因是,在元素大小较小的情况下,forward_list 能节约的内存是非常可观的;在列表不长的情况下,不能反向查找也不是个大问题。提高内存利用率,往往就能提高程序性能,更不用说在内存可能不足时的情况了。

4.queue与stack

(1)为什么 stack(或 queue)的 pop 函数返回类型为 void,而不是直接返回容器的 top(或 front)成员?

因为 stack(queue)为保证强异常安全性,如果元素类型没有提供一个保证不抛异常的移动构造函数, 通常会使用拷贝构造函数。pop作用是释放元素,c++98设计时还没有移动构造的概念,所以如果返回成员,必须要调用拷贝构造函数,这时分配空间可能出错,导致构造失败,要抛出异常,所以没必要返回成员。而c++11后有了移动,在多线程的环境里,移动返回加弹出实际上就变得有用了。

(2)stack与内存管理栈区别?

stack 跟我们前面讨论内存管理时的栈有一个区别:在这里下面是低地址,向上则地址增大;而我们讨论内存管理时,高地址在下面,向上则地址减小,方向正好相反。

5.关联容器

关联容器有 set(集合)、map(映射)、multiset(多重集)和 multimap(多重映射)。跳出 C++ 的语境,map(映射)的更常见的名字是关联数组和字典 ,而在 JSON 里直接被称为对象(object)。在 C++ 外这些容器常常是无序的;在 C++ 里关联容器则被认为是有序的。

与序列容器相比,关联容器没有前、后的概念及相关的成员函数,但同样提供 insert、emplace 等成员函数。此外,关联容器都有 find、lower_bound、upper_bound 等查找函数,结果是一个迭代器:

  • find(k) 可以找到任何一个等价于查找键 k 的元素(!(x < k || k < x))
  • lower_bound(k) 找到第一个不小于查找键 k 的元素(!(x < k))
  • upper_bound(k) 找到第一个大于查找键 k 的元素(k < x)

如果你需要在 multimap 里精确查找满足某个键的区间的话,建议使用 equal_range,可以一次性取得上下界(半开半闭)。

示例:

map<string, int> mp{
        {"one",   1},
        {"two",   2},
        {"three", 3},
        {"four",  4}
};

cout << mp << endl;


mp.insert({"four", 4});
cout << mp << endl;

cout << (mp.find("four") == mp.end()) << endl;

cout << (mp.find("five") == mp.end()) << endl;

mp["five"] = 5;

cout << mp << endl;


multimap<string, int> mmp{
        {"one",   1},
        {"two",   2},
        {"three", 3},
        {"four",  4}
};

cout << mmp << endl;

mmp.insert({"four", -4});

cout << mmp << endl;

cout << (mp.find("four")->second) << endl;
cout << (mp.lower_bound("four")->second) << endl;

cout << (mp.upper_bound("four")->second) << endl;
cout << ((--mp.upper_bound("four"))->second) << endl;

multimap<string, int>::iterator
        lower, upper;
std::tie(lower, upper) =
        mmp.equal_range("four");
cout << (lower != upper) << endl;   // 检测区间非空

cout << lower->second << endl;
cout << (--upper)->second << endl;

通过比较来进行查找、插入和删除,复杂度为对数 O(log(n)),有没有达到更好的性能的方法?

那么就是无序关联容器。

6.无序关联容器

从 C++11 开始,每一个关联容器都有一个对应的无序关联容器,它们是:

  • unordered_set
  • unordered_map
  • unordered_multiset
  • unordered_multimap

这些容器和关联容器非常相似,主要的区别就在于它们是“无序”的。这些容器不要求提供一个排序的函数对象,而要求一个可以计算哈希值的函数对象。你当然可以在声明容器对象时手动提供这样一个函数对象类型,但更常见的情况是,我们使用标准的hash 函数对象及其特化。

#include <complex>        // std::complex
#include <iostream>       // std::cout/endl
#include <unordered_map>  // std::unordered_map
#include <unordered_set>  // std::unordered_set
#include "output_container.h"

using namespace std;

namespace std {

template <typename T>
struct hash<complex<T>> {
  size_t
  operator()(const complex<T>& v) const
    noexcept
  {
    hash<T> h;
    return h(v.real()) + h(v.imag());
  }
};

}  // namespace std

int main()
{
  unordered_set<int> s{
    1, 1, 2, 3, 5, 8, 13, 21
  };
  cout << s << endl;

  unordered_map<complex<double>,
                double>
    umc{{{1.0, 1.0}, 1.4142},
        {{3.0, 4.0}, 5.0}};
  cout << umc << endl;
}

输出:

{ 21, 8, 5, 3, 13, 2, 1 }
{ (3,4) => 5, (1,1) => 1.4142 }

上述在 std 名空间中添加了特化,这是少数用户可以向 std 名空间添加内容的情况之一。正常情况下,向 std 名空间添加声明或定义是禁止的,属于未定义行为。

从实际的工程角度,无序关联容器的主要优点在于其性能。关联容器和priority_queue的插入和删除操作,以及关联容器的查找操作,其复杂度都是 O(log(n)),而无序关联容器的实现使用哈希表 ,可以达到平均 O(1)!但这取决于我们是否使用了一个好的哈希函数:在哈希函数选择不当的情况下,无序关联容器的插入、删除、查找性能可能成为最差情况的 O(n),那就比关联容器糟糕得多了。

7.array

C 数组在 C++ 里继续存在,主要是为了保留和 C 的向后兼容性。C 数组本身和 C++ 的容器相差是非常大的:

  • C 数组没有 begin 和 end 成员函数(虽然可以使用全局的begin 和 end 函数)
  • C 数组没有 size 成员函数(得用一些模板技巧来获取其长度)
  • C 数组作为参数有退化行为,传递给另外一个函数后那个函数不再能获得 C 数组的长度和结束位置在 C 的年代,大家有时候会定义这样一个宏来获得数组的长度:
#define ARRAY_LEN(a) \
(sizeof(a) / sizeof((a)[0]))
void test(int a[8])
{
  cout << ARRAY_LEN(a) << endl;
}

如果在一个函数内部对数组参数使用这个宏,结果肯定是错的。现在 GCC 会友好地发出警告:

warning: sizeof on array function parameter will return size of ‘int *’ instead of ‘int [8]’ [-Wsizeof-array-argument]

C++17 直接提供了一个 size 方法,可以用于提供数组长度,并且在数组退化成指针的情况下会直接失败:

#include <iostream>  // std::cout/endl
#include <iterator>  // std::size

void test(int arr[])
{
  //  不能编译
  // std::cout << std::size(arr)
  //           << std::endl;
}

int main()
{
  int arr[] = {1, 2, 3, 4, 5};
  std::cout << "The array length is "
            << std::size(arr)
            << std::endl;
  test(arr);
}

此外,C 数组也没有良好的复制行为。你无法用 C 数组作为 map 或 unordered_map 的键类型。下面的代码演示了失败行为:

#include <map>  // std::map

typedef char mykey_t[8];

int main()
{
  std::map<mykey_t, int> mp;
  mykey_t mykey{"hello"};
  mp[mykey] = 5;
  //  轰,大段的编译错误
}

如果不用 C 数组的话,我们该用什么来替代呢?

我们有三个可以考虑的选项:

  • 如果数组较大的话,应该考虑 vector。vector 有最大的灵活性和不错的性能。
  • 对于字符串数组,当然应该考虑 string。
  • 如果数组大小固定(C 的数组在 C++ 里本来就是大小固定的)并且较小的话,应该考虑 array。array 保留了 C 数组在栈上分配的特点,同时,提供了 begin、end、size 等通用成员函数。

array 可以避免 C 数组的种种怪异行径。上面的失败代码,如果使用 array 的话,稍作改动就可以通过编译:

#include <array>     // std::array
#include <iostream>  // std::cout/endl
#include <map>       // std::map
#include "output_container.h"

typedef std::array<char, 8> mykey_t;

int main()
{
  std::map<mykey_t, int> mp;
  mykey_t mykey{"hello"};
  mp[mykey] = 5;  // OK
  std::cout << mp << std::endl;
}

本文分享自微信公众号 - 光城(guangcity),作者:lightcity

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Image Captioning with RNNs

    0.导语1.下载数据集2.Look at the data3.Vanilla RNN3.1 step forward3.2 step backward3.3 f...

    公众号guangcity
  • 一起来相约猫眼

    之前有人给我提了个需求,让我去看看猫眼专业版,字体反爬问题,我觉得有趣,因为之前没学过字体反爬。然后,就尝试去搞了一下,结果当时因为xx原因,放弃了。也是实力不...

    公众号guangcity
  • 现代C++之SFINAE应用(小工具编写)

    是不是有点像Python的print一样简单,但这背后实现也就仅仅不到100行的代码,本节来实现这种功能。

    公众号guangcity
  • 在容器中使用 Java 的资源分配准则

    如果说在容器中运行 Java 应用有一条核心定律,那么就是:对于在容器中运行的 Java 进程,不要手工设置 JVM 堆内存。相反的,设置容器的限制。

    奋斗蒙
  • 热乎乎的寒“春”前端面试题来了

    这一关,我觉得是很有必要的,人眼可以判断出JS代码运行是否错误,这点判断排除BUG能力很关键。

    Peter谭金杰
  • 注册中心 Eureka 源码解析 —— 注册表 InstanceRegistry 类关系

    芋道源码
  • OSCAR云计算开源产业大会召开——计算无处不在,开源引领未来

    2019年7月3日,OSCAR云计算开源产业大会在北京国际会议中心盛大召开。本次大会主题为“计算无处不在,开源引领未来”,由国信息通信研究院主办,中国IDC圈协...

    云加社区
  • MySQL中如何选择VARCHAR和CHAR类型

    首先,VARCHAR和CHAR是两种最主要的字符串类型。在设计用于存储字符串的表字段时,可能会对到底选哪个类型有所犹豫,确实如果不了解它们之间的区别,选择上不会...

    JavaQ
  • .NET CORE(C#) WPF亚克力窗体

    使用 .Net Core 3.1 创建名为 “AcrylicWindow” 的WPF模板项目,添加三个Nuget库:MaterialDesignThemes、M...

    dotnet9.com
  • 基于华为fusionstorage的块存储CSI

    承接上文,块存储的CSI要比对象存储复杂一些,但总的处理逻辑还是一致的。下面以华为fusionstorage的CSI为例进行介绍,该插件支持了多个后端存储,如f...

    charlieroro

扫码关注云+社区

领取腾讯云代金券