C语法基础大全-容器

一、序列式容器

1.1 Vector

1.1.1 引入

#include < vector> 
using namespace std;

1.1.2 常用方法

（1）构造函数

• vector():创建一个空vector
• vector(int nSize):创建一个vector,元素个数为nSize
• vector(int nSize,const t& t):创建一个vector，元素个数为nSize,且值均为t
• vector(const vector&):复制构造函数
• vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中

（2）增加函数

• void push_back(const T& x):向量尾部增加一个元素X
• iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x
• iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x
• iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据

（3）删除函数

• iterator erase(iterator it):删除向量中迭代器指向元素
• iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
• void pop_back():删除向量中最后一个元素
• void clear():清空向量中所有元素

（4）遍历函数

• reference at(int pos):返回pos位置元素的引用
• reference front():返回首元素的引用
• reference back():返回尾元素的引用
• iterator begin():返回向量头指针，指向第一个元素
• iterator end():返回向量尾指针，指向向量最后一个元素的下一个位置
• reverse_iterator rbegin():反向迭代器，指向最后一个元素
• reverse_iterator rend():反向迭代器，指向第一个元素之前的位置

（5）判断函数

• bool empty() const:判断向量是否为空，若为空，则向量中无元素

（6）大小函数

• int size() const:返回向量中元素的个数
• int capacity() const:返回当前向量张红所能容纳的最大元素值
• int max_size() const:返回最大可允许的vector元素数量值

（7）其他函数

• void swap(vector&):交换两个同类型向量的数据
• void assign(int n,const T& x):设置向量中第n个元素的值为x
• void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素

1.2 deque

1.2.1 引入与使用

#include<deque>  // 头文件
deque<type> deq;  // 声明一个元素类型为type的双端队列que
deque<type> deq(size);  // 声明一个类型为type、含有size个默认值初始化元素的的双端队列que
deque<type> deq(size, value);  // 声明一个元素类型为type、含有size个value元素的双端队列que
deque<type> deq(mydeque);  // deq是mydeque的一个副本
deque<type> deq(first, last);  // 使用迭代器first、last范围内的元素初始化deq

1.2.2 常用方法

• deq[]：用来访问双向队列中单个的元素。
• deq.front()：返回第一个元素的引用。
• deq.back()：返回最后一个元素的引用。
• deq.push_front(x)：把元素x插入到双向队列的头部。
• deq.pop_front()：弹出双向队列的第一个元素。
• deq.push_back(x)：把元素x插入到双向队列的尾部。
• deq.pop_back()：弹出双向队列的最后一个元素。

1.2.3 与Vector的区别

• Vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空间。
• deque对象在队列的两端放置元素和删除元素是高效的，而向量vector只是在插入序列的末尾时操作才是高效的。
• deque和vector的最大差异，一在于deque允许于常数时间内对头端进行元素的插入或移除操作，二在于deque没有所谓的capacity观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像vector那样“因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque中是不会发生的。也因此，deque没有必要提供所谓的空间预留（reserved）功能

1.3 queue

• 队列容器，只能在容器的末尾添加新元素，只能从头部移除元素

• front()：返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
• back()：返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
• push(const T& obj)：在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
• push(T&& obj)：以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
• pop()：删除 queue 中的第一个元素。
• size()：返回 queue 中元素的个数。
• empty()：如果 queue 中没有元素的话，返回 true。
• emplace()：用传给 emplace() 的参数调用 T 的构造函数，在 queue 的尾部生成对象。
• swap(queue\ &other_q)：将当前 queue 中的元素和参数 queue 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。

1.4 stack

• top()：返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。
• push(const T& obj)：可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
• push(T&& obj)：以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
• pop()：弹出栈顶元素。
• size()：返回栈中元素的个数。
• empty()：在栈中没有元素的情况下返回 true。
• emplace()：用传入的参数调用构造函数，在栈顶生成对象。
• swap(stack\ & other_stack)：将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。对于 stack 对象有一个特例化的全局函数 swap() 可以使用。

1.5 priority_queue

• 维护一个堆的数据结构，可以是最大堆，也可以是最小堆

• top() 访问队头元素

• empty() 队列是否为空

• size() 返回队列内元素个数
• push() 插入元素到队尾 (并排序)
• emplace() 原地构造一个元素并插入队列
• pop() 弹出队头元素
• swap() 交换内容

//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大顶堆
priority_queue <int,vector<int>,less<int> >q;

1.6 List

#include <list>

• assign() 给list赋值
• back() 返回最后一个元素
• begin() 返回指向第一个元素的迭代器
• clear() 删除所有元素
• empty() 如果list是空的则返回true
• end() 返回末尾的迭代器
• erase() 删除一个元素
• front() 返回第一个元素
• get_allocator() 返回list的配置器
• insert() 插入一个元素到list中
• max_size() 返回list能容纳的最大元素数量
• merge() 合并两个list
• pop_back() 删除最后一个元素
• pop_front() 删除第一个元素
• push_back() 在list的末尾添加一个元素
• push_front() 在list的头部添加一个元素
• rbegin() 返回指向第一个元素的逆向迭代器
• remove() 从list删除元素
• remove_if() 按指定条件删除元素
• rend() 指向list末尾的逆向迭代器
• resize() 改变list的大小
• reverse() 把list的元素倒转
• size() 返回list中的元素个数
• sort() 给list排序
• splice() 合并两个list
• swap() 交换两个list
• unique() 删除list中相邻重复的元素

