c++STL容器整理笔记_c++ 不重复的容器_比小白菜还菜的博客-程序员信息网

技术标签： C++ c++STL容器 c++ 数据结构

c++STL容器:

【使用以下容器都需加上相应的头文件】

vector:

（vector所有例子中的vi为 vector vi)

1.变长数组，长度可以根据需要而自动改变的。

2.定义要求：需要到头文件加#include

3.eg：**

**需要定义类型，**并且类型与定义名之间必须要有空格

4.访问：****（1）通过下标访问

（2）迭代访问器：

定义为：vector

类似于指针

【begin（）函数作用便是取数组vi的首地址，end（）函数作用为取尾元素下一位的地址】eg：

常用函数

push_back()

push_back() 【push_back(x)就是在vector后面加一个x元素】

pop_back()

pop_back()【pop_back()就是删除末尾元素】

size()

【size()用来知道vector元素个数】eg：

clear()

【其是用来清空vector中所有元素】eg：

vi.clear()即可生效

insert()

【插入元素到数组任意位置】eg：

erase()

1.删除单个元素

eg:

vi.erease(vi.begin() + 3); //删除第三个元素

2.删除一个区间的元素

eg：

vi.(vi.begin() + 1,vi.begin() + 3) //删除的元素为vi[1],vi[2]

set：

（定义一个set st;)

1.set为一个自动有序额且不含重复元素的容器

2.set的定义：

set name;（与vector一样，也需要到类型与定义名之间加入空格）

sets name[arraySize];

3.set内元素访问：

只能通过迭代访问:

set::iterator it; //it为定义名，可以更换

for(set::iterator it = st.begin();it != st.end();it++){

cout<<*it<<endl;

}

常用函数

insert()

【insert（x）可将x插入到set容器中，您去会自动梯增排序和取重】

eg：

st.insert(2);

st.insert(3);

find（）

【find（x） x为set中的迭代器】

eg：

set::iterator it = st.find(x);

erase()

【两种用法：删除单个元素；删除一个区间的所以元素】

eg:

1.单个删除

（1） st.erase(it) // it为所要删除元素的迭代器，一般结合find（）函数使用如st.erase(st.find(x)) ;

（2）st.erase(x) // x为所要删除的值如st.erase(200);

2.区间删除

st.erase(first,last)first为所需删除区间的起始迭代器，last为所要删除区间的末尾迭代器的下一个地址

eg:

set::iterator it = st.find(x)

st.erase.(it,st.end());

size（）

同理上面，用来确定容器的元素个数的

eg：

st.size（）；

clear（）

【用来清除所有元素】

eg：st.clear（）;

string

1.定义：string str; eg: string str = “abda”;

2.string 通过下标内容访问 eg:

for(int i = 0;i < str.length();i++){

cout<<str[i];

}

（1）输入字符串：

cin>>str;

（2）输出字符串：

cout<<str;

3.通过迭代器访问 eg：

for(string::iterator it = str.begin();it != str().end();it++){

cout<<*it<<endl;

}

常用函数

operator+=

eg:

string str1 = “abd”,str2 = “abc”,str3;

str3 = str1 + str2;

str1 += str2; //将str2直接拼接到str1上

compare operator

【两个string类型可以直接使用 == , != , < , <=, > , >=比较大小,比较规则则是字典序】

eg：

string str1 = “aa”,str2 = “aaa”, str3 = “abc”, str4 = “xyz”;

if(str1 < str2) cout<<“ok1”<<endl;

if(str1 != str3) cout<<“ok2”<<endl;

if(str4 >= str3) cout<<“ok3”<<endl;

return 0;

结果：

ok1

ok2

ok3

length()/size()

【返回string长度，size()与length()基本相同】

eg：

string str = “abcxyz”;

cout<<str.length()<<size()<<endl;

结果：

insert()

1.insert()在pos号位置插入字符串string

eg：

string str1 = “abcxyz”,str2 = “opq”;

str1.insert(3,str2); //往str1[3]处的前面插入opq，这里str2的位置直接写成"opq"也行

结果：

abcopqxyz

