[人工智能]STL容器分类和序列式容器详解

STL 容器种类和功能

1. 序列容器
   主要包括 vector 向量容器、list 列表容器以及 deque 双端队列容器。之所以被称为序列容器，是因为元素在容器中的位置同元素的值无关，即容器不是排序的。将元素插入容器时，指定在什么位置，元素就会位于什么位置。
2. 排序容器
   包括 set 集合容器、multiset多重集合容器、map映射容器以及 multimap 多重映射容器。排序容器中的元素默认是由小到大排序好的，即便是插入元素，元素也会插入到适当位置。所以关联容器在查找时具有非常好的性能。
3. 哈希容器
   C++ 11 新加入 4 种关联式容器，分别是 unordered_set 哈希集合、unordered_multiset 哈希多重集合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射。和排序容器不同，哈希容器中的元素是未排序的，元素的位置由哈希函数确定。

迭代器

迭代器的分类

1. 前向迭代器
   假设 p 是一个前向迭代器，则 p 支持 ++p，p++，*p 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较。此外，两个正向迭代器可以互相赋值。
2. 双向迭代器
   双向迭代器具有正向迭代器的全部功能，除此之外，假设 p 是一个双向迭代器，则还可以进行 --p 或者 p-- 操作（即一次向后移动一个位置）。
3. 随机访问迭代器
   随机访问迭代器具有双向迭代器的全部功能。除此之外，假设 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：
   p+=i：使得 p 往后移动 i 个元素。
   p-=i：使得 p 往前移动 i 个元素。
   p+i：返回 p 后面第 i 个元素的迭代器。
   p-i：返回 p 前面第 i 个元素的迭代器。
   p[i]：返回 p 后面第 i 个元素的引用。
   此外，两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。
   

迭代器的定义

1. 正向迭代器

   容器类名::iterator 迭代器名;

2. 常量正向迭代器

   容器类名::const_iterator 迭代器名;

3. 反向迭代器

   容器类名::reverse_iterator 迭代器名;

4. 常量反向迭代器

   容器类名::const_reverse_iterator 迭代器名;
   示例：

#include<bits/stdc++.h> 
using namespace std;
int main()
{
	//v被初始化成有10个元素
    vector<int> v{1,2,3,4,5,6,7,8,9,10}; 
    cout << "第一种遍历方法：随机访问迭代器支持" << endl;
    //像普通数组一样使用vector容器
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] <<" "; 
    
    cout << endl << "第二种遍历方法：三种迭代器均支持" << endl;
    vector<int>::iterator i;
    //用 != 比较两个迭代器
    for (i = v.begin(); i != v.end(); ++i)
        cout << *i << " ";
    
    cout << endl << "第三种遍历方法：随机访问迭代器支持" << endl;
    //用 < 比较两个迭代器
    for (i = v.begin(); i < v.end(); ++i) 
        cout << *i << " ";
   
    cout << endl << "第四种遍历方法：随机访问迭代器支持" << endl;
    i = v.begin();
    //间隔一个输出   // 随机访问迭代器支持 "+= 整数"  的操作
    while (i < v.end()) { 
        cout << *i << " ";
        i += 2; 
    }
}

输出：

序列式容器

• array<T,N>（数组容器）：n个固定元素，随机访问
  表示可以存储 N 个 T 类型的元素，是 C++
  本身提供的一种容器。此类容器一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值；
• vector（向量容器）：尾部删除插入，随机访问
  用来存放 T类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或删除元素的效率最高（时间复杂度为O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中 n 为容器中元素的个数）；
• deque（双端队列容器）：头部尾部删除插入，随机访问
  和 vector非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1)常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶；
• list（链表容器）：任意位置删除插入，两个方向顺序访问
  是一个长度可变的、由 T类型元素组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。
• forward_list（正向链表容器）：任何位置删除插入，正向顺序访问
  和 list容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。

vector容器包含的成员函数