二、关联式容器

2.1 map

// map和multimap都需要#include<map>
#include<map>

• begin()：返回指向map头部的迭代器
• clear()：删除所有元素
• count()：返回指定元素出现的次数
• empty()：如果map为空则返回true
• end()：返回指向map末尾的迭代器
• equal_range()：返回特殊条目的迭代器对
• erase()：删除一个元素
• find()：查找一个元素
• get_allocator()：返回map的配置器
• insert()：插入元素
• key_comp()：返回比较元素key的函数
• lower_bound()：返回键值>=给定元素的第一个位置
• max_size()：返回可以容纳的最大元素个数
• rbegin()：返回一个指向map尾部的逆向迭代器
• rend()：返回一个指向map头部的逆向迭代器
• size()：返回map中元素的个数
• swap()：交换两个map
• upper_bound()：返回键值>给定元素的第一个位置
• value_comp()：返回比较元素value的函数

2.2 unordered_map

#include<unordered_map>
unordered_map<string,int> mp;
//迭代器遍历
unordered_map<string,int>::iterator iter;
for(iter=mp.begin();iter!=mp.end();iter++){
    cout<<iter->first<<": "<<iter->second<<endl;
}

//:遍历
for(auto &[name,value]:mp){
    cout<<name<<": "<<value<<endl;
}

2.3 set

// constructing sets
#include <iostream>
#include <set>

bool fncomp (int lhs, int rhs) {return lhs<rhs;}

struct classcomp {
  bool operator() (const int& lhs, const int& rhs) const
  {return lhs<rhs;}
};

int main ()
{
  std::set<int> first;                           // empty set of ints

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

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

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

  std::set<int,classcomp> fifth;                 // class as Compare

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

  return 0;
}

1. begin()：返回指向第一个元素的迭代器
2. clear()：清除所有元素
3. count()：返回某个值元素的个数
4. empty()：如果集合为空，返回true
5. end()：返回指向最后一个元素的迭代器
6. equal_range()：返回集合中与给定值相等的上下限的两个迭代器
7. erase()：删除集合中的元素
8. find()：返回一个指向被查找到元素的迭代器
9. get_allocator()：返回集合的分配器
10. insert()：在集合中插入元素
11. lower_bound()：返回指向大于（或等于）某值的第一个元素的迭代器
12. key_comp()：返回一个用于元素间值比较的函数
13. max_size()：返回集合能容纳的元素的最大限值
14. rbegin()：返回指向集合中最后一个元素的反向迭代器
15. rend()：返回指向集合中第一个元素的反向迭代器
16. size()：集合中元素的数目
17. swap()：交换两个集合变量
18. upper_bound()：返回大于某个值元素的迭代器
19. value_comp()：返回一个用于比较元素间的值的函数

2.4 unordered_set

// constructing unordered_sets
#include <iostream>
#include <string>
#include <unordered_set>

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

int main ()
{
  std::unordered_set<std::string> first;                                // empty
  std::unordered_set<std::string> second ( {"red","green","blue"} );    // init list
  std::unordered_set<std::string> third ( {"orange","pink","yellow"} ); // init list
  std::unordered_set<std::string> fourth ( second );                    // copy
  std::unordered_set<std::string> fifth ( cmerge(third,fourth) );       // move
  std::unordered_set<std::string> 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;
}

• 主要方法与set类似
• emplace(key)：插入元素

2.5 pair

2.5.1 概述

• pair是c++的一种数据类型，在头文件utility中

2.5.2 使用

pair<string, string> a("James", "Joy");
string name,last;
name = pair.first;
lase = pair.second;

// 给属性赋值
newone = make_pair(name, last);

2.5.3 priority_queue中的pair

#include<bits/stdc++.h>
using namespace std;
 
int main() {
	priority_queue<pair<int, int> > a;
	pair<int,int> b(1,5);
	pair<int,int> d(1,2);
	pair<int,int> c(6,1);
 
	a.push(d);
	a.push(c);
	a.push(b);
 
	while (!a.empty()) {
		cout<<a.top().first<<" "<<a.top().second<<endl;
		a.pop();
	}
 
	return 0;
}

/*
比较第一个，若相同，则比较第2个
6 1
1 5
1 2
*/

2.5.4 sort()

// lambda表达式自定义排序，以下为降序排列
sort(vec.begin(),vec.end(),[](const int a,const int b){return a>b;});

// 将自定义排序方式放在sort()外
bool cmp(int a,int b){
    return a>b;//从大到小排序
}

sort(vec.begin(),vec.end(),cmp);