Skip to content

Latest commit

 

History

History
523 lines (410 loc) · 19.7 KB

a9.md

File metadata and controls

523 lines (410 loc) · 19.7 KB
Raw

容器

下面代码需要先下载如下网址的single header文件 https://github.com/adah1972/output_container

output_container.h的使用范例如下:

#include <iostream>
#include <map>
#include <vector>
#include "output_container.h"

using namespace std;

int main()
{
	map<int, int> mp{
		{1, 1}, {2, 4}, {3, 9};
	}
	cout << mp << endl;
	vector<vector<int> vv{
		{1, 1}, {2, 4}, {3 ,9}
	};
	cout << vv << endl;
}

上述代码输出如下:

{ 1 => 1, 2 => 4, 3 => 9 }
{ { 1, 1 }, { 2, 4 }, { 3, 9 } }

string

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

跟其他大部分容器一样， string具有下列成员函数：

  • begin 可以得到对象起始点
  • end 可以得到对象的结束点
  • empty 可以得到容器是否为空
  • swap 可以和另外一个容器交换其内容

编码语言的习惯区间都为左闭右开,c++也如此。即C++的 begin和end是半开半闭区间：在容器非 空时，begin指向一个第一个元素，而end 指向最后一个元素后面的位置；在容器为空 时，begin等于end。在string的情况下，由于考虑到和C 字符串的兼容，end指向代 表字符串结尾的\0字符

上面就几乎是所有容器的共同点了。也就是说：

  • 容器都有开始和结束点
  • 容器会记录其状态是否非空
  • 容器有大小
  • 容器支持交换 当然，这只是容器的“共同点”而已。每个容器都有其特殊的用途。 string的内存布局大致如下图所示：

不管是内存布局，还是成员函数，string 和 vector 是非常相似的。

string支持如下函数:

  1. 字符拼接(+,+=)
  2. 字符串的查找(find和rfind)
  3. 支持istream读入字符串(getline)
  4. 支持通过const char*接口传递字符串内存(c_str)
  5. 支持数字互转(stoi和to_string)

如果不修改字符串,使用const string&或C++ 17的string_view作为类型参数最佳。推荐使用string_view它在只有C字符串的情况下,也不会引发不必要的内存复制。

下面看一个简单的例子:

string name;
cout << "What's your name? ";
getline(cin, name);
cout << "Nice to meet you, " << name
 << "!\n";

// 上述代码输出
/*
What's your name? hlt   (注这个hlt是我输入的)
Nice to meet you, hlt!
*/

vector

动态数组

基本相当于Java的ArrayList和Python的list。 和 string 相似，vector的成员在内存里连续存放，同时begin、end、front、back 成员函数指向的位置也和string 一样，大致如下图所示：

  • data 来获得指向其内容的裸指针（同 string）
  • capacity 来获得当前分配的存储空间的大小，以元素数量计（同 string）
  • reserve 来改变所需的存储空间的大小，成功后capacity()会改变（同 string）
  • resize 来改变其大小，成功后size()会改变（同 string）
  • pop_back 来删除最后一个元素（同 string）
  • push_back 在尾部插入一个元素（同 string）
  • insert 在指定位置前插入一个元素（同 string）
  • erase 在指定位置删除一个元素（同 string）
  • emplace 在指定位置构造一个元素
  • emplace_back 在尾部新构造一个元素

留意push_…和pop_… 成员函数。它们存在时，说明容器对指定位置的删除 和插入性能较高。vector 适合在尾部操作，这是它的内存布局决定的。只有在尾部插入和 删除时，其他元素才会不需要移动，除非内存空间不足导致需要重新分配内存空间。

当 push_back、insert、reserve、resize 等函数导致内存重分配时，或当 insert、erase 导致元素位置移动时，vector 会试图把元素“移动”到新的内存区域

注: vector通常保证强异常安全性，如果元素类型没有提供一个保证不抛异常的移动构造函 数，vector通常会使用拷贝构造函数。对于拷贝代价较高的自定义元素类型， 应当定义移动构造函数，并标其为noexcept，或只在容器中放置对象的智能指针。

