「LeetCode」C++ 常用容器类总结

2020-03-30
摘要: 本文总结了 C++ 常见容器类的主要用法。

请先掌握 C++ 迭代器相关知识。

容器类型
顺序型容器 vector 底层实现是数组,在尾部插入删除,动态成倍扩容。中间插入删除 $O(n)$,尾部插入删除、查找 $O(1)$
deque 底层是分段连续的线性空间,它是一种具有队列和栈的性质的数据结构,其插入和删除操作限定在两端进行。中间插入删除 $O(n)$,两端插入删除 、查找 $O(1)$。
list 底层实现为双向链表。可以快速地插入删除($O(1)$),但是查找需要 $O(n)$。
关联类容器 set/multiSet 底层实现是红黑树,键值有序,set 和 map 键不可重复,而 multiset 和 multimap 可重复。插入查找删除: $O(\log(n))$
unorderd_set/unordered_multiSet 底层实现是哈希表,键值无序,unordered_set 和 unordered_map 键不可重复,而另外两个可以重复。插入查找删除平均 $O(1)$,最坏 $O(n)$。
map/multiMap 底层实现是红黑树,键值有序,set 和 map 键不可重复,而 multiset 和 multimap 可重复。插入查找删除: $O(\log(n))$。
unorderd_map/unordered_multiMap 底层实现是哈希表,键值无序,unordered_set 和 unordered_map 键不可重复,而另外两个可以重复。插入查找删除平均 $O(1)$,最坏 $O(n)$
容器适配器 stack 底层实现一般用 deque,封闭头部即可,数据先进后出,不支持随机访问。各种操作都为 $O(1)$。
queue 底层实现一般用 deque,数据先进先出,不支持随机访问。各种操作都为 $O(1)$。
priority_queue 底层用堆实现,队列中各个元素被赋予优先级。插入删除 $O(\log(n))$,取堆顶 $O(1)$。

顺序类容器#

他们的操作大同小异,我们主要以 vector 为例子。

vector#

#include <vector>

初始化#

vector<int> v; // size = 0
vector<int> v(10); // size = 10
vector<int> v(5, 0); // repeat five zeros
vector<int> v = {1, 2, 4}; // initialize with constants
vector<int> v{1, 2, 4}; // initialize with constants

/* if we already have an array */
int  array[3] = {0, 1, 2};
vector<int> v(&array[0], &array[2]); // copy elements from array using addresses.
// or:
vector<int> v;
v.insert(v.begin(), &array[0], &array[2]);

/* if we already have an vector */
vector<int> v = {1, 2, 4};
vector<int> v1(v);

/* if we already have a container(set, vector...) */
vector<int> v2(container.begin(), container.end());

属性#

vector<int> v = {1, 2, 4};
v.empty(); // checks whether the container is empty 
v.size(); // the number of elements
v.capacity(); // the number of elements that can be held

查找#

vector<int> v = {1, 2, 4};
v[0] == 1;
v.at(0) == 1; // the same as [] operator
v.front(); // element
v.back(); // element

v.begin(); // iterator
v.end(); // iterator
v.rbegin(); // last element iterator
v.rend(); // v.begin()

修改#

插入和删除必须用迭代器。vector 没有针对首部的操作。

vector<int> v = {1, 2, 4};

v.push_back(8);
v.pop_back();
// there is no push_front

v.insert(v.begin(), 0);
v.insert(v.begin(), 5, 0); // five zeros
v.insert(v.begin(), v2.begin(), v2.end()); // insert another vector

v.erase(v.begin());
v.erase(v.begin(), v.end()) // erase [begin, end)
v.clear()

reverse(v.begin(), v.end());

deque 双端队列#

#include <deque>

成员函数只比 vector 多了头部的操作

dq.push_front(0);
dq.pop_front();

list 双向链表#

#include <list>

成员函数与 deque 相同

功能性函数#

splice(), merge(), sort()

关联类容器#

set/multiset, map/multimap 都是有序的,默认升序排列,自动排序。内部是平衡二叉树(红黑树)。左子树元素都比自己小,右子树元素都比自己大。

unordered_set/unordered_multiset, unordered_map/unordered_multimap 是无序的,通过哈希实现。元素在容器中的位置由元素的哈希值决定。默认用 equal_to<T> 对象来判断元素是否相等。

从有序和无序关联容器获取的各种迭代器之间有一些区别。我们可以从有序容器得到正向和反向迭代器,但是只能从无序容器得到正向迭代器

一般来说,当 set 中有大量元素时,在无序 set 上执行的随机插入和检索操作要比有序 set 快。在有 n 个元素的有序 set 中检索元素的时间复杂度是 $\log n$。在无序 set 中检索元素的平均时间复杂度是常量,这和元素的个数无关,尽管实际性能会受元素哈希操作和内部组织效率的影响。

set#

目的是快速检索,去重或者排序。

每次操作为 $O(\log n)$。

#include <set>

初始化#

set<int> s;

set<int, less<int>> s; // the default case. In ascending order.
set<int, greater<int>> s;

