当前位置：首页 > news >正文

C++中STL之容器和迭代器

news 来源：原创 2024/9/20 6:06:37

容器

什么是容器？

各种数据结构，如Vector,List,Deque,Set,Map,用来存放数据，STL容器是一种Class Template,就体积而言，这一部分很像冰山载海面的比率。

STL容器是什么？

简单的理解容器，它就是一些模板类的集合，但和普通模板类不同的是，容器中封装的是组织数据的方法(也就是数据结构)。STL提供有3类标准容器，分别是序列容器、排序容器和哈希容器，其中后两类容器有时也统称为关联容器。

容器种类

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

array容器

示例：

#include<iostream>
#include<array>
using namespace std;int main()
{array<int, 6> arr = { 1,2,3,4,5,6 };//
//在定义模板类的时候直接对其初始化//for (int i = 0; i < 6; i++)//{//	cout << arr[i] << endl;//}//array<int, 6>::iterator ite=arr.begin();//正向迭代array<int, 6>::iterator ite = arr.rbegin();while (ite !=arr.rend() ){cout << *ite << endl;ite++;}return 0;
}

vector容器

向量容器实现动态数组可进行插入和删除

示例：

#include<iostream>
#include<vector>
using namespace std;int main()
{vector<int> vec;cout << "size:" << vec.size() << "capacity:" << vec.capacity() << endl;vec.reserve(15);//增加容器的容量 可以预先预估一下所需要的容器容量for (int i = 0; i < 20; i++){vec.push_back(i);//添加元素 不够会自动扩容容器大小cout << "size:" << vec.size() << "capacity:" << vec.capacity() << endl;}for (int j = 0; j < vec.size(); j++){cout << vec[j] << endl;}return 0;
}

List容器

示例：

#include<iostream>
#include<list>
using namespace std;
int main()
{list<int> lst;lst.push_back(1);lst.push_back(3);lst.push_back(5);lst.push_front(7);lst.push_front(9);lst.push_front(11);list<int>::iterator ite = lst.begin();while (ite != lst.end()){if (*ite == 9){//	ite=lst.insert(ite,666);//插入在某个迭代器的前面 返回的就是所插入元素的迭代器（地址）//	cout << *ite << endl;//	ite++;ite=lst.erase(ite);//返回的是所删除迭代器（所指向的那个元素）的下一个}cout << *ite << endl;ite++;}return 0;
}

迭代器

什么是迭代器？

扮演容器与算法之间的胶合剂，是所谓的“泛型指针”，共有五种类型，以及其它衍生变化，从实现的角度来看，迭代器是一种将:Operators*,Operator->,Operator++,Operator--等相关操作予以重载的ClassTemplate（模板类）。所有STL容器都附带有自己专属的迭代器-一是的，只有容器设计者才知道如何遍历自己的元素，原生指针(Native pointer)也是一种迭代器。

STL迭代器（iterator）

容器最常做的操作无疑是遍历容器中存储的元素，而实现此操作，多数情况会选用“迭代器(iterator)"来实现。
简单来讲，迭代器和C++的指针非常类似，它可以是需要的任意类型，通过迭代器可以指向容器中的某个元素，如果需要，还可以对该元素进行读/写操作。

迭代器的4种定义方式:

正向迭代器容器类名::iterator迭代器名;
常量正向迭代器容器类名::const_iterator迭代器名;
反向迭代器容器类名::reverse_iterator迭代器名;
常量反向迭代器容器类名::const_reverse_iterator迭代器名

通过定义以上几种迭代器，就可以读取它指向的元素，‘*迭代器名`就表示迭代器指向的元素。其中，常量迭代器和非常量迭代器的分别在于，通过非常量迭代器还能修改其指向的元素。另外，反向迭代器和正向迭代器的区别在于:

对正向迭代器进行++操作时，迭代器会指向容器中的后一个元素;（从前往后）
而对反向迭代器进行++操作时，迭代器会指向容器中的前一个元素。（从后往前）

注意，以上4种定义迭代器的方式，并不是每个容器都适用。有一部分容器同时支持以上4种方式，比如array、deque、vector;而有些容器只支持其中部分的定义方式，例如 forward_list 容器只支持定义正向迭代器，不支持定义反向迭代器。

简单的自己实现迭代器:

#include<iostream>
using namespace std;typedef struct Node
{struct Node* pnext = NULL;int nval;
}List;void AddNode(List*& pphead,List*& ppend,int n)
{List* pnode = new List;pnode->nval = n;pnode->pnext = NULL;if (pphead == NULL){pphead = pnode;}else{ppend->pnext = pnode;}ppend = pnode;
}
class Iterator
{
private:List* p;
public:Iterator(List* ppphead){p = ppphead;}
public:bool operator!=(List* p){if (this->p != p){return true;}else{return false;}}int operator*(){return p->nval;}List* operator++(int)//右++{List* ptemp = p;p = p->pnext;//返回之前保存的当前节点的指针 ptemp。//这是后置递增运算符的特性，即返回递增前的原值。return ptemp;}
};int main()
{List* phead = NULL;List* pend = NULL;AddNode(phead, pend, 1);AddNode(phead, pend, 2);AddNode(phead, pend, 3);AddNode(phead, pend, 4);AddNode(phead, pend, 5);Iterator ite = phead;while (ite != NULL)//重载操作符{cout << *ite << endl;ite++;}/*while (phead){cout << phead->nval << endl;phead = phead->pnext;}*/return 0;
}