准则:如果对象要放入到vector中尽量要给对象实现移动构造函数(move constractor)并且要用noexcept修饰该函数。

右值引用的具体阐述请看: C++的优化以及右值引用的价值

下面代码 源文件

#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&)
Obj2()
Obj2()
Obj2()
Obj2(Obj2&&)
Obj2(Obj2&&)
*/

Obj1和Obj2的定义只差了一个noexcept，但这个小小的差异就导致了vector是否会移动对象。这点非常重要。 C++11开始提供的emplace… 系列函数是为了提升容器的性能而设计的。把 v1.emplace_back() 改成 v1.push_back(Obj1())。对于vector里的内容，结果是 一样的；但使用push_back会额外生成临时对象，多一次拷贝构造和一次析构。 现代处理器的体系架构使得对连续内存访问的速度比不连续的内存要快得多。因而，vector的连续内存使用是它的一大优势所在。 vector的一个主要缺陷是大小增长时导致的元素移动。如果可能，尽早使用 reserve 函数为 vector 保留所需的内存，这在 vector预期会增长到很大时能带来很大的性能提升。

deque

双端队列

容器不仅可以从尾部自由地添加和删除元素，也可以从头部自由地添加和删除。

deque 提供 push_front、emplace_front 和 pop_front 成员函数。

内存布局如下:

  1. 如果只从头、尾两个位置对deque进行增删操作的话，容器里的对象永远不需要移动。
  2. 容器里的元素只是部分连续的（因而没法提供data成员函数）。
  3. 由于元素的存储大部分仍然连续，它的遍历性能是比较高的。
  4. 由于每一段存储大小相等，deque支持使用下标访问容器元素，大致相当于index[i / chunk_size][i % chunk_size]，因此访问deque中的元素依然很高效。

C++中deque非常少用，因为deque和list等数据结构更流行侵入式的。

list和forward

这个不做赘述了，链表基本没人用。

queue

还有两个类容器。它们的特别点在于它们都不是完整的实现，而 是依赖于某个现有的容器，因而被称为容器适配器（container adaptor）。

先看一下队列 queue，先进先出（FIFO）的数据结构。 queue 缺省用 deque 来实现。它的接口跟 deque 比，有如下改变：

不能按下标访问元素 没有 begin、end 成员函数 用 emplace 替代了 emplace_back，用 push 替代了 push_back，用 pop 替代了 pop_front；没有其他的 push_…、pop_…、emplace…、insert、erase 函数

鉴于 queue 不提供 begin 和 end 方法，无法无损遍历，我们只能用下面的代码约略展示 一下其接口：

#include <iostream>
#include <queue>

int main()
{
	std::queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);

	while (!q.empty()) {
		std::cout << q.front() << std::endl;
		q.pop();
	}
}

push入队,pop出队,front获取队列头部元素。

stack

类似地，栈 stack 是后进先出（LIFO）的数据结构。 queue 缺省也是用 deque 来实现，但它的概念和 vector 更相似。它的接口跟 vector 比，有如下改变：

不能按下标访问元素 没有 begin、end 成员函数 back 成了 top，没有 front 用 emplace 替代了 emplace_back，用 push 替代了 push_back，用 pop 替代了 pop_back；没有其他的 push_…、pop_…、emplace…、insert、erase 函数

一般图形表示法会把 stack 表示成一个竖起的 vector：

这里有一个小细节需要注意。stack 跟我们前面讨论内存管理时的栈有一个区别：在这里 下面是低地址，向上则地址增大；而我们讨论内存管理时，高地址在下面，向上则地址减 小，方向正好相反。提这一点，是因为在有需要检查栈结构时不会因此而发生混淆；在使 用 stack 时，这个区别通常无关紧要。

示例代码和上面的 代码 相似，但输出正好相反：

#include <iostream>
#include <stack>

int main()
{
	std::stack<int> s;
	s.push(1);
	s.push(2);
	s.push(3);

	while (!s.empty()) {
		std::cout << s.top() << std::endl;
		s.pop();
	}
}

priority_queue