2.insert(it,it2,it3) it为原字符串的欲插入位置，it2和it3为待插字符串的首尾迭代器,用来表示串[it2, it3）将被插在it的位置上

eg：

string str1 = “abcxyz”,str2 = “opq”;

str1.insert(str1.begin() + 3,str2.begin(), str2.end());

cout<<str1;

结果：

abcopqxyz

erase()

有两种方法：删除单个元素；删除一个区间的所有元素。

1.删除单个元素

string str = “abcdefg”;

str.erase(str.begin() + 4); //删除第四号位即e

2.删除区间元素

(1)str.erase(first,last) 其中first，last为迭代器，last为需要删除区间的末尾迭代器的下一个地址，即[first,last)

eg:

string str = “abcdefg”;

str.erase(str.begin( ) + 1,str.end() - 1);

结果：

abg

(2)str.erase(pos,length)pos为str中删除起始位置，length为长度

string str = “abcdefg”;

str.erase(3,2);

cout<<str<<endl;

结果：

abcfg

clear()

清空string中的所有数据

eg：

str.clear()

substr()

substr(pos, len)返回从pos号位开始、长度为len的子串

eg:

str = “Thank you for smile.”;

cout<<str.substr(0,5)<<endl;

cout<<str.substr(7,3)<<endl;

结果：

Thank

you

string::npos

gtringspos是一个常数，其本身的值为-1,但由于是unsignedjnt类型，因此实际上也 可以认为是unsigned_int类型的最大值。string::npos用以作为find函数失配时的返回值。例 如在下面的实例中可以认为string::npos等于-1或者4294967295

eg:

if(string::npos == -1){

cout<<"-1 is ture."<<endl;

}

fi(string::npos == 4294967295){

cout<<"4294967295 is ture”<<endl;

}

结果：

-1 is ture.

4294967295 is ture

find()

str,find(str2),当str2是str的子串时，返回其在str中第一次出现的位置；如果妃不是 str的子串，那么返回string::nposo _ str.find(str2, pos),从str的pos号位开始匹配str2,返回值与上相同。 时间复杂度为O(nm),其中n和m分别为str和str2的长度。

eg:

string str = “Thank you for your smile.”;

string str2 = “you”;

string str3 = “me”;

if(str.find(str2) != string::npos){

cout<<str.find(str2)<<endl;

}

if(str.find(str2,7) != string::npos){

cout<<str.find(str2,7)<<endl;

}

if(str.find(str3) != string::npos){

cout<<str.find(str3)<<endl;

}else{

cout<<“i konow is no positon for me.”<<endl;

}

return 0;

结果：

i konow is no positon for me.

replace()

str.replace(pos, len, str2)把str从pos号位开始、长度为len的子串替换为str2。  str.replace(itl, it2, str2)把 str 的迭代器［itl, it2)范围的子串替换为 str2。

string str = “Maybe you turn around.”;

string str2 = “will not”;

string str3 = “surely”;

cout<<str.replace(10,4,str2)<<endl;

cout<<str.replace(str.begin(),str.begin() + 5,str3)<<endl;

Maybe you will not turn around.

surely you will not turn around.

map

【映射，和python的字典有点像】

1.map的定义：

map<typename1,typename2> mp; //第一个是键的类型，第二个是值的类型

如果是int型映射到整型，如果是字符串到整型，必须要string二不能用char数组

因为char数组作为数组是不能被作为建值的，如果想用字符串做映射，必须用string

2.map的键值可以是STL容器

eg：

map<set,string> mp;

3.map容器的访问：

map一般有两种访问方式：通过下标访问或者听过迭代访问,并且注意map中的值是唯一的

（1）通过下标访问

eg：

#include

int main(){

map<char,int> mp;

mp[‘c’] = 20;

mp[‘c’] = 30;

cout<<mp[‘c’]<<endl;

return 0;

}

结果：

(2)通过迭代器访问：

eg：

mp<typename1,typename2>::it;

#include

int main(){

map<char,int> mp;

mp[‘m’] = 20;

mp[‘r’] = 30;

mp[‘a’] = 40;

for(map<char,int>::it = mp.begin();it != mp.end();it++){

cout<< it-> first,it->second<<endl; //it->first,it->second分别为当前映射的键和值，字母会按照从小到大的顺序排序eg：a<b<c…。

}

return 0;

}

结果：

a 40

m 20

r 30

常用函数

find()

find()返回值key为映射的迭代器

eg：

#include

int main(){

map<char,int> mp;

mp[‘m’] = 20;

mp[‘r’] = 30;

mp[‘a’] = 40;

mp<char,int>::iterator it = mp.find(‘m’)

cout<< it->first,it->second;

return 0;

}

结果：

m 20

erase()

删除单个元素或者删除一个区间的所有元素

1.删除单个元素：

（1）it为迭代器

mp.erase(it)

#include