• begin() 返回指向容器中第一个元素的迭代器。
• end() 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。
• rbegin() 返回指向最后一个元素的迭代器。
• rend() 返回指向第一个元素所在位置前一个位置的迭代器。
• cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
• cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
• crbegin() 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
• crend() 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
• size() 返回实际元素个数。
• max_size() 返回元素个数的最大值。这通 常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。
• resize() 改变实际元素的个数。
• capacity() 返回当前容量。
• empty() 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
• reserve() 增加容器的容量。
• shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。
• operator[ ] 重载了 [ ] 运算符，可以向访问数组中元素那样，通过下标即可访问甚至修改 vector 容器中的元素。
• at() 使用经过边界检查的索引访问元素。
• front() 返回第一个元素的引用。
• back() 返回最后一个元素的引用。
• data() 返回指向容器中第一个元素的指针。
• assign() 用新元素替换原有内容。
• push_back() 在序列的尾部添加一个元素。
• pop_back() 移出序列尾部的元素。
• insert() 在指定的位置插入一个或多个元素。
  insert示例代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    std::vector<int> demo{1,2};
    //第一种格式用法
    demo.insert(demo.begin() + 1, 3);//{1,3,2}

    //第二种格式用法
    demo.insert(demo.end(), 2, 5);//{1,3,2,5,5}

    //第三种格式用法
    std::array<int,3>test{ 7,8,9 };
    demo.insert(demo.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}

    //第四种格式用法
    demo.insert(demo.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}

    return 0;
}

• erase() 移出一个元素或一段元素。
• remove() 删除容器中所有和指定元素值相等的元素，并返回指向最后一个元素下一个位置的迭代器。值得一提的是，调用该函数不会改变容器的大小和容量。
• clear() 移出所有的元素，容器大小变为 0。
• swap() 交换两个容器的所有元素。
• emplace() 在指定的位置直接生成一个元素。
• emplace_back() 在序列尾部生成一个元素。

示例：

#include<bits/stdc++.h>
using namespace std;
int main(){
	//	创建int类型vector容器 
	vector<int>v;
	//	获得vector容器容量 
	cout<<v.size()<<endl;
	//	向vector容器尾部插入元素 
	v.push_back(1); 
	v.push_back(2); 
	cout<<v.size()<<endl;
	//增加容器的容量,如果 vector 的容量在执行此语句之前，已经大于或等于 1 个元素
	v.reserve(1);
	cout<<v.size()<<endl;
	v.reserve(10);
	cout<<v.size()<<endl;
	//创建指定容量和元素的vector
	vector<int>va(10,-1);//第一个容量，第二个为值，默认为0 
	//返回元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。
	cout<<va.max_size()<<endl; 
	//改变实际元素的个数。
	v.resize(0);
	cout<<v.size()<<endl;
	//返回当前容量。
	cout<<va.capacity()<<endl;
	//判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
	cout<<va.empty()<<endl;
	//将内存减少到等于当前元素实际所使用的大小。
	va.shrink_to_fit();
	cout<<va.size()<<endl;
	//返回第一个元素的引用。
	cout<<va.front()<<endl;
	//返回最后一个元素的引用。
	cout<<va.back()<<endl;
	//返回指向容器中第一个元素的指针。
	cout<<va.data()<<endl;
	//移出序列尾部的元素。
	va.pop_back();
	//在指定的位置插入一个或多个元素。
	va.insert(va.begin()+5,1);
	cout<<va[5]<<endl;
	//用新元素替换原有内容。
	va.assign({1,1,1,1,1,1});
	cout<<va[1]<<endl;
	//移出一个元素或一段元素。
	va.erase(va.begin()+1,va.begin()+3);
	cout<<va.size()<<endl;
	//va.clear()   移出所有的元素，容器大小变为 0。
	//交换两个容器的所有元素。
	swap(v,va);
	cout<<va.size()<<endl;
	return 0;
} 

