目录

一、概述

二、Template

2.0 string(string - C++ Reference)

 2.1array

 2.2vector

 2.3deque

 2.4list

 2.5forward_list

 2.7map

 2.8multimap

 2.9set

 2.10multiset

 2.11unordered_map

 2.12unordered_multimap

 2.13unordered_set

 2.14unordered_multiset

 2.15stack（栈）

 2.16queue（队列）

 2.17priority_queue（优先队列）

三、容器对比 

3.2顺序容器 

3.2有序关联容器

3.3无序关联容器

3.4容器适配器

四、常用函数

4.1顺序容器

4.2关联容器

一、概述

	顺序容器	有序关联容器	无序关联容器	容器适配器
特点	1、只有实值 2、不涉及排序 3、通过元素在容器的位置顺序存储和访问元素	1、键值对（key，val） 2、内部自动排序 3、通过键存储和读取 3、以键值的方式来保存数据，就是说它能把关键字和值关联起来保存。		容器的模版 容器的容器 容器的接口
结构	一种各元素之间有顺序关系的线性表，是一种线性结构的可序群集。	关联式容器是非线性的树结构，更准确的说是二叉树结构。
容器	1、array 2、vector 3、deque 4、list 5、forward_list	1、map(元素唯一) 2、set(元素唯一) 3、multimap(元素可重复) 4、multiset(元素可重复)	1、unordered_map 2、unordered_set 3、unordered_multimap 4、unordered_multiset	（接口） 1、stack 2、queue 3、priority_queue
底层		红黑树	散列表
注意： 1、set和map的区别：map是一个键值对，set也是一个键值对，但是key=val。 2、有无multi的区别：有multi表示容器内的元素可重复。 3、有无unordered的区别：有unordered表示容器内的元素不会自动排序。

二、Template

2.0 string(string - C++ Reference)

  std::string s0 ("Initial string");

  // constructors used in the same order as described above:
  std::string s1;
  std::string s2 (s0);
  std::string s3 (s0, 8, 3);
  std::string s4 ("A character sequence");
  std::string s5 ("Another character sequence", 12);
  std::string s6a (10, 'x');
  std::string s6b (10, 42);      // 42 is the ASCII code for '*'
  std::string s7 (s0.begin(), s0.begin()+7);

 2.1array

template < class T, size_t N > class array;

 2.2vector

template < class T, class Alloc = allocator > class vector; // generic template

// constructors used in the same order as described above:
  std::vector first;                                // empty vector of ints
  std::vector second (4,100);                       // four ints with value 100
  std::vector third (second.begin(),second.end());  // iterating through second
  std::vector fourth (third);                       // a copy of third

  // the iterator constructor can also be used to construct from arrays:
  int myints[] = {16,2,77,29};
  std::vector fifth (myints, myints + sizeof(myints) / sizeof(int) );

 2.3deque

template < class T, class Alloc = allocator > class deque;

  std::deque mydeck (3,100);        // deque with 3 elements
  std::list mylist (2,200);         // list with 2 elements

  std::queue first;                 // empty queue
  std::queue second (mydeck);       // queue initialized to copy of deque

  std::queue > third; // empty queue with list as underlying container
  std::queue > fourth (mylist);

 2.4list

template < class T, class Alloc = allocator > class list;

// constructors used in the same order as described above:
  std::list first;                                // empty list of ints
  std::list second (4,100);                       // four ints with value 100
  std::list third (second.begin(),second.end());  // iterating through second
  std::list fourth (third);                       // a copy of third

  // the iterator constructor can also be used to construct from arrays:
  int myints[] = {16,2,77,29};
  std::list fifth (myints, myints + sizeof(myints) / sizeof(int) );

 2.5forward_list

