序列式容器

vector list deque

0. 迭代器

前向迭代器

支持++p,*p等操作

双向迭代器

支持--p等操作哦

随机访问迭代器

p+=i 迭代器往后移动i个元素

p+i 返回迭代器后第i个元素的迭代器

p[i] 返回p后面第i个元素的引用

通过迭代器遍历

for(i=v.begin();i<v.end();++i){
    cout<<*i<<endl;
}

array<T,N>(数组容器)，存储N个T类型的元素，长度初始化后不可变

vector,向量容器存放T类型的元素，长度可变，末尾添加删除元素效率高，随机访问效率低

deque,双端队列容器，可以在头部、尾部插入删除元素

list,链表容器，双向链表，长度可变，可以在任何地方添加删除元素，访问元素较慢

forward_list,正向链表容器，单向链表，只能从第一个元素开始访问，比list快，节省内存

array,vector,deque常见函数

1.STL array

声明后长度不可变

array<typename T,size_t N>
array<double,10> arr{};//不指定值，默认为0
array<double, 10> values {0.5,1.0,1.5,,2.0};//剩余元素为0

array通过[]访问元素，为了避免越界，可以使用at()成员函数，越界会抛出out_of_range异常

2.STL vector

vector<double> val;
//扩容，当val.size()>20则不做操作
val.reserve(20)；
std::vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};
std::vector<double> values(20);//指定元素个数，初始为0
std::vector<double> values(20,1);//指定元素个数，初始为1

访问元素的方式

vec[n];
vec.at(n);
vec.front();//首元素
vec.back();//尾元素
vec.data();//返回首元素的指针
*(vec.data()+n);

push_back();
emplace_back();

这两个函数都可以在容器末尾添加元素

push_back添加元素时，会生成一个元素，再将元素移动（或拷贝）至容器中，而emplace_back会

直接在容器末尾生成，因此emplace_back更加高效

iterator insert(pos,elem);//在指定位置之前插入一个元素elem
iterator insert(pos,n,elem);//在指定位置之前插入n个元素elem
iterator insert(pos,first,last);//在pos之前，插入其他容器中[first,last)区域内的所有元素，返回第一个新元素的迭代器的位置
iterator insert(pos,initlist);//在pos之前插入初始化列表的所有元素，返回第一个新元素的迭代器的位置

iterator emplace(const_iterator pos,args);

pos:指定插入元素的位置，args：新插入元素的构造函数对应的多个参数

删除元素

erase(n);//删除指定位置的元素
erase(first,last);//删除指定位置[first,last)的元素
remove(pos,n);//从pos开始删除值为n的元素

remove不会改变容器大小和容量

​ remove() 的实现原理是，在遍历容器中的元素时，一旦遇到目标元素，就做上标记，然后继续遍历，直到找到一个非目标元素，即用此元素将最先做标记的位置覆盖掉，同时将此非目标元素所在的位置也做上标记，等待找到新的非目标元素将其覆盖。因此，1,3,3,4,3,5，remove(3)如果将上面程序中 demo 容器的元素全部输出，得到的结果为 1 4 5 4 3 5。

因此删除指定元素需要和erase搭配

auto it=remove(demo.begin(),demo.end(),3);
demo.erase(it,demo.end());

vector<int> demo{1,2,3};
demo.clear();
//demo.size()=0
//demo.capacity()=6

vector<bool>并不是一个STL容器，也不容纳bool

vector<bool> 打包 bool 以节省空间，每个保存在“vector”中的“bool”占用一个单独的bit，而禁止有指向单个比特的指针。

3.STL deque

deque相比vector，可以高效的在容器底部或尾部插入元素，且容器内的元素不一定会放在一段连续内存里

deque<int> dq;//初始化空队列
deque<int> dq(100);//初始化100个默认值的队列
deque<int> dq(100,1);//初始化100个1的队列

注：创建first容器后，容器进行添加操作，会导致first失效

访问deque元素

dq[n];//访问容器的中第n个元素
dq.at(n);//访问容器的中第n个元素,有边界控制
dq.front();//访问dq的首元素
dq.back();//访问dq的尾元素

4.STL list

list双向链表容器，各元素靠指针维持顺序，分别指向前后两个元素，不能通过索引访问元素

list<int> l;
list<int> l(10);
list<int> l(10,5);

访问元素：

l.front();//返回list的第一个元素的引用
l.back();//返回list的最后一个元素的引用

list插入元素：

push_front();
push_back();
emplace_back();
emplace_front();
emplace();//在指定位置生成元素
insert();//在指定位置插入元素
splice();//在指定位置插入其他list容器中的元素

splice 将其他list容器中的元素添加当前list容器中指定位置处。

void splice(iterator pos,list& x);//pos：插入位置，x：另一个list容器
void splice(iterator pos,list& x,iterator i);//将x容器中i指向的元素移动到当前容器中pos指明的位置
void splice(iterator pos,list& x,iterator first,iterator last);//将x容器[first,last)范围内所有元素移动到当前容器pos位置上。

splice方法会将x容器中的相应元素添加到当前容器，该元素会从x中删除

unique()

void unique();
void unique(BinaryPredicate);//传入二元谓词函数

两种方式都可去重，第二种可以自定义去重规则

remove_if();//传入自定义为此函数，删除满足条件的元素

5.STL forward_list

C++11新容器，底层为单链表结构，数据存储是分散随机的。可以在序列任何位置添加和删除元素。

forward_list只提供前向迭代器，无rbegin，rend等函数

相较于list，消耗内存小，空间效率高

forward_list<int> fl;
forward_list<int> fl(10);
forward_list<int> fl(10,5);//初始化10个5

forward_list不提供size函数，如果想获取长度，采用iterator中的distance函数。

int count=distance(begin(fl),end(fl));
int count=distance(fl.begin(),fl.end());

begin()，end()为STL容器方法，可以获取容器第一个，最后一个元素的迭代器

begin(),end(),参数可以是普通数组，可可以是容器，为普通数组将返回第一个、最后一个元素的指针，为容器返回迭代器。

6.vector自定义排序

• 重载运算符

  struct Book{
  	int page;
  	string name;
  	bool operator <(const Book& b) const // 升序排序时必须写的函数
      {
          return page < b.page;
      }
      bool operator >(const Book& b) const // 降序排序时必须写的函数
      {
          return page > b.page;
      }
  }
  vector<Book> books;
  sort(books.begin(), books.end(), less<Book>());
  

• 全局比较函数

  struct Book{
  	int page;
  	string name;
  };
  
  bool lessmark(const Book& b1, const Book& b2)
  {
       return b1.page < b2.page;
  }
  bool greatermark(const Book& b1, const Book& b2)
  {
       return b1.page > b2.page;
  }
  vector<Book> books;
  sort(books.begin(), books.end(), lessmark); //升序排序
  

• 仿生函数(重写（）)

  struct Book{
  	int page;
  	string name;
  };
  class CompLess{
  public:
      bool operator ()(const Book& b1, const Book& b2)
      {
          return b1.page < b2.page;
      }
  };
  class CompGreater{
  public:
      bool operator ()(const Book& b1, const Book& b2)
      {
          return b1.page > b2.page;
      }
  };
  vector<Book> books;
  sort(books.begin(), books.end(), CompLess()); //升序排序