deque包含的成员函数
deque包含的成员函数和vector基本一致，常用的增加了：

• push_front() 在序列的头部添加一个元素。
• pop_front() 移除容器头部的元素。

list容器可用的成员函数

• empty() 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
• size() 返回当前容器实际包含的元素个数。
• max_size() 返回容器所能包含元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。
• front() 返回第一个元素的引用。
• back() 返回最后一个元素的引用。
• assign() 用新元素替换容器中原有内容。
• emplace_front() 在容器头部生成一个元素。该函数和 push_front() 的功能相同，但效率更高。
• push_front() 在容器头部插入一个元素。
• pop_front() 删除容器头部的一个元素。
• emplace_back() 在容器尾部直接生成一个元素。该函数和 push_back() 的功能相同，但效率更高。
• push_back() 在容器尾部插入一个元素。
• pop_back() 删除容器尾部的一个元素。
• emplace() 在容器中的指定位置插入元素。该函数和 insert() 功能相同，但效率更高。
• insert() 在容器中的指定位置插入元素。
• erase() 删除容器中一个或某区域内的元素。
• swap() 交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的。
• resize() 调整容器的大小。
• clear() 删除容器存储的所有元素。
• splice() 将一个 list 容器中的元素插入到另一个容器的指定位置。

#include<bits/stdc++.h>
using namespace std;
int main(){
	list<double>li1{3.1,2.2,2.9},li2{9.9,10.9};
	//排序 
	li1.sort();
	for (auto it:li1) {
        std::cout << it << " ";
    }
    cout<<endl;
    //指向 li1 容器中的元素 2
    list<double>::iterator it = ++li1.begin();
    //调用第一种语法格式
    li1.splice(it, li2); // li1: 3.1,9.9,10.9,2.2,2.9
                    
    for (auto it:li1) {
        std::cout << it << " ";
    }
    cout<<endl;
    //调用第二种语法格式，将 [li1.begin(),li1.end())范围内的元素移动到 li1.begin() 位置处  
	li2.splice(li2.begin(), li1, li1.begin(), li1.end());
	for (auto it:li2) {
        std::cout << it << " ";
    }
	return 0;
} 

• remove(val) 删除容器中所有等于 val 的元素。

#include<bits/stdc++.h>
using namespace std;
int main(){
	list<int>li{1,3,5,2,4,3,5,3,3};
	li.remove(3);
	for (auto it:li) {
        std::cout << it << " ";
    }
	return 0;
} 

• remove_if() 删除容器中满足条件的元素。

#include<bits/stdc++.h>
using namespace std;
int main(){
	list<int>li{1,3,5,2,4,3,5,3,3};
	li.remove_if([](int value) {return (value <= 3); }); 
	for (auto it:li) {
        std::cout << it << " ";
    }
	return 0;
} 

• unique() 删除容器中相邻的重复元素，只保留一个。

#include <iostream>
#include <list>
using namespace std;
//二元谓词函数
bool demo(double first, double second)
{
    return (int(first) == int(second));
}

int main()
{
    list<double> mylist{ 1,1.2,1.2,3,4,4.5,4.6 };
    //删除相邻重复的元素，仅保留一份
    mylist.unique();//{1, 1.2, 3, 4, 4.5, 4.6}

    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        cout << *it << ' ';
    cout << endl;
    //demo 为二元谓词函数，是我们自定义的去重规则
    mylist.unique(demo);

    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        std::cout << *it << ' ';
    return 0;
}

• merge() 合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的。

#include<bits/stdc++.h>
using namespace std;
int main(){
	list<int>li{1,3,5,2,4,3,5,3,3},l2{9,8,1,5};
	li.merge(l2); 
	for (auto it:li) {
        std::cout << it << " ";
    }
	return 0;
} 

• sort() 通过更改容器中元素的位置，将它们进行排序。
• reverse() 反转容器中元素的顺序。