priority_queue 也是一个容器适配器。上一讲没有和其他容器适配器一起讲的原因就在 于它用到了比较函数对象（默认是 less）。它和 stack 相似，支持 push、pop、top 等 有限的操作，但容器内的顺序既不是后进先出，也不是先进先出，而是（部分）排序的结 果。在使用缺省的 less 作为其 Compare 模板参数时，大的数值会出现在容器的“顶 部”。如果需要小的数值出现在容器顶部，则可以传递 greater 作为其 Compare 模板参数

#include <functional>
#include <iostream>
#include <memory>
#include <queue>
#include <vector>

using namespace std;

int main()
{
	priority_queue<
		pair<int, int>,
		vector<pair<int, int>>,
		greater<pair<int, int>>
	> q;
	q.push({1, 1});
	q.push({2, 2});
	q.push({0, 3});
	q.push({9, 4});
	while (!q.empty()) {
		cout << q.top() << endl;
		q.pop();
	}
}

输出为:

(0, 3)
(1, 1)
(2, 2)
(9, 4)

关联容器和无序关联容器

关联容器

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

#include <functional>
#include <map>
#include <set>
#include <string>

using namespace std;

int main()
{
	set<int> s{1, 1, 1, 2, 3, 4}; // 里面元素只有1,2,3,4
	multiset<int, greater<int>> ms{1, 1, 2, 3, 4}; // 元素为且从大到小排列 4, 3, 2, 1, 1
	// 初始化map
	map<string, int> mp {
		{"one", 1},
		{"two", 2},
		{"three", 3},
		{"four", 4}
	};
	// map添加元素
	mp.insert({"five", 5});
	if (mp.find("four") == mp.end())
	{
		// 判断four为key是否在map中出现
	}

	// 添加元素第二种方法
	mp["six"] = 6;

	multimap<string, int> mmp{
		{"one", 1},
		{"two", 2},
		{"three", 3},
		{"four", 4}
	};
	// 如果是map就会覆盖，而multimap允许重复键值对
	mmp.insert({"four", -4});
	return 0;
}

关联容器是一种有序的容器。名字带“multi”的允许键重复，不带的不允许键 重复。set 和 multiset 只能用来存放键，而 map 和 multimap 则存放一个个键值对。 与序列容器相比，关联容器没有前、后的概念及相关的成员函数，但同样提供 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， 可以一次性取得上下界(左闭右开)。如下所示

#include <tuple>
#include <map>
#include <iostream>
#include <string> 	

using namespace std;

int main()
{
	multimap<string, int> mmp{
		{"one", 1},
		{"two", 2},
		{"three", 3},
		{"four", 4}
	};
	// 如果是map就会覆盖，而multimap允许重复键值对
	mmp.insert({"four", -4});
	multimap<string, int>::iterator  lower, upper;
	// tie函数作用是把多个变量引用整合成一个tuple,tuple可以理解为多个参数的集合(pair是两个参数的集合)
	std::tie(lower, upper) = mmp.equal_range("four");
	if (lower != upper) { // 区间是否非空
		std::cout << lower->second << std::endl;
		std::cout << (--upper)->second << std::endl; // 左闭右开所以右边下标要--
	}
	return 0;
}

如果在声明关联容器时没有提供比较类型的参数，缺省使用 less 来进行排序。如果键的类型提供了比较算符 < 的重载，我们不需要做任何额外的工作。否则，我们就需要对键类型 进行 less 的特化，或者提供一个其他的函数对象类型。 对于自定义类型，推荐尽量使用标准的 less 实现，即通过重载 <（及其他标准比较运算 符）对该类型的对象进行排序。存储在关联容器中的键一般应满足严格弱序关系（strict weak ordering），即：

  • 对于任何该类型的对象 x：!(x < x)（非自反）
  • 对于任何该类型的对象 x 和 y：如果 x < y，则 !(y < x)（非对称）
  • 对于任何该类型的对象 x、y 和 z：如果 x < y 并且 y < z，则 x < z（传递性）
  • 对于任何该类型的对象 x、y 和 z：如果 x 和 y 不可比（!(x < y) 并且 !(y < x)） 并且 y 和 z 不可比，则 x 和 z 不可比（不可比的传递性）