template < class T, class Alloc = allocator > class forward_list;

  std::forward_list first;                      // default: empty
  std::forward_list second (3,77);              // fill: 3 seventy-sevens
  std::forward_list third (second.begin(), second.end()); // range initialization
  std::forward_list fourth (third);            // copy constructor
  std::forward_list fifth (std::move(fourth));  // move ctor. (fourth wasted)
  std::forward_list sixth = {3, 52, 25, 90};    // initializer_list constructor

 2.7map

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less,                     // map::key_compare
           class Alloc = allocator >    // map::allocator_type
           > class map;

#include 
#include 

 2.8multimap

template < class Key,                                     // multimap::key_type
           class T,                                       // multimap::mapped_type
           class Compare = less,                     // multimap::key_compare
           class Alloc = allocator >    // multimap::allocator_type
           > class multimap;

#include 
#include 

 2.9set

template < class T,                        // set::key_type/value_type
           class Compare = less,        // set::key_compare/value_compare
           class Alloc = allocator      // set::allocator_type
           > class set;

#include 
#include 

bool fncomp (int lhs, int rhs) {return lhs first;                           // empty set of ints

  int myints[]= {10,20,30,40,50};
  std::set second (myints,myints+5);        // range

  std::set third (second);                  // a copy of second

  std::set fourth (second.begin(), second.end());  // iterator ctor.

  std::set fifth;                 // class as Compare

  bool(*fn_pt)(int,int) = fncomp;
  std::set sixth (fn_pt);  // function pointer as Compare

  return 0;
}

 2.10multiset

template < class T,                        // multiset::key_type/value_type
           class Compare = less,        // multiset::key_compare/value_compare
           class Alloc = allocator >    // multiset::allocator_type
           > class multiset;

#include 
#include 

bool fncomp (int lhs, int rhs) {return lhs first;                          // empty multiset of ints

  int myints[]= {10,20,30,20,20};
  std::multiset second (myints,myints+5);       // pointers used as iterators

  std::multiset third (second);                 // a copy of second

  std::multiset fourth (second.begin(), second.end());  // iterator ctor.

  std::multiset fifth;                // class as Compare

  bool(*fn_pt)(int,int) = fncomp;
  std::multiset sixth (fn_pt); // function pointer as Compare

  return 0;
}

 2.11unordered_map

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash,                       // unordered_map::hasher
           class Pred = equal_to,                   // unordered_map::key_equal
           class Alloc = allocator< pair >  // unordered_map::allocator_type
           > class unordered_map;

#include 
#include 
#include 

typedef std::unordered_map stringmap;

stringmap merge (stringmap a,stringmap b) {
  stringmap temp(a); temp.insert(b.begin(),b.end()); return temp;
}

int main ()
{
  stringmap first;                              // empty
  stringmap second ( {{"apple","red"},{"lemon","yellow"}} );       // init list
  stringmap third ( {{"orange","orange"},{"strawberry","red"}} );  // init list
  stringmap fourth (second);                    // copy
  stringmap fifth (merge(third,fourth));        // move
  stringmap sixth (fifth.begin(),fifth.end());  // range

  std::cout << "sixth contains:";
  for (auto& x: sixth) std::cout << " " << x.first << ":" << x.second;
  std::cout << std::endl;

  return 0;
}

 2.12unordered_multimap

template < class Key,                                    // unordered_multimap::key_type
           class T,                                      // unordered_multimap::mapped_type
           class Hash = hash,                       // unordered_multimap::hasher
           class Pred = equal_to,                   // unordered_multimap::key_equal
           class Alloc = allocator< pair >  // unordered_multimap::allocator_type
           > class unordered_multimap;

#include 
#include 
#include 

template
T cmerge (T a, T b) { T t(a); t.insert(b.begin(),b.end()); return t; }

int main ()
{
  std::unordered_set first;                                // empty
  std::unordered_set second ( {"red","green","blue"} );    // init list
  std::unordered_set third ( {"orange","pink","yellow"} ); // init list
  std::unordered_set fourth ( second );                    // copy
  std::unordered_set fifth ( cmerge(third,fourth) );       // move
  std::unordered_set sixth ( fifth.begin(), fifth.end() ); // range

  std::cout << "sixth contains:";
  for (const std::string& x: sixth) std::cout << " " << x;
  std::cout << std::endl;

  return 0;
}

 2.13unordered_set

