C++STL笔记
长久以来软件界一直希望建立一种可重复利用的东西
面向对象和泛型编程，目的就是复用性的提升
STL从广义上分为容器，算法和迭代
容器和算法之间通过迭代器进行无缝连接
STL几乎所有的代码都采用了模板类或者模板函数
STL的六大组件
容器，算法，迭代器，仿函数，空间配置器，适配器
1.容器：各种数据结构，如vector，list，deque，set，map等，来存放数据
2.算法：各种常用的算法，如sort，find,copy,for_each等
3.迭代器：扮演了容器和算法之间的胶合器
4仿函数：行为类似函数，可作为算法的某种策略
5.适配器：一种用来修饰容器或者仿函数或迭代器接口的东西
6.空间配置器：负责空间的配置和管理
容器
容器可以分为序列式容器和关联式容器
算法
可以分为质变算法和非质变算法
迭代器
输入迭代器
输出迭代器
前向迭代器
双向迭代器
随机访问迭代器
vector的遍历方法
#include<iostream> #include<vector> using namespace std; int main(){ vector<int> a; a.push_back(10); a.push_back(20); a.push_back(30); a.push_back(40); vector<int>::iterator abegin=a.begin(); vector<int>::iterator aend=a.end(); while(abegin!=aend){ cout <<*abegin<<endl; abegin++; } return 0; }
#include<iostream> #include<vector> using namespace std; int main(){ vector<int> a; a.push_back(10); a.push_back(20); a.push_back(30); a.push_back(40); vector<int>::iterator abegin=a.begin(); vector<int>::iterator aend=a.end(); for(vector<int>::iterator it=a.begin();it!=a.end();it++){ cout <<*it<<endl; } return 0; }
#include<iostream> #include<vector> #include<algorithm> using namespace std; void myprint(int a){ cout <<a<<endl; } int main(){ vector<int> a; a.push_back(10); a.push_back(20); a.push_back(30); a.push_back(40); vector<int>::iterator abegin=a.begin(); vector<int>::iterator aend=a.end(); for_each(abegin,aend,myprint); return 0; }
Vector容器嵌套容器
vector<vector<int>>v;
#include<iostream> #include<vector> using namespace std; vector<vector<int> > v; vector<int> v1; vector<int> v2; vector<int> v3; vector<int> v4; int main(){ for(int i=0;i<4;i++){ v1.push_back(i+1); v2.push_back(i+2); v3.push_back(i+3); v4.push_back(i+4); } v.push_back(v1); v.push_back(v2); v.push_back(v3); v.push_back(v4); for(vector<vector<int> >::iterator it=v.begin();it!=v.end();it++){ for(vector<int>::iterator vit=(*it).begin();vit!=(*it).end();vit++) cout <<*vit<<' '; cout <<endl; } return 0; } /* [Error] '>>' should be '> >' within a nested template argument list vector<vector<int> >嵌套时候> >中间要加一个空格 */
string
字符串string本质是一个类
char *是个指针
string是个类，类的内部封装了char *，管理这个字符串，是个char *的容器
string中有很多成员方法
string()； //创建一个空字符串，例如string str；
string'(const char* s) //使用字符串s初始化
string(const string& str)使用一个string对象初始化另一个string对象
string(int n,char c);使用n个字符初始化
string str4;
str4.assign("hello world");
#include<iostream> #include<string> using namespace std; int main(){ string str; str.assign("hello world"); cout <<str<<endl; string str2; str2=str; cout <<str2<<endl; string str3="hello world"; cout <<str3<<endl; return 0; }
字符串拼接
#include<iostream> #include<string> using namespace std; int main(){ string str; str.assign("hello world"); str+=",hello C++"; str+='!'; str.append("\nI love Code!"); str.append("hackerdsdsg",6); str.append("tyut yyds",4,5); cout <<str<<endl; return 0; }
字符串查找
查找指定字符串是否存在
在指定位置替换字符串
find rfind
str1.find("as",1);
find找的是第一次出现的位置
rfind找的是最后一次位置
replace替换
replace(1,3,"1111");
从一位开始，替换3个字符，换成字符串" 1111"
字符串比较
compare
string存取
str.size();返回长度
str[i]; str.at(i);可以访问每一个元素
字符串的插入和删除
insert(pose,"");
erase(pose,num);
子串获取
substr
vector
单端数组
数组是静态空间，而vector可以动态扩展
并不是在原空间之后连接空间，而是找更大的内存空间，然后将原数据拷贝到新空间
构造
vector的迭代器支持随机访问
vector<int> v3(num,data);
vector<int> v2(v1.begin(),v1.end());
vector<int> v4(v3);
赋值
push_back();
v1=v2;
assign(10,100);
assign(v3.begin(),v3.end());
容量和大小
empty();
capacity(); //容器的容量
size();//返回容器中容量的大小
capacity>=size
resize(int num)重新制定容器长度
resize(int num,elem);容器如果变长，用elem填充新位置
#include<iostream> #include<vector> using namespace std; void printVector(vector<int>&v){ for(vector<int>::iterator it=v.begin();it!=v.end();it++) cout <<*it<<' '; cout <<endl; } void test01(){ vector<int>v; for(int i=0;i<10;i++) v.push_back(i); printVector(v); if(v.empty()){ cout <<"v1为空"<<endl; } else{ cout <<"v1不为空"<<endl; cout <<"v1的容量是"<<v.capacity()<<endl; cout <<"v1的大小是" <<v.size()<<endl; } v.resize(15,100); //将长度加长为15，默认用0填充新的位置 printVector(v); v.resize(5); printVector(v); //将长度缩短，超出的会删除掉 } int main(){ test01(); return 0; }
插入和删除
#include<iostream> #include<vector> using namespace std; int main(){ vector<int>v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.pop_back(); //将最后一个数据4弹出 v.insert(v.begin(),100); //在迭代器的位置插入一个数据100 v.insert(v.begin(),3,1000); //在迭代器的位置插入n个数据 v.erase(v.begin()); //将迭代器位置的数据删除 for(vector<int>::iterator it=v.begin();it!=v.end();it++) cout <<*it<<' '; cout <<endl; return 0; }
Vector的数据存取
v.size();
用中括号和at访问第i个元素
.front();
返回第一个元素
.back();
返回最后一个元素
容器互换
v1.swap(v2);
用swap收缩内存
v.resize();
vector<int>(v).swap(v);
预留空间
reserve();
不停的加数据，会重新分配内存
可以直接预存空间，避免太多次分配内存
deque
双端数组
构造函数
deque内部有个中控区，维护每段缓冲区的内容，缓冲区中存放真实数据
中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间
#include<iostream> #include<deque> using namespace std; int main(){ deque<int> u; u.push_front(1); u.push_front(2); u.push_back(3); u.push_back(4); u.push_front(5); for(deque<int>::iterator it=u.begin();it!=u.end();it++) cout <<*it<<' '; cout <<endl; cout <<u.size(); cout <<endl; cout <<u.empty(); cout <<endl; for(int i=0;i<u.size();i++) cout <<u.at(i); cout <<u.back(); return 0; }
速度没有vector快
赋值操作
d2=d1;
d3.assign(开始迭代器,终止迭代器);
大小操作
empty();
size();
resize();
插入删除
push_back();
push_front();
pop_front();
pop_back();
insert(pos,elem);
insert(pos,n,elem);
insert(pos,beg,end);
clear();
数据存取
at()或者[];
front();第一个元素;
back();最后一个元素;
排序
#include<iostream> using namespace std; #include<deque> #include<algorithm> deque<int> u; int n; int a; int main(){ cin >>n; while(n--){cin >>a; u.push_back(a);} sort(u.begin(),u.end()); for(deque<int>::iterator it=u.begin();it!=u.end();it++){ cout <<*it<<' '; } return 0; }
stack
stack<int> stk;
push();
pop();
top();
empty();
size();
queue
push();
pop();
front();
back();
empty();
size();
list
由结点组成，数据域和指针域
可以对任意位置进行快速插入和删除
容器遍历速度没有数组快
占用的空间比数组大
STL中的链表是双向循环的链表，next,prev
.front(); .back(); .begin(); pop_back(); .end();
采用动态分配内存
时间和空间额外耗费大
assign(begin,end);
.swap();
大小操作
resize();
empty();
pop_back();
pop_front();
insert();
clear();
erase();
remove();
数据存取
front();
back();
翻转和排序
reserve();
set
关联式容器
set不允许有重复的元素
multiset允许容器中有重复的元素
set叫关联式容器
multiset 允许容器中有重复的元素
set.insert(10);
交换和大小
size();
swap();
插入和删除数据
insert();
clear();
erase();
查找和统计
find();查找数值是否存在，若存在，返回下标
count(); 统计key的个数
Pari
pair<int,int> p(q,a);
pair<int,int> p=make_pair(q,a);
set容器的排序
利用仿函数
map
multimap
map<int,int>
m.insert(pair<int,int>(1,10));
swap();