set<int> s = {1, 2, 4};
set<int> s{1, 2, 4};

/* if we already have an array */
int  array[3] = {0, 1, 2};
set<int> s(&array[0], &array[2]); // copy elements from array using addresses.

/* if we already have a set */
set<int> s1(s);

/* if we already have a container(set, vector...) */
set<int> s1(container.begin(), container.end());
自定义比较函数#
元素不是结构体#

自定义 myComp,重载 () 操作符。

struct myComp {
  bool operator() (const your_type& a, const your_type& b) {
    return a.data > b.data;
  }
}

set<yout_type, myComp> s;
元素是结构体#

直接将比较函数写在结构体内。

struct Info {
  string name;
  float score;

  bool operator < (const Info &another) const {
    return score < another.score;
  }
}

set<Info> s;

属性#

s.size();
s.empty();
s.begin();
s.end();
s.rbegin();
s.rend();

查找#

set<int> s{1, 2, 2, 4};

s.find(1); // return iterator. return .end() if nil
s.count(1); // return the number of specific element
s.contains(1); // true or false. (C++20)

/* return std::pair containing a pair of iterators defining the wanted range: the first pointing to the first element that is not less than key and the second pointing to the first element greater than key. 
pr.first == s.begin() + 1, pr.second == s.begin() + 3 */
auto pr = s.equal_range(1);
auto it = s.lower_bound(2); // s.begin() + 1
auto it = s.upper_bound(2); // s.begin() + 3

修改#

s.clear();

s.erase(iterator);
s.erase(firstIterator, lastIterator); // [first; last)
s.erase(value);

/* return pair<set<int>::iterator, bool>. Returns a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool value set to true if the insertion took place. */
s.insert(value); 
s.insert(first, last); // [first, last). Support both array address and iterator
s.insert(s.first, 0); // inserts value in the position as close as possible
s.insert({6, 7, 8});

集合的交并差#

这几个函数都指定五个参数,前面四个参数是一样的,用于取范围,最后一个用于指定结果存放的位置。注意,这些操作可以作用在多种容器上,不只是 set 上,但是作用在 vector 上时,一定要保证其已经排序。这里只以 set_union 做为例子。

set_intersection()#
set_difference#
set_symmetric_difference#
set_union#
vector 例子#

back_inserter 意味着插在其后面(需要支持 push_back)。

std::vector<int> set1 {1, 2, 3, 4, 5, 6};
std::vector<int> set2 {4, 5, 6, 7, 8, 9};
std::vector<int> result;
std::set_union(std::begin (set1), std::end(set1), // Range for set that is left operand
std::begin(set2), std::end(set2), // Range for set that is right operand
std::back_inserter(result));    // Destination for the result:1 2 3 4 5 6 7 8 9
set 例子#
std:: set<int, std::greater<int>> set1 {1, 2, 3, 4, 5, 6}; // Contains 6 5 4 3 2 1
std:: set<int, std:: greater<int>> set2 {4, 5, 6, 7, 8, 9}; // Contains 9 8 7 6 5 4
std::set<int, std::greater<int>> result; // Elements in descending sequence
std::set_union(std::begin(set1), std::end(set1),
                                std::begin(set2), std::end(set2),
                                std::inserter(result, r));
                                std::inserter(result, result.begin()));
// Result destination: 9 8 7 6 5 4 3 2 1
// result.begin() 也可以改成别的迭代器
cout 例子#
std::set_union(std::begin(set1), std::end(set1), std::begin(set2), std::end(set2),std::ostream_iterator<int> {std::cout, " "}); // 间隔符为 " "

子集判断#

includes 函数用于判断子集关系,与数学中定义相同。

std::set<string> words1 { "one", "two", "three", "four", " five", "six"};
std::set<string> words2 {"four", "two", " seven"};
std::set<string> words3 {"four", "two"};

includes(std::begin(words1), std::end(words1), std::begin(words2), std::enwords2)); // false
includes(std::begin(words1), std::end(words1), std::begin(words3), std::end(words3)); // true

multiset#

成员函数与 set 相同,只不过表现不同。

unordered_set#

T 类型的对象在容器中的位置由它们的哈希值决定,因而需要定义一个 Hash<T> 函数。好在基本类型已经有了性能良好的哈希函数。成员函数基本相同。

img

每次操作为 $O(1)$,最坏为 $O(n)$。

map#

#include<map>

初始化#

map<string, int> m;
map<string, int, less<int>> m;
map<string, size_t> people{{"Ann", 25}, {"Bill", 46},{"Jack", 32},{"Jill", 32}};
map<string, size_t> personnel {people}; // Duplicate people map
map<string, size_t> personnel {begin(people), end(people)};
map<string,size_t> people{make_pair("Ann",25), make_pair("Bill", 46), make_pair("Jack", 32)};

插入#

map<int, float> m;
m.insert(pair<int, float>(10,2.3));
m.insert(make_pair(10,2.3));
m[key] = value;   //只能是 map 容器,不适用于 multimap

查找#