template < class Key,                        // unordered_set::key_type/value_type
           class Hash = hash,           // unordered_set::hasher
           class Pred = equal_to,       // unordered_set::key_equal
           class Alloc = allocator      // unordered_set::allocator_type
           > class unordered_set;

#include 
#include 
#include 

template
T cmerge (T a, T b) { T t(a); t.insert(b.begin(),b.end()); return t; }

int main ()
{
  std::unordered_set first;                                // empty
  std::unordered_set second ( {"red","green","blue"} );    // init list
  std::unordered_set third ( {"orange","pink","yellow"} ); // init list
  std::unordered_set fourth ( second );                    // copy
  std::unordered_set fifth ( cmerge(third,fourth) );       // move
  std::unordered_set sixth ( fifth.begin(), fifth.end() ); // range

  std::cout << "sixth contains:";
  for (const std::string& x: sixth) std::cout << " " << x;
  std::cout << std::endl;

  return 0;
}

 2.14unordered_multiset

template < class Key,                         // unordered_multiset::key_type/value_type
           class Hash = hash,            // unordered_multiset::hasher
           class Pred = equal_to,        // unordered_multiset::key_equal
           class Alloc = allocator       // unordered_multiset::allocator_type
           > class unordered_multiset;

#include 
#include 
#include 

template
T cmerge (T a, T b) { T t(a); t.insert(b.begin(),b.end()); return t; }

int main ()
{
  std::unordered_multiset first;                                // empty
  std::unordered_multiset second ( {"red","green","blue"} );    // init list
  std::unordered_multiset third ( {"red","yellow","blue"} );    // init list
  std::unordered_multiset fourth ( second );                    // copy
  std::unordered_multiset fifth ( cmerge(third,fourth) );       // move
  std::unordered_multiset sixth ( fifth.begin(), fifth.end() ); // range

  std::cout << "sixth contains:";
  for (const std::string& x: sixth) std::cout << " " << x;
  std::cout << std::endl;

  return 0;
}

 2.15stack（栈）

template  > class stack;

  std::deque mydeque (3,100);          // deque with 3 elements
  std::vector myvector (2,200);        // vector with 2 elements

  std::stack first;                    // empty stack
  std::stack second (mydeque);         // stack initialized to copy of deque

  std::stack > third;  // empty stack using vector
  std::stack > fourth (myvector);

 2.16queue（队列）

template  > class queue;

  std::deque mydeck (3,100);        // deque with 3 elements
  std::list mylist (2,200);         // list with 2 elements

  std::queue first;                 // empty queue
  std::queue second (mydeck);       // queue initialized to copy of deque

  std::queue > third; // empty queue with list as underlying container
  std::queue > fourth (mylist);

 2.17priority_queue（优先队列）

template ,
  class Compare = less > class priority_queue;

#include        // std::cout
#include           // std::priority_queue
#include          // std::vector
#include      // std::greater

