【C++11】字符串与常用数据结构


学习一门编程语言,考察编程语言支持的基本数据结构是很重要的。如果你以前学的C/C++倾向于自己造轮子,或者你有其他语言背景的话,建议重新了解一下C++11 标准库中的数据结构。

字符串 std::string

你可以用 const char* 也就是字符串字面量来构造 std::string ,也可以从 std::string 中获取 C风格字符串的指针(const char*)。

std::string 是可变的,所以你可以修改 std::string 而不用太担心性能

关于不可变字符串,有很多讨论,这里列举一下想要用不可变的“字符串”话,在不用其他库的情况下可以怎么做

  • const char* 如果自己分配的字符串数组的话,需要记得delete。字符串字面量的话不用担心。
  • const std::string& 给 std::string 加const,严格来说这只是防止修改
  • 自己造轮子

std::string 支持 copy 和 move

std::string 的 substr 返回的是 copy 过的子字符串。

C++17开始支持 string_view。在C++17之前想用“字符串视图”的话,你可能要自己构造一个类似下面这种包装结构

std::string 的 = 是字符串比较,而不是地址比较。

std::string 提供的相关方法不多,现有的比如查找find/rfind

需要注意找不到时返回的不是-1,而是npos,一个特殊的值

std::string 提供了两个获取字符的方法,at 和 [],前者加了范围检查,后者没有

支持用迭代器方式遍历字符串

关于UTF-8字符串,可能和 std::string 没有直接关系,但是C++11中的字符串字面量

1是依赖于系统编码的字符串字面量,2是UTF-8编码的字符串字面量。

std::string 没有直接支持UTF-8的方法,size返回的是字节数,如果你用迭代器遍历的话,是按照逐个byte的方式(虽然类型叫char)

自增长数组:std::vector<T>

对于有自增长需求的数组,std::vector 是一个很好的选择,但是在使用C++11引入的initializer_list需要注意复制问题。具体来说

1是没有问题的,基础类型本来就可以随意复制。2会复制字符串。原因在于initializer_list的begin和end返回值有const修饰,vector的构造函数里只能复制。解决方法是

也就是说,不要使用intializer_list构造T为非基础类型的vector

上述代码中第二行的reserve是必须的。使用vector的默认构造函数时初始大小为0。那么是否有可以指定初始大小的构造函数?有兴趣的可以看一下 std::vector 的构造函数,回答是可能没有。注意使用数字初始化vector时你会得到指定数量的T的实例,而不是指定数量的空位(nullptr)。

之后调用C++11新增的emplace_back方法。emplace_back比C++11之前的push_back好的地方是不需要move,直接在vector里初始化。这里涉及 std::vector 是内部所有元素的 owner 的要求,所以任何通过 push_back 传入的元素都会被 move,如果不支持 move 那么就 copy。

如果你用上一篇用于测试copy/move的MyString作为T执行上述代码的话,输出只有3次构造函数调用。用push_back的话,会有3次move。不用reverse的话,会有3 + 2 + 1 = 6次move,这是因为内部需要扩容,扩容时会move。如果用initializer_list初始化的话,会有3次copy。

如果你要高效地使用vector的话,请注意上述问题。

构造完了之后,可以通过range-for-loop迭代

随机访问同样有 at 和 [] 两种选择,前者带范围检查,后者不带。

常规使用,记住以上内容就可以了。

哈希表:std::unordered_map<K, V>

本篇介绍的最后一个常用的数据结构。

这里特别演示了自定义K的方式。需要一个std::hash<MyKey>结构和重载==方法。

和 std::vector 一样,这里不使用 initailizer_list 初始化 map 避免比必要的复制。添加KV对的方式有好几种

  • emplace,rvalue(这里是临时值),一次move
  • emplace,lvalue(key3),一次copy
  • insert + make_pair,两次move

和 std::vector 不同的是,考虑到 unordered_map 是专门为查找使用的容器,所以 key 被复制个人认为没有太大问题,上述代码中也看到,查询时需要一个key,存放时又需要保证key被容器所管理,所以copy是无法避免的。

查找时,返回的是一个迭代器,如果不为 map.end() ,表示找到,并且调用 map_it-> second 得到KV对的value。这里 *map_it 的类型是 std::pair。

删除可以用迭代器,也可以用 key,这里演示了用key的方式。

小结

总体来说,C++11的数据结构很基础,还不足以达到其他更高级的编程语言的易用性,所以会有很多自制的 string,比如Qt的QString。

除了这里的vector和unordered_map,C++还有链表list,基于红黑树的有序映射表map等等。如果上面这两个基础的数据结构你会使用了的话,其他的数据结构相信你也知道如何使用。

这里还有一些头文件 <algorithm> 中的方法没有列出来,C++里,使用algorithm里面的方法加lambda可以做一些比较有趣的事情。有机会下次介绍。

作为补充,推荐《C++ Cookbook》。虽然这本书可能有点早,但是对于开发中常见的问题都会直接的解决方案以及解释,很适合作为C++开发的参考。


One response to “【C++11】字符串与常用数据结构”

  1. 感谢分享!已推荐到《开发者头条》:https://toutiao.io/posts/hekyl6 欢迎点赞支持!使用开发者头条 App 搜索 385148 即可订阅《并发与分布式系统研究》