STL容器:C++标准库的一部分,用C++ Template机制表达泛型的库,用泛型技术设计完成实例。
Template特性:
(1)类模板偏特化,进行严格的类型检查。
(2)默认模板参数,模板中允许用默认参数。
(3)成员模板,模板类中包含模板函数
(4)关键字typename,类型前的标识, typename T::SubType *ptr 指向T中子类型的指针
template内被typename修饰的标识才会被当做类型,否则当做值。
六大组件:
(1)容器(container)
(2)算法(Algorithm)
(3)迭代器(Iterator)
(4)仿函数(Function Object)
(5)适配器(Adaptor)
(6)空间配置器(allocator)智能分配与管理内存
容器的分类: 1.序列式容器,元素位置固定:vector deque list
2.关联式容器,元素位置取决于特定的排序准则,与插入顺序无关: set 集合 map 映射 multiset multimap
1.线性容器vector,array,tuple 与 链式容器list的基本操作
线性容器(array,vector,tuple)的介绍见播客 vector array tuple
#include<iostream>
#include<stdio.h>
#include<vector>
#include<array>
#include<tuple>
#include<list>
//tuple<int, double, char *> mytuple = {100,10.8,"123456789"};
using namespace std;
//线性容器
void mainx()
{
//栈上的静态数组
array<int, 3>myarray = { 0,0,0 };
//堆上的动态数组
vector<int> myvector;
myvector.push_back(1);
}
//list适用于频繁插入删除的情况
void mainl1()
{
//不可通过下标访问
list<int> mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
//通过迭代器删除元素
auto i = mylist.begin();
++i;
mylist.erase(i); //链式存储结构,不允许下标访问,删除只能用++和--
auto j= mylist.end();
--j;
//删除链表
mylist.erase(j);
//清空链表
mylist.clear();
//迭代器list遍历
auto ibegin = mylist.begin(); //指向迭代器的指针
auto iend = mylist.end();
for (;ibegin != iend;ibegin++)
{
cout << *ibegin << endl;
printf("%p\n",ibegin);
}
cin.get();
}
//链表的插入删除,访问
void mainl2()
{
int a[5] = {1,2,3,4,5};
//列表直接通过数组初始化,传递开始地址,传递结束地址
list<int> mylist(a,a+5);
{
//指针指向迭代器,迭代访问
auto ibegin = mylist.begin();
auto iend = mylist.end();
//反向迭代器
auto rb = mylist.rbegin();
auto re = mylist.rend();
mylist.remove(3);//根据数据删除
for (;ibegin != iend;ibegin++)
{
cout << *ibegin << endl;
//指定位置插入数据
if (*ibegin == 3)
{
mylist.insert(ibegin, 30);
break;
}
}
cin.get();
}
}
//链表的合并
void mainl3()
{
int a[5] = {1,2,3,4,5};
list<int> myl1(a, a + 5);
int b[5] = {19,9,15,12,10};
list<int> myl2(b, b + 5);
myl2.sort();//排序
myl1.merge(myl2); ///链表合并
auto ibegin = myl1.begin();
auto iend = myl1.end();
for (;ibegin != iend;ibegin++)
{
cout << *ibegin << endl;
}
cin.get();
}
//删除链表中重复的元素,可以应用于链表合并排序中,删除重复的元素
void mainl4()
{
int a[6] = {1,2,99,99,103,6};
list<int> myl1(a, a + 6);
myl1.unique(); //去掉链表中重复的元素
auto ibegin = myl1.begin();
auto iend = myl1.end();
for (;ibegin != iend;ibegin++)
{
cout << *ibegin << endl;
}
cin.get();
}
2.队列queue与双端队列deque,优先队列priority_queue的基本操作,双端队列的原理。
双端队列:提供二维动态数组的功能,进行头部和尾部的删除
a. deque双端队列相对vector,不仅可以在尾部插入和删除元素,还可以在头部插入和删除元素,对应的时间复杂度都是0(1)移动一个元素,是一个实现了Random access container,back insertion sequence 和 Front insertion sequence概念的模型,一般当考虑到容器元素的内存分配策略和操作性能时,deque比vector更有优势
b. deque的元素采用分块儿的线性结构进行存储,每个块儿成称为deque块儿,大小一般为512字节,所有的deque块儿用一个Map块儿管理,每个Map数据项记录了各个deque块儿的首地址,Map是deque的中心部件,它将先于deque块儿,依照deque元素的个数计算出deque块儿数。作为Map块儿的数据项数,创建Map块儿,以后每创建一个deque块儿都将deque块儿的首地址放入Map的相应数据项中。
c. 在Map和deque块儿的结构下,deque使用了两个迭代器M_start和M_finish,对首deque块儿和末deque块儿进行控制访问
d. deque的iterator共有4个变量域,包括M_first、M_last、M_cur和M_node。M_node存放当前deque块儿的Map数据项首地址,M_first和M_last分别存放该deque块首尾元素的地址
#include<iostream>
#include<queue>
#include<stdlib.h>
#include<string>
#include<vector>
#include<deque> //双端队列
using namespace std;
void mainq()
{
//双端容器
queue<char *> myq;
myq.push("calc");
myq.push("mspaint");
myq.push("notepad");
while (!myq.empty())
{
//获取要弹出的数据
char *p = myq.front();
system(p);
myq.pop();
}
cin.get();
}
//双端队列
//提供二维动态数组的功能,进行头部和尾部的删除
/*
1.deque双端队列相对vector,不仅可以在尾部插入和删除元素,还可以在头部插入和删除元素,
对应的时间复杂度都是0(1)移动一个元素,是一个实现了Random access container,
back insertion sequence 和 Front insertion sequence
概念的模型,一般当考虑到容器元素的内存分配策略和操作性能时,deque比vector更有优势
2.deque的元素采用分块儿的线性结构进行存储,每个块儿成称为deque块儿,大小一般为512字节,
所有的deque块儿用一个Map块儿管理,每个Map数据项记录了各个deque块儿的首地址,
Map是deque的中心部件,它将先于deque块儿,依照deque元素的个数计算出deque块儿数。
作为Map块儿的数据项数,创建Map块儿,以后每创建一个deque块儿都将deque块儿的首地址放入Map的相应数据项中。
3. 在Map和deque块儿的结构下,deque使用了两个迭代器M_start和M_finish,对首deque块儿和末deque块儿进行控制访问
4.deque的iterator共有4个变量域,包括M_first、M_last、M_cur和M_node。M_node存放当前deque块儿的Map数据项首地址,
M_first和M_last分别存放该deque块首尾元素的地址*/
void maindq()
{
deque<int> mydq;
mydq.push_back(1);
mydq.push_back(11);
mydq.push_back(1111);
mydq.push_back(11111);
mydq.push_back(111111);
mydq.push_front(123);//头部插入
mydq.insert(mydq.begin() + 3, 100);
mydq.erase(mydq.begin());//删除
mydq.pop_back();// mydq.erase(mydq.end()-1);
mydq.pop_back(); //尾部弹出
mydq.pop_front(); //头部弹出
mydq.clear();//清除数据
for (int i = 0;i < mydq.size();i++)
{
cout << mydq[i] << endl;
}
auto ib = mydq.begin();
auto ie = mydq.end();
for (;ib != ie;ib++)
{
cout << *ib << endl;
}
cin.get();
}
void maindq1()
{
deque<int> mydq1;
mydq1.push_back(1);
mydq1.push_back(11);
mydq1.push_back(1111);
mydq1.push_back(11111);
mydq1.push_back(111111);
deque<int> mydq2;
mydq2.push_back(2);
mydq2.push_back(21);
mydq2.push_back(21111);
mydq2.push_back(211111);
mydq2.push_back(2111111);
mydq1.swap(mydq2);//整体交换
//最多可以装多少元素
cout << mydq1.max_size() << endl;
auto ib = mydq1.begin();
auto ie = mydq1.end();
for (;ib != ie;ib++)
{
cout << *ib << endl;
}
cin.get();
}
void mainq2()
{
priority_queue<int> myq;
myq.push(1112);
myq.push(11);
myq.push(1111);
myq.push(11111);
myq.push(111111); //自动排序
while (!myq.empty())
{
//获取要弹出的数据
cout << myq.top() << endl;
myq.pop();
}
cin.get();
}
struct student
{
int age;
string name;
};
//结构体重载括号
struct stuless
{
bool operator()(const student &s1,const student &s2)
{
return s1.age > s2.age;
}
};
//优先队列的实现排序
void main()
{
priority_queue<student,vector<student>,stuless> myq;
student s1;
s1.age = 10;
s1.name = "john";
student s2;
s2.age = 22;
s2.name = "herry";
student s3;
s3.age = 20;
s3.name = "jack";
myq.push(s1);
myq.push(s2);
myq.push(s3);
while (!myq.empty())
{
cout << myq.top().age << ' ' << myq.top().name << endl;
myq.pop();
}
cin.get();
}
3. 栈stack的基本操作
#include<iostream>
#include<stack>
using namespace std;
//通过栈实现进制装换
void mains1()
{
int num;
cin >> num;
stack<int> mystack;
for (;num;num /= 2)
{
mystack.push(num%2);
cout << "当前元素个数" << mystack.size()<< endl;
}
while (!mystack.empty())
{
int num = mystack.top();
cout << num<< ' ';
mystack.pop();
}
cin.get();
cin.get();
}
//通过栈实现数据的逆序输出
void mains2()
{
int a[10] = {1,2,3,4,5,6,7,8,9,10};
stack<int> mys;
for (int i = 0;i < 10;i++)
{
mys.push(a[i]);
}
while (!mys.empty())
{
int num = mys.top();
cout << num << " ";
mys.pop();
}
cin.get();
}
下一篇 :集合set multiset bitset 映射 map 以及散列hash的介绍
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)