// 配合 m.count(key) 使用
m.at(key); // 如果 key 不存在对应的值,会报错。
m[key]; // 慎用。如果 key 不存在对应的值,会插入一个默认值并返回。

删除#

m.erase(key);
m.erase(begin, end);
m.clear();

multimap#

multimap 大部分成员函数的使用方式和 map 相同。因为重复键的原因,multimap 有一些函数的使用方式和 map 有一些区别。

multimap 不支持下标运算符,因为键并不能确定一个唯一元素。和 map 相似,multimap 也不能使用 at() 函数。multimap 的成员函数 fmd() 可以返回一个键和参数匹配的元素的迭代器。

一般来说,我们想访问给定键对应的所有元素。成员函数 equal_range() 就可以做到这一点。它会返回一个封装了两个迭代器的 pair 对象,这两个迭代器所确定范围内的元素的键和参数值相等。例如:

auto pr = people.equal_range("Ann");
if(pr.first != std::end(people))
{
    for (auto iter = pr.first ; iter != pr.second; ++iter)
        std:cout << iter->first << " is " << iter->second << std::endl;
}

multimap 的成员函数 lower_bound() 会返回一个迭代器,它指向键值和参数相等或大于参数的第一个元素,或者指向结束迭代器。upper_bound() 也返回一个迭代器,它指向键值大于函数参数的第一个元素,如果这样的元素不出现的话,它就是一个结束迭代器。所以,当存在一个或多个相等键时,这些函数会返回一个开始迭代器和一个结束迭代器,它们指定了和参数匹配的元素的范围,这和 equal_range() 返回的迭代器是相同的。因而前面的代码段可以这样重写:

auto iter1 = people.lower_bound("Ann");
auto iter2 = people.upper_bound("Ann");
if(iter1 != std::end(people))
{
    for(auto iter = iterl ; iter != iter2; ++iter)
        std::cout << iter->first << " is " << iter->second << std::endl;
}

distance() 函数模板运用到成员函数 equal_range() 返回的迭代器或者 lower_bound()upper_bound() 返回的迭代器上,可以获取键和给定键相等的元素的个数:

std::string key{"Jack"};
auto n = std::distance( people.lower_bound(key), people.upper_bound(key)); // No. of elements matching key

自定义比较函数#

map 容器的比较函数在相等时不能返回 true,换句话说,不能使用<=>=来比较。这是为什么? map 或 multimap 容器用等价来判断键是否相等。如果表达式 key1<key2key2<key1 的结果都是 false,那么 key1key2 是等价的,所以它们被认为是相等的。换一种方式,等价意味着 !(key1<key2)&&!(key2<key1) 的运算值为 true。如果我们的函数对象实现了 <=,思考一下会发生什么。当 key1key2 相等时,key1<=key2 key2<=key1 都为 true,因而表达式 !(key1<=key2)&&!(key2<=key1)false,这意味着来自于容器的这两个键竟然不相等。

方法和 set 相同。

unordered_map#

生成 unordered_map 容器和生成 map 一样简单,只要可以用 hash<K> 的实例哈希 k 类型的键,而且必须能够用 == 运算符来比较键。成员函数相同。

容器适配器#

容器适配器是一个封装了序列容器的类模板,它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类,是因为它可以通过适配容器现有的接口来提供不同的功能。

stack#

是一个封装了 deque<T> 容器的适配器类模板。stack<T> 模板定义在头文件 stack 中。

创建堆栈时,不能在初始化列表中用对象来初始化,但是可以用另一个容器来初始化,只要堆栈的底层容器类型和这个容器的类型相同。例如:

list<double> values {1.414, 3.14159265, 2.71828};
stack<double, list<double>> my_stack (values); // 一个基于 list 的 stack
stack<double, list<double>> copied_stack (my_stack); // 拷贝另一个 stack

如果没有在第二个 stack 模板类型参数中将底层容器指定为 list,那么底层容器可能是 deque,这样就不能用 list 的内容来初始化 stack;只能接受 deque。

操作#

s.top();
s.push(const T& obj);
s.pop();
s.size();
s.empty();

queue#

是一个封装了 deque<T> 容器的适配器类模板。queue<T> 模板定义在头文件 queue 中。只能访问 queue<T> 容器适配器的第一个和最后一个元素。只能在容器的末尾添加新元素,只能从头部移除元素。生成方式与 stack 相同。

操作#

q.front();
q.back();
s.push(const T& obj);
q.pop();
q.size();
q.empty();

priority_queue#

是一个封装了 vector<T> 容器的适配器类模板,默认实现的是一个会对元素排序,从而保证最大元素总在队列最前面的队列。priority_queue<T> 模板定义在头文件 queue 中。

注意在 priority_queue 中,遍历顺序与比较器是相反的,less 的默认情况反而是从大到小遍历的。

priority_queue<int> p; 
priority_queue<int, vector<int>, greater<int>> p;  // 自定义顺序。

p.push(const T& obj);
p.top();
p.pop();

自定义比较函数参考 set 与 map。简单来说,使用 less<int> 只需要重载 < 号即可。