贵阳网站app制作,教育网站制作定制,网站源码下载免费源码,如何用wordpress做淘宝客目录
STL基本概念
STL六大组件
STL的优点
STL三大组件
容器
算法
迭代器
普通的迭代器访问vector容器元素
算法for_each实现循环
迭代器指向的元素类型是自定义数据类型
迭代器指向容器
常用容器
string容器
string的基本概念
string容器的操作
string的构造函…目录
STL基本概念
STL六大组件
STL的优点
STL三大组件
容器
算法
迭代器
普通的迭代器访问vector容器元素
算法for_each实现循环
迭代器指向的元素类型是自定义数据类型
迭代器指向容器
常用容器
string容器
string的基本概念
string容器的操作
string的构造函数
string基本赋值操作
string的存取字符串操作
string拼接操作
string的查找与替换
string比较操作
string子串
string插入和删除操作
string对象的类型转换
vector容器
vector容器基本概念
vector的数据结构
vector的构造函数
vector常用赋值操作
vector大小操作
vector容器数据存储操作
vector容器的插入和删除
利用swap收缩空间
deque容器
deque容器基本概念
deque容器的实现原理
deque的api—构造函数
deque的aip—赋值操作
deque的api—容器的大小操作
deque的api—双端的插入和删除
deque的api—数据存储
deque的api—插入操作
deque的api—删除操作 STL基本概念
STL(Standard Template Library标准模板库)是惠普实验室开发的一系列软件的统 称。现在主要出现在c中但是在引入c之前该技术已经存在很长时间了。 STL从广义上分为容器(container)算法(algorithm)迭代器(iterator)容器和算法之间通过迭代器进行无缝连接。STL 几乎所有的代码都采用了模板类或者模板函数这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。STL(Standard Template Library)标准模板库在我们c标准程序库中隶属于STL的占到了80%以上。
STL六大组件
容器保存数据的空间结构如vector、list、deque、set、map等
算法特定的的求解步骤如sort、find、copy、for_each。
迭代器本质是一个指针
仿函数函数对象重载了operator()的类
适配器一种用来修饰容器或者仿函数或迭代器接口的东西。
空间配置器负责内存空间的申请 释放 管理等
STL的优点
STL 具有高可重用性高性能高移植性跨平台的优点。 高可重用性STL中几乎所有的代码都采用了模板类和模版函数的方式实现这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。 高性能如map 可以高效地从十万条记录里面查找出指定的记录因为map 是采用红黑树的变体实现的。
STL三大组件
容器
保存数据的(数据结构)
常用的数据结构数组(array)链表(list)tree(树)栈(stack)队列(queue)集合(set)映射表(map)根据数据在容器中的排列特性这些数据分为序列式容器和关联式容器两种。 序列式容器强调值的排序序列式容器中的每个元素均有固定的位置除非用删除或插入的操作改变这个位置。Vector容器、Deque容器、List容器等。 关联式容器是非线性的树结构更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。关联式容器另一个显著特点是在值中选择一个值作为关键字key这个关键字对值起到索引的作用方便查找。Set/multiset 容器 Map/multimap容器
算法
以有限的步骤解决逻辑或数学上的问题这一门学科我们叫做算法(Algorithms). 广义而言我们所编写的每个程序都是一个算法其中的每个函数也都是一个算法毕竟它们都是用来解决或大或小的逻辑问题或数学问题。STL收录的算法经过了数学上的效能分析与证明是极具复用价值的包括常用的排序查找等等。特定的算法往往搭配特定的数据结构算法与数据结构相辅相成。 算法分为质变算法和非质变算法。质变算法指运算过程中会改变该区间内的元素的内容如拷贝替换删除等。非质变算法是指运算过程中不会改变该区间内的元素的内容如查找遍历计数等。
迭代器
普通的迭代器访问vector容器元素
#include iostream
#include string.h
#include iterator
#include vector
using namespace std;void test01()
{vectorint v;v.push_back(2);v.push_back(5);v.push_back(4);v.push_back(7);//若需要访问容器内的元素 需要拿到容器首元素的迭代器(指针)vectorint::iterator it_s v.begin();vectorint::iterator it_e v.end();for(;it_s ! it_e;it_s){cout *it_s ;}cout endl;}int main()
{test01();return 0;
}算法for_each实现循环
void printf(int a)
{cout a endl;
}
void test01()
{vectorint v;v.push_back(2);v.push_back(5);v.push_back(4);v.push_back(7);//若需要访问容器内的元素 需要拿到容器首元素的迭代器(指针)vectorint::iterator it_s v.begin();vectorint::iterator it_e v.end();/*for(;it_s ! it_e;it_s){cout *it_s ;}*/cout endl;for_each(it_s,it_e,printf);//头地址 尾地址 回调函数}
迭代器指向的元素类型是自定义数据类型
#include iostream
#include string.h
#include iterator
#include vector
using namespace std;class person
{
public:person(int age){this-age age;}int age;};
void printf(person p)
{cout p.age endl;
}
void test01()
{person p1(1);person p2(2);person p3(3);person p4(4);vectorperson v;v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);vectorperson::iterator it_s v.begin();vectorperson::iterator it_e v.end();for(;it_s ! it_e;it_s){//对容器取* 得到的是里的类型printf(*it_s);}cout endl;
}迭代器指向容器
#include iostream
#include string.h
#include iterator
#include vector
using namespace std;void test01()
{vector vectorint v;//数据类型为容器的容器vectorint v1;vectorint v2;vectorint v3;for(int i 0;i3;i){v1.push_back(i);//小容器v1尾部插入 0 1 2v2.push_back(i10);//v2尾部插入 10 11 12v3.push_back(i100);//v3尾部插入 100 101 102}//小容器插入大容器v.push_back(v1);v.push_back(v2); v.push_back(v3);vectorvectorint::iterator it v.begin();//大容器头地址for(;it!v.end();it ){//*it得到的是vectorintvectorint::iterator it1 (*it).begin();//小容器头vectorint::iterator it2 (*it).end();//尾for(;it1!it2;it1){cout *it1 endl;}}}int main()
{test01();return 0;
}
常用容器
string容器
string的基本概念
string容器是一个类 容器中有一个指针 指针维护了一个数组
string容器提供了copy find insert replace等功能
string容器的操作
string的构造函数 string();//创建一个空的字符串 例如 string str; string(const string str);//使用一个string对象初始化另一个string对象 string(const char* s);//使用字符串s初始化 string(int n, char c);//使用n个字符c初始化v
#include iostream
#include string.h
#include iterator
#include vector
#include string
using namespace std;void test01()
{string str;string str1(hello);string str2(str1);string str3(5,k);cout str1 endl;cout str2 endl;cout str3 endl;
}int main()
{test01();return 0;
}编译运行 string基本赋值操作
string operator(const char* s);//char*类型字符串 赋值给当前的字符串 string operator(const string s)//把字符串s 赋给当前的字符串 string operator(char c);//字符赋值给当前的字符串 string assign(const char *s)//把字符串s 赋给当前的字符串 string assign(const char *s, int n)//把字符串s的前n个字符赋给当 当前的字符串string assign(const string s)//把字符串s 赋给当前字符串 stringassign(int n, char c)//用n个字符c 赋给当前字符串 string assign(const string s, int start, int n)//将s从start 开始n个字符赋值给字符4
#include iostream
#include string.h
#include iterator
#include vector
#include string
using namespace std;void test01()
{string str(helloworld);string str1(heihei);str str1;str hehe;str c;str.assign(str1);str.assign(jack);str.assign(jack,2); cout str endl;str.assign(5,c);cout str endl; str.assign(str1,2,3);cout str endl;
}int main()
{test01();return 0;
}
编译运行 string的存取字符串操作
char operator[](int n);//通过[]方式取字符串
char at(int n);//通过at方法获取字符
#include iostream
#include string.h
#include iterator
#include vector
#include string
using namespace std;void test01()
{string str(helloworld);cout str[4] endl;//输出ostr[4] c;cout str.at(4) endl;//输出c
}int main()
{test01();return 0;
}string拼接操作
string operator(const string str)//重载操作符
string operator(const char* str)//重载操作符
string operator(const char c)//重载操作符
string append(const char *s)//把字符串s连接到当前字符串结尾
string append(const char *s, int n)//把字符串s的前n个字符连接到当前字符串结尾
string append(const string s);//同operator()
string append(const string s,int pos,int n)//把字符串s中从pos开始的n个字符连接到当前字符串尾
string append(int n,char c);//在当前字符串结尾添加n个字符c
#include iostream
#include string.h
#include iterator
#include vector
#include string
using namespace std;void test01()
{string str1(helloworld);cout str1 endl;string str2(123456789);str1 str2;cout str1 endl;str1 hehe;cout str1 endl;str1 c;cout str1 endl;str1.append(hehe);cout str1 endl;str1.append(hehe,2);cout str1 endl;str1.append(str2,2,3);cout str1 endl;
}int main()
{test01();return 0;
}
编译运行 string的查找与替换
int find(const string str, int pos 0) const//查找str第一次出现位置从pos开始查找
int find(const char* s, int pos 0) const; //查找s第一次出现位置从pos开始查找
int find(const char* s, int pos, int n) const//从pos 位置查找s的前n个字符第一次位置
int find(const char c, int pos 0) const; //查找字符c第一次出现位置
int rfind(const string str, int pos npos) const//查找str最后一次位置从pos开始查找
int rfind(const char* s, int pos npos) const//查找s最后一次出现位置从pos开始查找
int rfind(const char* s, int pos, int n) const//从pos 查找s的前n个字符最后一次位置
int rfind(const char c, int pos 0) const//查找字符c最后一次出现位置
string replace(int pos, int n, const string str)//替换从pos开始n个字符为字符串
strstring replace(int pos, int n, const char* s)//替换从pos开始的n个字符为字符串s
#include iostream
#include string.h
#include iterator
#include vector
#include string
using namespace std;void test01()
{string str1(helloworld);string str2(wor);cout str1.find(str2) endl;cout str1.find(wor) endl;cout str1.find(world,0,2) endl;cout str1.find(o) endl;cout str1.rfind(rl) endl;//rfind 从右往左查str1.replace(2,4,str2);cout str1 endl;
}int main()
{test01();return 0;
}编译运行 string比较操作
compare函数在时返回1时返回-1时返回0
比较区分大小写比较时参考字典顺序排前面的小 大写的A比小写的a小
int compare(const string s) const;//与字符串s比较
int compare(const char *s) const;//与字符串s比较 void test01() { string str1(helo); string str2(world); cout str1.compare(str2) endl;//输出-1 } string子串
string substr(int pos 0,int n npos);//返回由pos开始的n个字符组成的字符串 void test01() { string str1(heloworld); cout str1.substr(4,3) endl;//输出wor } string插入和删除操作
string insert(int pos, const char* s);//插入字符串
string insert(int pos, conststring str);//插入字符串
string insert(int pos,int n,char c);//在指定位置插入n个字符串c
string erase(int pos. int n,char c);//指定位直插入n个字符c
string erase(int pos, int n npos);//删除从Pos开始的n
#include iostream
#include string.h
#include iterator
#include vector
#include string
using namespace std;void test01()
{string str1(helloworld);str1.insert(2,kk);cout str1 endl;string str2(helloworld);string str(hello);str2.insert(2,str);cout str2 endl;string str3(helloworld);str3.insert(2,10,r);cout str3 endl;string str4(helloworld);str4.erase(3,3);cout str4 endl;
}int main()
{test01();return 0;
}编译运行 string对象的类型转换
//string 转 char* string str itcast; const char* cstr str.c_str(); //char* 转 string char*s itcast; string str(s); 在c中存在一个从const char到string的隐式类型转换却不存在从一个string对象到Cstring的自动类型转换。对于string类型的字符串可以通过cstr()函数返回string对象对应的C_string. 通常程序员在整个程序中应坚持使用string类对象直到必须将内容转化为char时才将其转换为C_string.
提示 为了修改 string字符串的内容下标操作符[]和 at 都会返回字符的引用。但当字符串的内存被重新分配之后可能发生错误. void test01() { string str(helloworld); str world;//调用str.operator(char *) char *s NULL; //str.c_str();//得到const char * //去const s cosnt castchar *(str.c_str()); } vector容器
vector容器基本概念
向量 vector是一种对象实体, 能够容纳许多其他类型相同的元素, 因此又被称为容器。 与string相同, vector 同属于STL(Standard Template Library, 标准模板库)中的一种自定义的数据类型, 可以广义上认为是数组的增强版。在使用它时, 需要包含头文件 #includevector。vector 容器与数组相比其优点在于它能够根据需要随时自动调整自身的大小以便容下所要放入的元素。此外, vector 也提供了许多的方法来对自身进行操作。
vector 型变量的声明以及初始化的形式也有许多, 常用的有以下几种形式 vectorint a ; //声明一个int型向量a vectorint a(10) ; //声明一个初始大小为10的向量 vectorint a(10, 1) ; //声明一个初始大小为10且初始值都为1的向量 vectorint b(a) ; //声明并用向量a初始化向量b vectorint b(a.begin(), a.begin()3) ; //将a向量中从第0个到第2个(共3个)作为向量b的初始值 除此之外, 还可以直接使用数组来初始化向量: int n[] {1, 2, 3, 4, 5} ; vectorint a(n, n5) ; //将数组n的前5个元素作为向量a的初值
vectorint a(n[1], n[4]) ; //将n[1] - n[4]范围内的元素作为向量a的初值vector的数据结构
Vector所采用的数据结构非常简单线性连续空间它以两个迭代器Myfirst和Mylast分别指向配置得来的连续空间中目前已被使用的范围并以迭代器_Myend指向整块连续内存空间的尾端。 为了降低空间配置时的速度成本vector实际配置的大小可能比客户端需求大一些以备将来可能的扩充这边是容量的概念。换句话说一个vector的容量永远大于或等于其大小一旦容量等于大小便是满载下次再有新增元素整个vector容器就得另觅居所。 注意 所谓动态增加大小并不是在原空间之后续接新空间(因为无法保证原空间之后尚有可配置的空间)而是一块更大的内存空间然后将原数据拷贝新空间并释放原空间。因此对vector的任何操作一旦引起空间的重新配置指向原vector的所有迭代器就都失效了。这是程序员容易犯的一个错误务必小心。
vector的构造函数
vectorTv//采用模板实现类实现默认构造函数
vector(v.begin(), v.end())//将头和尾区间中的元素拷贝给本身
vector(n, elem)//构造函数将n个elem拷贝给本身
vector(const vector vec)//拷贝构造函数 void printf(int a) { cout a endl; } void test01() { vectorint v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); //vectorint v2(v1); //vectorint v2(v1.begin(), v1.end())//将头和尾区间中的元素拷贝给本身 vectorint v2(v1.begin()1, v1.end())//将头和尾区间中的元素拷贝给本身 for_each(v2.begin(),v2.end(),printf); } vector常用赋值操作
assign(beg, end)//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem)//将n个elem拷贝赋值给本身。
vectoroperator(const vector vec)//重载等号操作符
swap(vec)//将vec与本身的元素互换。
void printf(int a) { cout a endl; } void test01() { vectorint v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); vectorint v2; v1.push_back(5); v1.push_back(6); v1.push_back(7); v1.push_back(8); //v2.assign(v1.begin(),v1.end());//将[beg, end)区间中的数据拷贝赋值给本身 //v2.assign(10,5);//将n个elem拷贝赋值给本身 //v2 v1;//重载等号操作符 v2.swap(v1);//v1和v2的指针指向交换 for_each(v2.begin(),v2.end(),printf); } vector大小操作
size()//返回容器中元素的个数 empty();//判断容器是否为空 resize(int num)//重新指定容器的长度为num若容器变长则以默认值填充新位置。如果容器变短则末尾超出容器长度的元素被删除。 resize(int num, elem);//重新指定容器的长度为num若容器变长则以elem值填充新位置。如果容器变短则末尾超出容器长度的元素被删除。 capacity();//容器的容量 reserve(int Len);//容器预留Len个元素长度预留位置不初始化元素不可访问。
void printf(int a)
{cout a endl;
}void test01()
{vectorint v1;v1.push_back(1); v1.push_back(2);v1.push_back(3);v1.push_back(4);cout v1.size() endl;//大小cout v1.capacity() endl;//容量v1.resize(10);if(!v1.empty()){cout 不为空 endl;}for_each(v1.begin(),v1.end(),printf());//1234000000vectorint v2;v2.reserve(1000);//为v2预留1000个空间 设置容量cout v2.size() endl;//0cout v2.capacity() endl;//1000
}
vector容器数据存储操作
at(int idx)//返回索引idx 所指的数据如果idx 越界 抛出out_of_range异常。
operator[]//返回索引idx所指的数据越界时 运行直接报错
front()//返回容器中第一个数据元素
back()//返回容器中最后一个数据元素
#include iostream
#include string.h
#include iterator
#include vector
#include string
using namespace std;void printf(int a)
{cout a endl;
}void test01()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);cout v1.at(2) endl;//3cout v1[2] endl;//3cout v1.front() endl;//1cout v1.back() endl;//4
}int main()
{test01();return 0;
}vector容器的插入和删除
insert(const_iterator pos, int count,ele 一 代器指向位置pos插入count 个元素ele.push_back(ele)//尾部插入元素ele pop_back()//删除最后一个元素 erase(const_iterator start, const_iterator end)//删除迭代器从start 到end之间的元erase(const_iterator pos);//删除迭代器指向的元素 clear()//删除容器中所有元素
利用swap收缩空间
swap收缩空间的本质是指针指向了不同的容器
#include iostream
#include string.h
#include iterator
#include vector
#include string
#include iostream
#include vector
#include string
using namespace std;void test01()
{vectorint v1;for (int i 0; i 1000; i){v1.push_back(i);}cout v1.size() v1.capacity() endl;//1000 1024v1.resize(10);//cout v1.size() v1.capacity() endl;//10 1024vectorint(v1).swap(v1);cout v1.size() v1.capacity() endl;//10 10}int main()
{test01();return 0;
}
deque容器
deque容器基本概念
Deque 容器和vector容器最大的差异一在于deque允许使用常数项时间对头端进行元素的插入和删除操作。二在于deque没有容量的概念因为它是动态的以分段连续空间组合而成随时可以增加一段新的空间并链接起来换句话说像vector那样”旧空间不足而重新配置一块更大空间然后复制元素再释放旧空间”这样的事情在deque身上是不会发生的。也因此deque没有必须要提供所谓的空间保留(reserve)功能. 虽然deque容器也提供了Random Access lterator但是它的迭代器并不是普通的指针其复杂度和vector不是一个量级这当然影响各个运算的层面。因此除非有必要我们应该尽可能的使用vector而不是deque。对deque进行的排序操作为了最高效率可将deque先完整的复制到一个vector中对vector容器进行排序再复制回deque 双端数组deque和vector的区别 vector对于头部的插入效率低数据量越大效率越低 deque相对而言对头部的插入删除速度会比vector快 vector访问元素时的速度会比deque快这和两者内部实现有关
deque容器的实现原理
Deque 容器是连续的空间至少逻辑上看来如此连续现行空间总是令我们联想到 array数组 和vector,array 无法成长,vector 虽可成长却只能向尾端成长而且其成长其实是一个假象事实上(1) 申请更大空间 2)原数据复制新空间 3)释放原空间 三步骤如果不是 vector 每次配置新的空间时都留有余裕其成长假象所带来的代价是非常昂贵的。 Deque 是由一段一段的定量的连续空间构成。一旦有必要在 deque 前端或者尾端增加新的空间便配置一段连续定量的空间串接在 deque 的头端或者尾端。Deque 最大的工作就是维护这些分段连续的内存空间的整体性的假象并提供随机存取的接口避开了重新配置空间复制释放的轮回代价就是复杂的迭代器架构。既然 deque 是分段连续内存空间那么就必须有中央控制维持整体连续的假象数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque代码的实现远比vector或list 都多得多。Deque 采取一块所谓的 map(注意不是 STL的 map 容器)作为主控这里所谓的 map 是一小块连续的内存空间,其中每一个元素(此处成为一个结点)都是一个指针指向另一段连续性内存空间称作缓冲区。缓冲区才是deque的储存空间的主体。 deque的api—构造函数
dequeT deqT;//默认构造形式
deque(begend);//构造函数将[begend)区间中的元素拷贝给本身
deque(neLem);//构造函数将n 个eLem 拷贝给本身。
deque(const deque deq);//拷贝构造函数。
void print(int a)
{cout a endl;
}void test01()
{//构造dequeint d1;d1.push_back(1);d1.push_back(2);d1.push_back(3);dequeint d2(d1.begin(),d1.end());dequeint d3(d1);dequeint d4(10,8);//遍历for_each(d1.degin(),d1.end(),print);
}
deque的aip—赋值操作
assign(begend);//将[beg end)区间中的数据拷贝赋值给本身。
assign(nelem);//将n个elem拷贝赋值给本身。
deque operator(const deque deq); //重载等号操作符
swap(deq);// 将deq与本身的元素互换 dequeint d3; dequeint d4; d4.assign(d3); d4 d3; d3.swap(d4); for_each(d4.begin(),d4.end(),print); deque的api—容器的大小操作
deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长则以默认值填充新位置。如果容器变短则末尾超出容器的元素被删除
deque.resizenumelem); //重新指定容器的长度为num,若容器变长则以elem值填充新位置,如果容器变短则末尾超出容器长的的元素被删除
#include iostream
#include string.h
#include iterator
#include vector
#include string
#include algorithm
#include deque
using namespace std;void print(int a)
{cout a endl;
}void test01()
{dequeint d1;d1.push_back(1);d1.push_back(2);d1.push_back(3);cout d1.size() endl;if(!d1.empty()){cout 不为空 endl;}d1.resize(3);d1.resize(4,5);for_each(d1.begin(),d1.end(),print);}int main()
{test01();return 0;
}编译运行 deque的api—双端的插入和删除
push_back(eLem);//在器尾部添加一个数据 push_front(eLem);//在容器头部插入一个数据 pop_back();//删除器最后一个数据 pop_front();//删除容器第一个数据
deque的api—数据存储
at(idx);//返回索引idx 所指的数据如idx 越界抛出out_of_range。 operator[];//返回索引dx 所指的数据如idx 越界不地出异直接出错。 front();//返回第一个数据。 back();//返回最后一个数据
deque的api—插入操作
insert(pos,eLem);//在pos 位置插入一个eLem 元素的拷贝返回新数据的位置。 insert(pos,n,elem);//在pos 位置插An 个eLem 数据无返回值。 insert(pos,beg,end);//在pos 位置插入[beg,end)区间的数据无返回值。
deque的api—删除操作
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据返回下一个数据的位智
erase(pos);//删除pos 位置的数据返回下一个数据的位置。
