安徽网站建设认准-晨飞网络,平湖市住房建设局网站,自己如何开发一个小程序,企业网站模板源码免费文章目录前言一、概念1.1 顺序容器1.2 容器适配器1.3 关联容器二、程序示例1. vector和Set自定义数据类型的访问2.vector容器嵌套3.list容器排序4.pair对组的使用总结前言
STL是C中的基于数据结构和算法的标准模板库#xff0c;可以大量节约系统开发时间#xff0c;增加程序…
文章目录前言一、概念1.1 顺序容器1.2 容器适配器1.3 关联容器二、程序示例1. vector和Set自定义数据类型的访问2.vector容器嵌套3.list容器排序4.pair对组的使用总结前言
STL是C中的基于数据结构和算法的标准模板库可以大量节约系统开发时间增加程序复用性。 STL的六大件包括容器、算法、迭代器、仿函数、适配器和空间配置器其中几乎所有代码均使用了模板类和模板函数的概念。
一、概念
容器从字面意思理解就是放东西的器件C中的容器是指将对象放入存储对象的模板类型里。 容器有以下几种
1.1 顺序容器
顺序容器也叫序列式容器是各元素之间存在顺序关系的线性表其中元素的位置固定但可用删除或插入的操作进行改变这种操作称为质变算法。
顺序容器由vector(向量)、list(列表)、deque(队列)组成。
vector是最常见的容器类型访问其中的数据有很多方法这里使用迭代器完成一般使用iterator迭代器它是指针的泛化声明的对象可以用*对象完成查看。与普通数组的不同之处在于vector是可以动态扩展的数据结构没有长度的限制其原理是重新开辟新空间来拷贝原来的数组内容然后删除原有空间。 其缺陷在于对头部进行插入或删除时效率较低。
//头文件
#includevector//定义容器
vectorint v;
//插入数据
v.push_back(1);
v.push_back(3);
v.push_back(5);
//访问数据1
for (vectorint::iterator i v.begin(); i ! v.end(); i)
{cout *i endl;
}
//[]和at访问
cout v[0] endl;
cout v.at(0) endl;
//拷贝构造完成赋值
vectorintv2(v);
v2.resize(3);
v2.insert(v2.begin(),100);
v2.erase(v2.begin());dequedouble-ended queue双端队列是一种对两端元素进行添加和删除操作的容器又称双端数组应用方式基本和vector一样。 其特点 1: 采用多个连续的内存存储数据并且在一个映射结构中保存对这些内存和顺序的跟踪索引数组是存储每段数组的首地址。 2和vevtor不同deque向两端插入或删除元素时效率较高但中间效率较低。 3deque在访问元素时比vector慢。 4deque的迭代器也支持随机访问数组元素。 工作原理 deque是由一个中控器来维护缓冲区的地址其中缓冲区存放数据。 dequeintd;for (int i 0; i 10; i){d.push_back(i);}PrintDeque(d);dequeintd1(d.begin(), d.end());PrintDeque(d1);//赋值dequeintd2;d2 d1;PrintDeque(d2);dequeintd3;//尾插d3.push_back(1);//头插d3.push_front(2);PrintDeque(d3);d3.insert(d3.begin(), 3);PrintDeque(d3);dequeint::iterator i d3.begin();d3.erase(i);//默认从小到大sort(d3.begin(), d3.end());PrintDeque(d3);d3.clear();PrintDeque(d3);list叫双向链表其数据元素是通过链表指针串连成的线性表由节点表示元素位置节点由三部分组成前驱元素指针域、数据域和后继元素指针域。前驱元素指针域保存了前驱元素的首地址数据域则是本节点的数据后继元素指针域则保存了后继元素的首地址。迭代器也是双向迭代器。 缺点 1由于list元素节点并不要求在一段连续的内存中故不支持快速随机存取只能通过“”或“–”操作将迭代器移动到后继/前驱节点元素处。 2遍历速度慢是用指针进行读取的。 3占用内存大。 优点 1可以快速的插入和删除数据。原因是list是通过指针指向来串联的插入元素的时候只需要让前后的指针指向新的元素节点即可不需移动元素位置。 2采用动态分配内存不会浪费。 //构造函数listintl;l.push_back(1);l.push_back(2);l.push_back(3);
listintl2(l.begin(),l.end());PrintList(l2);listintl3(l2);PrintList(l3);listintl4(3,10);PrintList(l4);//赋值listintl5;l5 l4;listintl6;l6.assign(l5.begin(), l5.end());listintl7;l7.assign(3, 10);PrintList(l7);//交换l.swap(l7);PrintList(l);PrintList(l7);//存取coutl.front()endl;cout l.back() endl;//list不支持随机访问listint::iterator i l.begin();i;//支持,--访问元素i--;//反转l.swap(l7);l.reverse();PrintList(l); 1.2 容器适配器
容器适配器包括stackqueuepriority_queue三种可以让基本的容器类型采用另一种更适配于当前工作要求的工作方式实现。三种适配器都需满足一定的约束条件也可以可理解为加了限制条件的容器。
stack称为栈容器是以deque为底层容器封闭一些功能而形成一种具有“先进后出”特性并不允许遍历行为的容器适配器所以stack没有迭代器。 #includestackstackints;//从栈顶入栈s.push(1);s.push(2);//判断栈顶是否为空出栈while (!s.empty()){cout s.top() endl;s.pop();}cout s.size()endl;queue又称队列必须符合先进先出原则也不允许遍历成员所以也没有迭代器。
#includeiostream
#includestring
#includequeue
#includealgorithm
using namespace std;void test()
{queueints;//从队顶入队s.push(1);s.push(2);//判断队头是否为空出队while (!s.empty()){cout s.front() endl;cout s.back()endl;s.pop();}cout s.size() endl;
}int main()
{test();system(pause);
}priority_queue称为优先队列自定义数据的优先级, 让优先级高的排在队列前面, 可以优先出队。
#include queuepriority_queueint a;for (int i 0; i 10; i){a.push(i);}while (!a.empty()){cout a.top() ;a.pop();}cout endl;
1.3 关联容器
关联容器是一种二叉树的结构没有严格的顺序关系元素位置会按照二叉树的排序方式进行在排序的时候按照升序排列。 主要包含有三种set(集合)multiset多重集合mapmultimap。
set和multiset均可以进行快速查找数据但区别在于set容器不允许有重复值multiset可以有。 set在内存中是通过链表进行排序的所以插入时比vector和deque要快但是比list慢在访问元素上比vector 慢比list快原因是list 是逐个搜索它搜索的时间是跟容器的大小成正比而关联容器 查找的复杂度是Log(N) 比vector少。
void printSet(setints)
{for (setint::iterator i s.begin(); i ! s.end(); i){cout *i ;}cout endl;
}
//降序.声明仿函数
class Comparedown
{
public:bool operator()(int a, int b)const{return a b;}
};int main()
{setints;//只能使用insert方法插入数据s.insert(1);s.insert(2);s.insert(3);//遍历容器printSet(s);//拷贝构造setints2(s);printSet(s2);//赋值setints3;s3 s2;printSet(s3);//插入s.insert(4);s.erase(s.begin());s.erase(2);printSet(s);//互换s.swap(s2);//查找setint::iterator i s.find(3);if (i! s.end()){cout *i endl;}else{cout null endl;}//统计int n s.count(3);cout n endl;//排序setint, Comparedowns5;s5.insert(3);s5.insert(2);for (setint, Comparedown::iterator i s5.begin(); i ! s5.end(); i){cout *i ;}//多重集合multisetintms;ms.insert(1);ms.insert(1);for (multisetint::iterator i ms.begin(); i ! ms.end(); i){cout *i ;}
}map 提供一种“键-值”关系的一对一的数据存储能力所有元素都是pair类型。 pair的第一个元素是键值第二个为value值。 键值即索引值在容器中不可重复其内部按链表的方式存储故也继承了链表的优缺点在插入时所有元素都会根据键值自动排序。 与set相似multimap可以实现重复数据的存储。
void printMap(mapint,intm)
{for (mapint,int::iterator i m.begin(); i ! m.end(); i){cout key (*i).first value i-secondendl;}cout endl;
}class Comparedown
{
public:bool operator()(int a, int b)const{return a b;}
};void test()
{mapint, intm;//插入数据m.insert(pairint, int(1, 2));m.insert(pairint, int(3, 4));m.insert(make_pair(2, 6));m.insert(make_pair(5, 34));m.insert(mapint, int::value_type(7, 8));printMap(m);//拷贝构造mapint, intmap1(m);//赋值mapint, intmap2;map2 m;//按key进行删除m.erase(1);printMap(m);//按key查找mapint, int::iterator i m.find(3);if (i ! m.end()){cout i-first i-second endl;}else{cout 未找到 endl;}//统计key但key不重复所以n值为0或1int n m.count(3);cout n endl;//用仿函数完成从大到小排序mapint, int,Comparedownmap4;map4.insert(make_pair(2, 6));map4.insert(make_pair(6, 6));map4.insert(make_pair(3, 6));for (mapint, int, Comparedown::iterator i map4.begin(); i ! map4.end(); i){cout key (*i).first value i-second endl;}
}int main()
{test();system(pause);
}二、程序示例
1. vector和Set自定义数据类型的访问
class Person
{
public:Person(string name, int age){this-Name name;this-Age age;}string Name;int Age;
};
//存数据
void test()
{//vectorvectorPerson v;Person p1(sun, 4);Person p2(aun, 3);Person p3(cun, 2);Person p4(dun, 1);v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);for (vectorPerson::iterator i v.begin(); i ! v.end(); i){cout (*i).Name (*i).Ageendl;cout i-Name i-Age endl;}//setsetPerson s;Person p1(sun, 4);Person p2(aun, 3);Person p3(cun, 2);Person p4(dun, 1);
}//存指针
void test1()
{vectorPerson* v;Person p1(sun, 4);Person p2(aun, 3);Person p3(cun, 2);Person p4(dun, 1);v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);for (vectorPerson*::iterator i v.begin(); i ! v.end(); i){cout (*(*i)).Name (*(*i)).Age endl;cout (*i)-Name (*i)-Age endl;}
}2.vector容器嵌套
void test()
{vectorvectorintdoublev;//创建内层容器vectorintdoublev1;//放数据for (int i 0; i 3; i){doublev1.push_back(i 1);}//放入外层容器doublev.push_back(doublev1);//遍历数据for (vectorvectorint::iterator i doublev.begin(); i ! doublev.end(); i){for (vectorint::iterator j (*i).begin(); j ! (*i).end(); j){cout *j endl;cout j endl;//内层嵌套的迭代器指针地址}cout i endl;//外层嵌套的迭代器指针地址}
}3.list容器排序
class Cat
{
public:Cat(string name, int color,int age){this-Name name;this-Color color;this-Age age;}public:string Name;int Color;int Age;
};//指定排序规则
bool Compare(Cat c1, Cat c2)
{if (c1.Color c2.Color){return c1.Age c2.Age;}else{return c1.Color c2.Color;}
}void test()
{listCatL;Cat cat1(小100, 76, 3);Cat cat2(小200, 32, 2);Cat cat3(小300, 32, 4);Cat cat4(小400, 32, 3);Cat cat5(小500, 54, 1);//插入L.push_back(cat1);L.push_back(cat2);L.push_back(cat3);L.push_back(cat4);L.push_back(cat5);for (listCat::iterator i L.begin(); i ! L.end(); i){cout (*i).Name (*i).Color (*i).Age endl;}L.sort(Compare);for (listCat::iterator i L.begin(); i ! L.end(); i){cout (*i).Name (*i).Color (*i).Age endl;}
}int main()
{test();system(pause);
}4.pair对组的使用
pair是一个模板结构体类型set集合的insert方法就是pair类模板定义的pair的参数类型有两种一个是迭代器另外一个是bool类。bool返回迭代器是否应用方法成功pair里的对象可以由pair的两个函数first和second访问。
multiset只返回迭代器类型故可以重复插入。
//set
pairiterator, bool insert(value_type _Val)
{const auto _Result _Emplace(_STD move(_Val));return {iterator(_Result.first, _Get_scary()), _Result.second};
}
//pair定义
struct pair { // store a pair of values
using first_type _Ty1;
using second_type _Ty2;//multiset
iterator insert(value_type _Val)
{return iterator(_Emplace(_STD move(_Val)).first, _Get_scary());
}
//
pairsetint::iterator, bool p s.insert(4);
if (p.second)//first返回迭代器second返回bool
{cout 插入成功 endl;
}pair既可以将2个数据组合成一组数据也可以让函数返回2个数据具体应用如下 pairstring, int p1(string(a), 3);cout p1.first p1.second endl;pairstring, int p2 make_pair(string(a), 3);cout p2.first p2.second endl; 总结
容器的构造函数和成员函数的调用规则基本是类似的但每种都会存在一点差别重点记忆vector, listmap三种的调用方式。