大部分情况下，类型是可以满足这些条件的，不过：

  • 如果类型没有一般意义上的大小关系（如复数），我们一定要别扭地定义一个大小关系吗？
  • 通过比较来进行查找、插入和删除，复杂度为对数 O(log(n))，有没有达到更好的性能的方法？

无序关联容器

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

unordered_set
unordered_map
unordered_multiset
unordered_multimap

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

#include <complex> // c++自带的复数实现
#include <iostream>
#include <unordered_map>
#include <unordered_set>


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()
{
	std::unordered_set<int> s{
		1, 1, 2, 3, 5, 8, 13, 21
	};

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

	std::unordered_map<std::complex<double>, double>  umc{
		{{1.0, 1.0}, 1.4142},
		{{3.0, 4.0}, 5.0}
	};

	for (auto i : umc) {
		std::cout << "(" << i.first.real() << "," << i.first.imag() << ")" << " " << "=> " << i.second << " ";
	}
	std::cout << std::endl;
	return 0;
}

输出为:

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

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

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

总结

  1. SequenceContainers：维持顺序的容器。
  • vector：动态数组，是我们最常使用的数据结构之一，用于 O(1)的随机读取。因为大 部分算法的时间复杂度都会大于O(n)，因此我们经常新建vector来存储各种数据或中 间变量。因为在尾部增删的复杂度是O(1)，我们也可以把它当作stack来用。
  • list：双向链表，也可以当作stack和queue来使用。由于链表不支持快速随机读取，因此我们很少用到这个数据结构。一个例外是经典的LRU问题，我们需要利用链表的特性来解决。
  • deque：双端队列，这是一个非常强大的数据结构，既支持O(1)随机读取，又支持O(1) 时间的头部增删和尾部增删，不过有一定的额外开销。
  • array：固定大小的数组，一般不使用。
  • forward_list：单向链表，一般不使用。
  1. ContainerAdaptors：基于其它容器实现的数据结构。
  • stack：后入先出（LIFO）的数据结构，默认基于deque实现。stack常用于深度优先搜索、一些字符串匹配问题以及单调栈问题。
  • queue：先入先出（FIFO）的数据结构，默认基于 deque实现。queue常用于广度优先 搜索。 (c).
  • priority_queue： 最大值先出的数据结构，默认基于vector实现堆结构。它可以在O(nlogn) 的时间排序数组，O(logn)的时间插入任意值，O(1)的时间获得最大值，O(logn)的时 间删除最大值。priority_queue常用于维护数据结构并快速获取最大或最小值。
  1. AssociativeContainers：实现了排好序的数据结构。
  • set：有序集合，元素不可重复，底层实现默认为红黑树，即一种特殊的二叉查找树 （BST）。它可以在 O(nlogn) 的时间排序数组，O(logn) 的时间插入、删除、查找任 意值，O(logn) 的时间获得最小或最大值。这里注意，set 和 priority_queue 都可以用 于维护数据结构并快速获取最大最小值，但是它们的时间复杂度和功能略有区别，如 priority_queue默认不支持删除任意值，而set获得最大或最小值的时间复杂度略高，具 体使用哪个根据需求而定。 (b).
  • multiset：支持重复元素的set。
  • map：有序映射或有序表，在set的基础上加上映射关系，可以对每个元素key存一个 值value。
  • multimap：支持重复元素的map。 4. UnorderedAssociativeContainers：对每个AssociativeContainers实现了哈希版本。
  • unordered_set：哈希集合，可以在 O(1)的时间快速插入、查找、删除元素，常用于快 速的查询一个元素是否在这个容器内。
  • unordered_multiset：支持重复元素的unordered_set。
  • unordered_map：哈希映射或哈希表，在unordered_set的基础上加上映射关系，可以对 每一个元素key存一个值value。在某些情况下，如果key的范围已知且较小，我们也 可以用vector代替unordered_map，用位置表示key，用每个位置的值表示value。
  • unordered_multimap：支持重复元素的unordered_map。