class mycomparison
{
  bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (const int& lhs, const int&rhs) const
  {
    if (reverse) return (lhs>rhs);
    else return (lhs first;
  std::priority_queue second (myints,myints+4);
  std::priority_queue, std::greater >
                            third (myints,myints+4);
  // using mycomparison:
  typedef std::priority_queue,mycomparison> mypq_type;

  mypq_type fourth;                       // less-than comparison
  mypq_type fifth (mycomparison(true));   // greater-than comparison

  return 0;
}

三、容器对比 

3.2顺序容器 

名称	说明	特点	方向	迭代器失效	插入	删除	查找	场景
string	字符串、顺序、随机访问		——	插入失效，删除不会	尾端O（1）非尾端P：O（N-P）	尾端O（1）非尾端P：O（N-P）	O（1）	类似vector，但是string删除元素不会释放空间（为了下次操作方便）
array	数组、顺序		——	固定长度	无	无	O（1）	类似vector，比数组更安全（不担心越界），但是内容在栈上，且属于定长容器。
vector	向量、顺序、随机访问	一个线性顺序结构。相当于数组，但其大小可以不预先指定，并且自动扩展。 vector 是一段连续的内存块	——	插入和删除都会失效	尾端O（1） 非尾端P：O（N-P）	尾端O（1） 非尾端P：O（N-P）	O（1）	需要快速查找，不需要频繁插入/删除
deque	队列、顺序、随机访问	一种优化了的、对序列两端元素进行添加和删除操作的基本序列容器。 采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。 deque 是多个连续的内存块。	双向	插入失效。删除头和尾元素，指向被删除节点迭代器失效，而删除中间元素会使所有迭代器失效	首尾端：O（1） 非首尾P：O（min（p， N-P））	首尾端：O（1） 非首尾P：O（min（p， N-P））	O（1）	头尾增删元素很快，随机访问比vector慢一点，因为内部处理堆跳转。中间插入和删除效率交较高。因为他是list和vector综合的样子。使用较少
list	列表容器、顺序	一个线性链表结构，它的数据由若干个节点构成，每一个节点都包括一数据、一个前驱指针和一个后驱指针。  list 是所有数据元素分开保存	双向	插入不失效，被删除节点自身失效。	O（1）	O（1）	O（N）	需要频繁插入/删除，不需要快速查找
forward_list	前向列表、顺序		单向	插入不失效，被删除节点自身失效。	O（1）	O（1）	O（N）	需要list的优势，但只要向前迭代

3.2有序关联容器

名称	说明	方向	特点	迭代器失效	插入	删除	查找	场景
map	映射有序关联	双向	链表	插入不失效。删除时只是被删除节点的迭代器失效，但迭代器返回void，所以需要保存删除前迭代器位置。	O(logN)	O(logN)	O(logN)	需要key有序将值关联到key，查找/删除/插入性能一样
multimap	多重映射有序关联	双向	链表	同上	O(logN)	O(logN)	O(logN)	同上
set	集合有序关联	双向	链表	同上	O(logN)	O(logN)	O(logN)	需要元素有序，查找/删除/插入性能一样。红黑树效率都是O(logN)。即使是几个亿的内容，最多也查几十次。
multiset	多重集合有序关联	双向	链表	同上	O(logN)	O(logN)	O(logN)	同上

3.3无序关联容器

名称	说明	方向	迭代器失效	插入	删除	查找	场景
unordered_map	映射无序关联/哈希表	单向	插入删除失效	平均情况：O（1）最差情况：O（N）	平均情况：O（1）最差情况：O（N）	平均情况：O（1）最差情况：O（N）	内存使用比有序的高一些，但是查找速度更快。只有哈希函数太差或者发生哈希重建才会退化为O（N）。但是一般很少发生，均摊还是O（1）。
unordered_multimap	多重映射无序关联/哈希表	单向	同上	同上	同上	同上	同上
unordered_set	集合无序关联	单向	同上	同上	同上	同上	同上
unordered_multiset	多重集合无序关联	单向	同上	同上	同上	同上	同上

3.4容器适配器

名称	说明	迭代器失效	插入	删除	查找	场景
stack	映射无序关联	不支持迭代器	只能尾端入：O（1）	只能尾端删除：O（1）	不支持	FILO（先进后出）底层容器可以是list或vector或deque。
queue	队列	不支持迭代器	只能尾端入：O（1）	只能首端删除：O（1）	不支持	FIFO（先进先出）。底层容器可以是list或deque。
priority_queue	优先、队列	不支持迭代器	同上	同上	不支持	FIFO（先进先出）。底层容器可以是vector或deque。

3.5 小节 

1、关联容器对元素的插入和删除操作比vector 要快，因为vector 是顺序存储，而关联容器是链式存储；

        比list 要慢，是因为即使它们同是链式结构，但list 是线性的，而关联容器是二叉树结构，其改变一个元素涉及到其它元素的变动比list 要多，并且它是排序的，每次插入和删除都需要对元素重新排序；

2、 关联容器对元素的检索操作比vector 慢，但是比list 要快很多。

        vector 是顺序的连续存储，当然是比不上的，但相对链式的list 要快很多是因为list 是逐个搜索，它搜索的时间是跟容器的大小成正比，而关联容器 查找的复杂度基本是Log(N) ，比如如果有1000 个记录，最多查找10 次，1,000,000 个记录，最多查找20 次。容器越大，关联容器相对list 的优越性就越能体现；

3、 在使用上set 区别于vector,deque,list 的最大特点就是set 是内部排序的，这在查询上虽然逊色于vector ，但是却大大的强于list 。

4、在使用上map 的功能是不可取代的，它保存了“键- 值”关系的数据，而这种键值关系采用了类数组的方式。数组是用数字类型的下标来索引元素的位置，而map 是用字符型关键字来索引元素的位置。在使用上map 也提供了一种类数组操作的方式，即它可以通过下标来检索数据，这是其他容器做不到的，当然也包括set 。

注意：STL 中只有vector 和map 可以通过类数组的方式操作元素，即如同num[1]下表索引的方式。

5、适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作“它保存一个容器，这个容器再保存所有元素”。

        STL 中提供的三种适配器可以由某一种顺序容器去实现。默认下stack 和queue 基于deque 容器实现，priority_queue 则基于vector 容器实现。

        当然在创建一个适配器时也可以指定具体的实现容器，创建适配器时在第二个参数上指定具体的顺序容器可以覆盖适配器的默认实现。

四、常用函数

4.1顺序容器

Headers		">	">	">	">	">
Members		array	vector	deque	forward_list	list
	constructor（构造函数）	implicit	vector	deque	forward_list	list
	destructor（析构函数）	implicit	~vector	~deque	~forward_list	~list
	operator=（重载函数）	implicit	operator=	operator=	operator=	operator=
iterators	begin （返回头指针）	begin	begin	begin	begin before_begin	begin
	end （返回尾部下一个元素的指针）	end	end	end	end	end
	rbegin（返回尾指针）	rbegin	rbegin	rbegin		rbegin
	rend （返回首部上一个元素的指针）	rend	rend	rend		rend
const iterators	cbegin（常量指针）	cbegin	cbegin	cbegin	cbegin cbefore_begin	cbegin
	cend（常量指针）	cend	cend	cend	cend	cend
	crbegin（常量指针）	crbegin	crbegin	crbegin		crbegin
	crend（常量指针）	crend	crend	crend		crend
capacity	size（元素个数）	size	size	size		size
	max_size(可容纳最大元素个数)	max_size	max_size	max_size	max_size	max_size
	empty（是否为空）	empty	empty	empty	empty	empty
	resize（改变大小）		resize	resize	resize	resize
	shrink_to_fit（适应合适容量）		shrink_to_fit	shrink_to_fit
	capacity（存储容量>=size）		capacity
	reserve（改变容量和大小）		reserve
element access	front（首元素）	front	front	front	front	front
	back（尾元素）	back	back	back		back
	operator[]（索引函数）	operator[]	operator[]	operator[]
	at（返回下标）	at	at	at
modifiers	assign（拷贝、赋值）		assign	assign	assign	assign
	emplace（插入函数）		emplace	emplace	emplace_after	emplace
	insert（插入函数）		insert	insert	insert_after	insert
	erase（删除函数）		erase	erase	erase_after	erase
	emplace_back（从尾压入）		emplace_back	emplace_back		emplace_back
	push_back（从尾压入）		push_back	push_back		push_back
	pop_back（从尾弹出）		pop_back	pop_back		pop_back
	emplace_front（从头压入）			emplace_front	emplace_front	emplace_front
	push_front（从头压入）			push_front	push_front	push_front
	pop_front（从头弹出）			pop_front	pop_front	pop_front
	clear（删除所有）		clear	clear	clear	clear
	swap（交换）	swap	swap	swap	swap	swap
list operations	splice（插入）				splice_after	splice
	remove（删除）				remove	remove
	remove_if（条件删除）				remove_if	remove_if
	unique（删除重复元素）				unique	unique
	merge（合并）				merge	merge
	sort（排序）				sort	sort
	reverse（逆序）				reverse	reverse
observers	get_allocator(获取空间配置器)		get_allocator	get_allocator	get_allocator	get_allocator
	data（返回头指针）	data	data

4.2关联容器

Headers		">		">		">		">
Members		set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap
	constructor（构造函数）	set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap
	destructor（析构函数）	~set	~multiset	~map	~multimap	~unordered_set	~unordered_multiset	~unordered_map	~unordered_multimap
	assignment（拷贝）	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=
iterators	begin（返回头指针）	begin	begin	begin	begin	begin	begin	begin	begin
	end（返回尾部下一个元素的指针）	end	end	end	end	end	end	end	end
	rbegin（返回尾指针）	rbegin	rbegin	rbegin	rbegin
	rend（返回首部上一个元素的指针）	rend	rend	rend	rend
const iterators	cbegin（常量指针）	cbegin	cbegin	cbegin	cbegin	cbegin	cbegin	cbegin	cbegin
	cend（常量指针）	cend	cend	cend	cend	cend	cend	cend	cend
	crbegin（常量指针）	crbegin	crbegin	crbegin	crbegin
	crend（常量指针）	crend	crend	crend	crend
capacity	size（元素个数）	size	size	size	size	size	size	size	size
	max_size(可容纳最大元素个数)	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size
	empty（是否为空）	empty	empty	empty	empty	empty	empty	empty	empty
	reserve（改变大小）					reserve	reserve	reserve	reserve
element access	at（返回key）			at				at
	operator[]（索引函数）			operator[]				operator[]
modifiers	emplace（插入）	emplace	emplace	emplace	emplace	emplace	emplace	emplace	emplace
	emplace_hint(插入)	emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint
	insert（插入）	insert	insert	insert	insert	insert	insert	insert	insert
	erase（删除）	erase	erase	erase	erase	erase	erase	erase	erase
	clear（删除所有）	clear	clear	clear	clear	clear	clear	clear	clear
	swap（交换）	swap	swap	swap	swap	swap	swap	swap	swap
operations	count（返回某元素个数）	count	count	count	count	count	count	count	count
	find（查找）	find	find	find	find	find	find	find	find
	equal_range（重复元素）	equal_range	equal_range	equal_range	equal_range	equal_range	equal_range	equal_range	equal_range
	lower_bound（返回当前值迭代器）	lower_bound	lower_bound	lower_bound	lower_bound
	upper_bound（返回下一值迭代器）	upper_bound	upper_bound	upper_bound	upper_bound
observers	get_allocator(获取空间配置器)	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator
	key_comp（返回比较键容器）	key_comp	key_comp	key_comp	key_comp
	value_comp（返回比较值容器）	value_comp	value_comp	value_comp	value_comp
	key_eq(返回键相等比较对象)					key_eq	key_eq	key_eq	key_eq
	hash_function（返回哈希对象）					hash_function	hash_function	hash_function	hash_function
buckets	bucket（找到元素的桶）					bucket	bucket	bucket	bucket
	bucket_count（桶计数）					bucket_count	bucket_count	bucket_count	bucket_count
	bucket_size（桶大小）					bucket_size	bucket_size	bucket_size	bucket_size
	max_bucket_count（最大桶数量）					max_bucket_count	max_bucket_count	max_bucket_count	max_bucket_count
hash policy	rehash（设置桶的数量）					rehash	rehash	rehash	rehash
	load_factor（返回load_factor = size / bucket_count）					load_factor	load_factor	load_factor	load_factor
	max_load_factor（管理每个桶的平均元素数量的最大值）					max_load_factor	max_load_factor	max_load_factor	max_load_factor