int main(){

map<char,int> mp;

mp[‘m’] = 20;

mp[‘r’] = 30;

mp[‘a’] = 40;

mp<char,int>::iterator it = mp.find(‘m’);

mp.erase(it);

for(map<char,int>::it = mp.begin();it != mp.end();it++){

cout<< it-> first,it->second<<endl;

return 0;

}

结果：

a 40

r 30

（2）key为删除映射的键

mp.erase(key)

eg：

#include

int main(){

map<char,int> mp;

mp[‘m’] = 20;

mp[‘r’] = 30;

mp[‘a’] = 40;

mp.erase(‘m’);

for(map<char,int>::it = mp.begin();it != mp.end();it++){

cout<< it-> first,it->second<<endl;

return 0;

}

a 40

r 30

2.删除区间的元素

mp.erase(first,last),first为所要删除区间的起始迭代器，last为所删除区间的末尾迭代器的下一个地址[first,last)

mp<char,int>::iterator it = mp.find(‘m’);

mp.erase(it,mp.end());

for(map<char,int>::it = mp.begin();it != mp.end();it++){

cout<< it->first,it->second<<endl;

}

结果：

a 40

clear()

清空映射中所有元素

queue

1.定义：queue为队列，实现先进先出的功能

eg：queue name;

2.访问queue元素

通过front()来访问队首元素，通过back()来访问队尾元素

eg：

queue q;

for(int i = 0;i <= 5;i++){

q.push(i); //push(i)用以将i压入队列，因此为1 2 3 4 5

}

cout<<q.front(),q.back();

结果：

1 5

常用函数

push()

push(i)用以将i压入队列

front(),back()

分别访问队列首元素与尾元素

pop()

让队列首元素出队

for(int i = 1;i < 3;i++){

q.pop();

}

cout<<q.front;

结果：

empty()

empty()为检验queue是否为空，返回ture则空，false为非空

eg:

queue q;

if(q.empty == ture)

cout<<“empty”<<endl;

else

cout<<“not empty”<<endl;

q.push(1);

if(q.empty == ture)

cout<<“empty”<<endl;

else

cout<<“not empty”<<endl;

return 0;

结果：

empty

not empty

size()

返回队列类元素个数

eg：

a = q.size();

priority_queue

1.priority_queue的定义：优先队列头文件需加#include ,此处优先级自己设置

eg：

pirority_queue name;

2.prioirty_queue没有front(),back(),只有top()来访问队首元素，也就是最高优先级

eg：

#include

using namespace std;

int main(){

q.push(3);

q.push(4);

q.push(1);

cout<<q,top<<endl;

return 0;

}

结果：

push()

q.push(x)将x元素入队

top()

q.top()可以获得队首元素

pop()

q.pop() 可以令队首元素出队

empty()

检查优先队列是否为空，空返回ture，非空false；

size()

返回队列内元素个数

优先级设置

priortiy_queue

1.此处指的基本数据类型就是int型、double型、char型等可以直接使用的数据类型，优先 队列对它们的优先级设置一般是数字大的优先级越高，因此队首元素就是优先队列内元素最 大的那个（如果char型，则是字典序最大的）。对基本数据类型来说，下面两种优先队列的 定义是等价的（以int型为例，注意最后两个>之间有一个空格）：

eg:

priority_queue q;

priorty_queue<int, vector, less >

可以发现，第二种定义方式的尖括号内多出了两个参数：一个是vector,另一个是 lesso其中vector (也就是第二个参数)填写的是来承载底层数据结构堆(heap)的容 器，如果第一个参数是double型或char型，则此处只需要填写vector或vector； 而第三个参数是对第一个参数的比较类，less表示数字大的优先级越大，而 greater表示数字小的优先级越大。

eg:

priority_queue<int, vector, greater > q;

q.push(3);

q.push(4);

q.push(1);

cout<<q.top();

return 0;

结果：

2.通过重载的方式

eg：

struct fruit{

string name;

int price;

friend bool oprator < (fruit f1,fruit f2){

return f1.price <f2.price;

}

可以看到，我定义的为水果价格越高优先级就越高，如果想价格越低优先级越高，则把f1.price < f2.price; 中小于改成大于。

prioity_queue q;

stack

翻译为栈，想进后出。

1.定义：

要使用的加头文件#include ,stack name;

2.栈的访问

eg：

stack st;

for(int i = 1;i <= 5;i++){

st.push(i);

}

cout<<st.top();

return 0;

结果：

常用函数

push()

push(x)将x入栈

top()

top()获得栈顶元素

pop()

用于弹出栈顶元素

empty()

可以检测栈是否为空，空则返回ture，非空返回false；

size()

返回stack内元素的个数

pair

1.定义：合成元素，用的话徐需要到头文件加上#include

eg:pair<typename1,typename2> name;

pair<string,int> p;

如果想初始化则可以

(1)pair<string,int>(“haha”,5);

(2)make_pair(“haha”,5) //make_pair为自带的函数

2.访问

按照正常结构体取访问就可(first和second是两个元素)

eg：

pair<string,int>;

p.first = “haha”;

p.second = 5;

cout<<p.first<<" "<<p.second;

return 0;

结果：

haha 5

常用函数

比较操作数

可用==，!=,<,<=,>,>=比较大小，比较规则为先以first的大小，只有first相同才比较second

用途

1.一般用于代替二元结构体

2.作为map的键值对来进行插入，eg：

#include

using namespace std;

int main(){

map<string,int> mp;

mp.insert(make_pair(“hehe”,5));

map<string,int>::iterator it = mp.begin();

cout<< it->first<<" "<< it->second<<endl;

return 0;

}

结果：

hehe 5

algorithm头文件

常用函数

max(),min(),abs();

max(x,y)和min(x,y)分别返回x和y中最大最小值，且必须是两个数，想要是三个可以max(x,max(x,y))

abs(x)返回x的绝对值，其中x必须是整数，浮点型的绝对值用math头文件下的fabs

swap()

swap(x,y)用来交换x，y的值

reverse()

reverse(it,it2)可以将数组指针在[it,it2)之间的元素或者容器的迭代器在[it,it2)范围内的元素进行反转，eg：

#include

usingnamespace std;

int main(){

int a[5] = {1,2,3,4,5};

reverse(a,a+4);

for(int i = 0;i < 5;i++){

cout<<a[i]<<" ";

}

结果：

4 3 2 1 5

如果是对容器中的元素（例如string字符串）进行反转，结果也是一样:

eg:

string str = “abcdefghi”;

reverve(str.begin() + 2,str.begin() + 6);

for(int i = 0;i < str.length()li++){

cout<<str[i];

}

结果：

abfedcghi

next_permutation()

其为给出一个序列在全排列中的下一个序列

eg:n ==3时的全排列为：123 132 213 231 312 321

int a[3] = {1,2,3};

do{

cout<<a[0]<<a[1]<<a[2];

}while(next_permutation(a,a+3))

结果：

123 132 213 231 312 321

fill()

把某一区间的值赋为相同的值，所赋值是数组类型对应的范围值

eg：

int a[3] = {1,2,3};

fill(a,a+3,233);

for(int i = 0;i < 3;i++){

cout<<a[i];

}

结果：

233 233 233

sort()

排序函数，sort(首元素地址（必填)，尾元素地址（必填），比较函数（非必填））；

比较函数不填默认为递增排序，如果想让取从大到小则自定义cmp函数eg：

bool cmp(int a,int b){

return a>b;

}

eg：

#include

usingnamespace std;

bool cmp(int a,int b){

return a>b;

}

int main(){

int a[5] = {3,1,4,2};

sort(a,a+4); //a[0]-a[3]进行递增排序

//结果：1234

int a[5] = {3,1,4,2};

sort(a,a+4,cmp);

//结果：4321

字符的排序遵从字典序

}

结构体数组排序

#include

usingnamespace std;

struct node{

int x,y;

}ssd[10];

bool cmp(node a,node b){

return a.x>b.x;

}

int main(){

ssd[0].x = 2;

ssd[0].y = 2;

ssd[1].x = 1;

ssd[1].y = 3;

ssd[2].x = 3;

ssd[2].y = 1;

sort(ssd,ssd + 3,cmp);

for(int i = 0;i < 3;i++){

cout<<ssd[i].x,ssd[i].y<<endl;

}

return 0;

}

结果：

3 1

2 2

1 3

如果想先按x从大到小排序，但当x相等的情况下，按照y的大小从小到大排序，那么cmp的写法：

eg:

#include

usingnamespace std;

struct node{

int x,y;

}ssd[10];

bool cmp(node a,node b){

if(a.x != b.x) return a.x > b.x;

else return a.y < b.y;

}

int main(){

ssd[0].x = 2;

ssd[0].y = 2;

ssd[1].x = 1;

ssd[1].y = 3;

ssd[2].x = 2;

ssd[2].y = 1;

sort(ssd,ssd + 3,cmp);

for(int i = 0;i < 3;i++){

cout<<ssd[i].x,ssd[i].y<<endl;

}

return 0;

}

结果：

2 1

2 2

1 3

容器的排序

只有vector，string，deque可以用sort

eg：

输出结果为：aaa

bbbb

lower_bound()和upper_bound()

lower_bound(first,last,val),upper_bound(first,last,val)需要以那个在一个有序数组或者容器中，分别用来寻找[first,last)范围内第一个值大于等于和大于val的元素位置，如果是数组则返回指针，如果是容器则返回迭代器

eg：

#include

usingnamespace std;

int main(){

int a[10] = {1,2,2,3,3,3,5,5,5,5};

int *lowerPos = lower_bound(a,a+10,-1);

int *upperPos = upper_bound(a,a + 10,-1);