C++标准模板库（STL）之Set/List/Map/Priority_Queue/Queue/Stack/String/Vector

一、Set的用法

Set：集合，一个内部自动有序而且不重复元素的容器。使用set，要加头文件#include<set>和using namespace std;

1.1、Set的定义

set<typename> name;set<int> name;set<double> name;set<char> name;set<Node> name;//Node是结构体类型set<typename> Arrayname[arraySize];//set<int> a[100];a[0]~a[99]的每一个都是一个set容器

/*定义和写法和vector基本一样，同样typename可以是任何基本类型，结构体，STL容器类型。

　　同样，typename是容器的时候，>>后要加空格，避免编译器当成位运算出错。*/

1.2、set容器内元素的访问

set只能通过迭代器iterator访问 set<typename>::iterator it;//typename对应定义set时的类型。set<int>::iterator it;

因为除了vector和string之外的STL的容器都不支持以下标的方式访问 。

　　#include<stdio.h>

　　#include<set>using namespace std;int main()

    　　set<int> st;

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

        　　st.insert(i);

   　　 for(set<int>::iterator it=st.begin();it!=st.end();it++)

        　　printf("%d ",*it);

    　　return 0;

set内的元素，自动递增排序，并且去重。

1.3、set常用函数

1.3.1、insert()函数

insert(x)：将x插入set容器中，并且自动递增排序和去重。时间复杂度为O(logN)，N为元素个数

1.3.2、find()函数

find(value)：查找值为value的元素，返回它的迭代器。时间复杂度为O(logN),N为元素个数

1.3.3、erase()函数

erase(x)：删除单个元素，时间复杂度为O(logN)

erase(a,b);删除左闭右开区间内[a,b)的元素，时间复杂度为O(b-a)

1.3.4、size()函数

size()：用来获得set内元素的个数，时间复杂度为O(1)

1.3.5、clear()函数

clear()：用来清空set所有元素，时间复杂度为O(N)

　　#include<stdio.h>

　　#include<set>using namespace std;int main()

    　　　　set<int> st;

    　　　　st.insert(2);

    　　　　st.insert(5);

    　　　　st.insert(1);

    　　　　st.insert(2);

    　　　　st.inert(4);

    　　　　st.insert(3);

   　　　　 int len=st.size();//3

    　　　　for(set<int>::iterator it=st.begin();it!=st.end();it++)

        　　　　printf("%d ",*it);//1,2,3,4,5    }

    　　　　　st.erase(st.find(2));//利用find()函数先找到2，然后erase删除它

    　　　　   st.erase(3);//删除set中值为3的元素，时间复杂度为O(logN)

    　　　　   set<int>::iterator it=st.find(4);

    　　　　  st.erase(it,st.end());//删除元素2到set末尾之间的数，也就是4,5    st.clear();

    　　　　  int len_clear=st.size();//0

    　　　　  return 0;

1.3、set的用途

set重要的作用：自动去重，升序排序。

二、C++ STL 标准模板库（ list ）

引用头文件#include<list> list类本身是一个类模板 list链表中的迭代器list类模板的一个内部类 这个类实现了链表元素指针的功能是一个线性链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定 的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指5针将有序的元素链接起来。

由于其结构的原因， list 随机检索的性能非常的不好，因为它不像 vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找 ，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。 list 的特点：

(1) 不使用连续的内存空间这样可以随意地进行动态操作；

(2) 可以在内部任何位置快速地插入或删除，当然也可以在两端进行push和pop 。

(3) 不能进行内部的随机访问，即不支持[ ] 操作符和vector.at() ；

Lists将元素按顺序储存在链表中，与向量(vectors)相比，它允许快速的插入和删除，但是随机访问却比较慢.

//list的使用

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<list>

using namespace std;

class Student{

public:

int age;

char name[30];

void Print(){

void ProtectA(){

Student s1, s2, s3;

s1.age = 12;

strcpy(s1.name, "小米");

s2.age = 14;

strcpy(s2.name, "小红");

s3.age = 16;

strcpy(s3.name, "小刚");

list<Student *> ldata;

//从后面添加一个元素

ldata.push_back(&s1);

ldata.push_back(&s2);

ldata.push_back(&s3);

//定义迭代器

//list<Student *>::iterator current = NULL;

//报错：error C2440: “初始化”: 无法从“int”转换为“std::_List_iterator<std::_List_val<std::_List_simple_types<Student

//说明  list<Student *>::iterator本质上是list<Student *>类的一个内部类

//这个内部类重载了=运算符   构造函数可以接受一个指针

begin()方法返回的是链表头元素的迭代器

list<Student *>::iterator current = ldata.begin();

// 强调 current 是个内部类 但是迭代器的功能相当于链表元素的指针

// 迭代器步长是一个元素类型大小的字节

for (current; current != ldata.end(); current++)

Student *temp = *current;

//迭代器这个内部类重载了*运算符

cout << "学生姓名：" << temp->name << "；学生年龄是：" << temp->age << endl;

void ProtectB(){

Student s1, s2, s3;

s1.age = 12;

strcpy(s1.name, "小米");

s2.age = 14;

strcpy(s2.name, "小红");

s3.age = 16;

strcpy(s3.name, "小刚");

list<Student> ldata;

ldata.push_back(s1);

ldata.push_back(s2);

ldata.push_back(s3);

list<Student>::iterator current = ldata.begin();

for (current; current != ldata.end(); current++)

//Student *temp = current;

//报错： 2   IntelliSense:  不存在从 "std::_List_iterator<std::_List_val<std::_List_simple_types<Student>>>" 到 "Student *" 的适当转换函数    g:\test\SolutionC3\C001\tec01.cpp

//简单来说没有实现=操作符重载  所以无法赋值

//2个操作数  左操作数类型是 Student *  用户没写  c++编译无法编译通过

cout << "学生姓名：" << current->name << "；学生年龄是：" << current->age << endl;

//迭代器内部类重载了->操作符

void main(){

ProtectA();

system("pause");

三、 C++标准模板库（STL）之 Map

3.0 Map的常用用法

map：映射。可以将任何基本类型，结构体，STL容器映射到任何基本类型包括容器。

使用map，需要加map的头文件，#include<map>和using namespace std;

3.1 map的定义

map<typename1,typename2> mp;

map<string,int> mp;//如果是字符串到int的映射，必须使用string不能使用char数组。

3.2、map容器元素的访问

map的两种访问方式：下标访问、迭代器访问

3.2.1、下标访问

和访问数组一样。map中键是唯一的

3.2.2、迭代器访问

map<typename1,typename2>::iterator it;

#include<stdio.h>

#include<map>

using namespace std;

int main()

    map<char,int> mp;

    mp['a']=5;

    mp['b']=10;

    mp['d']=40;

    mp['c']=20;

    mp['c']=30;//20被覆盖

    printf("%d\n",mp['c']);

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

        printf("%c %d\n",it->first,it->second);//it->first:当前映射的键，it->second:当前映射的值    }

    //a 5  

    //b 10  

    //c 30 

    //d 40

    //map会以键从小到大的顺序自动排序。map内部是使用红黑树实现的，set内部也是。

    //建立映射的时候，会自动实现从小到大的排序功能

    return 0;

3.3、map常用函数

3.3.1、find()

find(key)：返回键为key的映射，时间复杂度为O(logN)

3.3.2、erase()

删除单个元素：

mp.erase(it)：it为需要删除的元素的迭代器。时间复杂度为O(1)

mp.erase(key):key为删除元素的键，时间复杂度为O(logN)

删除区间内的元素，左闭右开[start,end)

3.3.3、size()

3.3.4、clear()

用来清空map，复杂度为O(N)

#include<stdio.h>

#include<map>

using namespace std;

int main()

    map<char,int> mp;

    mp['a']=5;

    mp['b']=10;

    mp['d']=40;

    mp['c']=20;

    mp['c']=30;//20被覆盖

    printf("%d\n",mp['c']);//30    

    mp.erase('b');//删除键为b的映射，也就是b 10

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

        printf("%c %d\n",it->first,it->second);

    //a 5

    //c 30

    //d 40

    map<char,int>::iterator it=mp.find("a");

    mp.erase(it);//删除a 5

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

        printf("%c %d\n",it->first,it->second);

    //c 30

    //d 40

    mp['e']=50;

    mp['f']=60;

    map<char,int>::iterator it=mp.find("d");

    mp.erase(it,mp.end());//删除区间， d 40  e 50

    return 0;

3.4、map的常见用途

a、建立字符或者字符串与整数之间的映射的时候，使用map

b、判断大整数或者其他类型数据是否存在的时候，map可以当bool数组用

c、字符串和字符串的映射

四、C++标准模板库（STL）之Priority_Queue

4.0. Priority_Queue的常用用法

priority_queue：优先队列，底层是使用堆来实现的。优先队列中，队首元素一定是当前队列中优先级最高的哪一个。

a (优先级3)，b(优先级4)，c(优先级1)，出队顺序是：b（4）-》a（3）-》c（1）

4.1 priority_queue的定义

使用优先队列，要加头文件#include<queue>和using namespace std;

priority_queue<typename> pq;

4.2、priority_queue容器元素访问

优先队列和队列 queu 不一样，没有 front() 和 back() 函数，只能通过 top() 函数访问队首元素（堆顶元素），优先级最高的元素。

#include<stdio.h>

#include<queue>

using namespace std;

int main()

    priority_queue<int> q;

    q.push(3);

    q.push(4);

    q.push(1);

    printf("%d\n",q.top());//输出结果为4

    return 0;

4.3、priority_queue的常用函数

4.3.1、push()

push(x)：将x入队，时间复杂度为O(logN)，N为优先队列中元素个数。

4.3.2、top()

top()：获得堆顶元素，时间复杂度为O(1)

4.3.3、pop()

pop()：让堆顶元素出队，时间复杂度为O(logN)

4.3.4、empty()

empty()：检测优先队列是否为空，返回bool值，true为空，false非空

4.3.5、size()

size()：返回优先队列中的元素个数。

4.4、priority_queue内元素优先级的设置

4.4.1、基本数据类型的优先级设置

基本数据类型：int,double,char等。

　　priority_queue<int> pq;

　　priority_queue<int,vector<int>,less<int>> pq;/*

　　vector<int>:承载底层数据结构堆Heap的容器

　　如果第一个参数是double，那么第二个也对应是double

　　less<int>：是对第一个参数的比较类，less<int>表示的数组大的优先级越大。

　　greater<int>：表示数字小的优先级越大

　　priority_queue<int,vector<int>,greater<int>> pq;

　　//优先队列总是把最小的元素放在队首。

　　priority_queueK<int,vector<int>,less<int>> pq;

　　//优先队列总是把最大的元素放在队首。

　　#include<stdio.h>

　　#include<queue>

　　using namespace std;

　　int main()

    　　//用greater优先队列总是把最小的排在堆顶

    　　priority_queue<int,vector<int>,greater<int>> q;

    　　q.push(3);

    　　q.push(4);

   　　 q.push(1);

    　　printf("%d\n",q.top());//输出结果为1

    　　//用less优先队列总是把最大的排在堆顶

   　　 priority_queue<int,vector<int>,less<int>> pq;

    　　pq.push(3);

   　　 pq.push(5);

   　　 pq.push(2);

   　　 printf("%d\n",pq.top());//输出结果为5

   　　 return 0;

4.4.2、结构体的优先级设置

#include<stdio.h>

#include<queue>

using namespace std;struct fruit

    string name;

    int price;

    friend bool operator < (fruit f1,fruit f2)

        return f1.price<f2.price;

}f1,f2,f3;

int main()

    priority_queue<fruit> q;

    f1.name="apple";

    f1.price=3;

    f2.name="perl";

    f2.name=4;

    f3.name="banana";

    f3.price=1;

    q.push(f1);

    q.push(f2);

    q.push(f3);

    cout<<q.top.name<<" "<<q.top().prince<<endl;//banana 1

    return 0;

4.5、priority_queue的常见用途

可以解决贪心问题，也可以定义Dijkstra算法进行优化

使用top()函数，必须使用empty()判断优先队列是否为空。

五、C++ STL--queue 的使用方法

5.0 queue

q ueue 模板类的定义在<queue>头文件中。

定义queue 对象的示例代码如下：
queue<int> q1;
queue<double> q2;

queue 的基本操作有：
入队，如例：q.push(x); 将x 接到队列的末端。

出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。

访问队首元素，如例：q.front()，即最早被压入队列的元素。

访问队尾元素，如例：q.back()，即最后被压入队列的元素。

判断队列空，如例：q.empty()，当队列空时，返回true。

访问队列中的元素个数，如例：q.size()

#include <cstdlib>

#include <iostream>

#include <queue>

using namespace std;

int main()

    int e,n,m;

    queue<int> q1;

    for(int i=0;i<10;i++)

       q1.push(i);

    if(!q1.empty())

    cout<<"dui lie  bu kong\n";

    n=q1.size();

    cout<<n<<endl;

    m=q1.back();

    cout<<m<<endl;

    for(int j=0;j<n;j++)

       e=q1.front();

       cout<<e<<" ";

       q1.pop();

    cout<<endl;

    if(q1.empty())

    cout<<"dui lie  bu kong\n";

    system("PAUSE");

    return 0;

六、C++标准模板库（STL）之Stack

6.0、Stack的常用用法

stack：栈，一个后进先出的容器。

6.1、stack的定义

加上头文件#include<stack>和using namespace std;

stack<typename> sk;

6.2、stack容器元素的访问

是一种操作受限制的线性表，只能通过 top() 来访问栈顶元素。

#include<stdio.h>

#include<stack>

using namespace std;int main()

    stack<int> sk;

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

        sk.push(i);//push(i)用来把i压入栈，入栈顺序1,2,3,4,5    }

    printf("%d\n",sk.top());

    return 0;

6.3、stack常用函数

6.3.1、push()

push(x)：将x入栈，时间复杂度为O(1)

6.3.2、top()

top()：获取栈顶元素，时间复杂度为O(1)

6.3.3、pop()

pop()：出栈顶元素。

6.3.4、empty()

empty():判断栈是否为空

6.3.5、size()

size()：获得栈元素个数

#include<stdio.h>

#include<stack>

using namespace std;int main()

    stack<int> sk;

    if(sk.empty()==true)printf("Empty\n");//判断栈空

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

        sk.push(i);//push(i)用来把i压入栈，入栈顺序1,2,3,4,5    }

    printf("%d %d\n",sk.top(),sk.size());//5 5

    return 0;

6.4、stack的用途

用来模拟实现递归。程序的栈内存空间很小，如果用普通递归，可能会导致程序运行崩溃。

用栈模拟递归可以避免这种问题。

C++标准模板库（STL）之String

七、C++标准模板库（STL）之String

7.0 String的常用用法

在C语言中，使用字符数组char str[]来存字符串，字符数组操作比较麻烦，而且容易有'\0'的问题，C++在STL中加入string类型，对字符串常用的需求功能进行封装。

使用string，必须要加头文件#include<string>和using namespace std;

注意：#include<string>和#include<string.h>的区别，#inlcude<string.h>是包含了字符串常用的函数，比如strcat，strcmp。#include<string.h>和#include<cstring>等价。

7.1、string的定义

定义string的方式和基本类型定义相同。

string str;string str="abcd";

7.2、string中的内容访问

和vector一样，有两种方式：下标访问，迭代器访问

7.2.1、下标访问

可以如同字符数组一样去访问string

7.2.2、迭代器访问

string的迭代器不需要参数，直接定义string::iterator it;

#include<stdio.h>

#include<string>

using namespace std;

int main()

    string str="abcd";

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

        printf("%c ",str[i]);//a b c d    }

    //通过迭代器访问string内容

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

        pritnf("%c ",*it);

    return 0;

7.3、string常用函数

7.3.1、+，+=，字符串拼接

7.3.2、==，！=，<，<=，>=，>比较大小

7.3.3、length()/size()，字符串长度

7.3.4、insert()

7.3.5、erase()

7.3.6、clear()

7.3.7、substr()

7.3.8、replace()

#include<stdio.h>

#include<string>

using namespace std;

int main()

    string str="abcd";

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

        printf("%c ",str[i]);//a b c d    }

    //通过迭代器访问string内容

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

        pritnf("%c ",*it);

    string str1="xyz";

    string str2=str+str1;

    cout<<str2<<endl;//abcdxyz

    if(str<str1)printf("OK\n");//字符串比较，首先比较长度，长度相同的进行字典序比较。

    printf("%d %d\n",str.lenght(),str.size());//4,4//获取字符串的长度，大小

    cout<<str.insert(3,str1)<<endl;//往str[3]处插入xyz，输出abcxyzd;

    str.insert(str.begin()+3,str.begin(),str.end);

        str.substr(0,3);//substr(pos,len),从0开始，长度为3的子串

    return 0;

7.3.9、string::npos

string::npos是一个常数，本身值为-1，用来做find函数失配的返回值。

7.3.10、find()

#include<stdio.h>

#include<string>

using namespace std;

int main()

    string str="abcd";

    string str1="bc";

    if(str.find(str1)!=string::npos)

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

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

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

        cout<<"No Find"<<endl;

    return 0;

八、C++标准模板库（STL）之Vector

在C中，有很多东西需要自己实现。C++提供了标准模板库（Standard Template Libray,STL）,其中封装了很多容器，不需要费力去实现它们的细节而直接调用函数来实现功能。

具体容器链接： set ， string ， map ， queue ， priority_queue ， stack ， pair

8.0 vector的用法

vector：向量，这里叫“变长数组”，长度根据需要而自动改变的数组。有时会碰到普通数组会超过内存的情况，可以使用vector解决。而且，vector可以用来以邻接表的方式存储图，可以解决当节点数太多，无法使用邻接矩阵，又害怕使用指针实现邻接表的时候，使用很简单。

使用vector，需要添加头文件，#include<vector>，还要头文件下加入using namespace std;

8.1、vector的定义

vector<typename> name;

相当于定义了一个一维数组name[SIZE]，只不过size可以根据需要进行变化，比较节省空间，也就是变长数组

typename:任何基本类型，int,char,double,结构体,STL容器vector,set,queue等。

如果typename是STL容器，定义的时候要在>>之后加上空格，如果不加空格，编译器就把它认为是位操作。

vector<int> stu;

vector<double> stu;

vector<char> stu;

vector<Node> stu;//Node是结构体类型

vector<vector<int>> name;

二维数组的定义：一维是一个数组的数组

vector<typename> Arrayname[arraySize]

/*Arrayname[]的每一个元素都是一个vector，可以理解为两个维都是可变长的二维数组*/

写法一：vector<int> vi[100];//一维长度已经固定为arraySize

vi[0]~vi[99]中每一个都是一个vector容器。

写法二：vector<vector<int>> vi//区别：这个两个维度是变长的

8.2、vector容器内元素的访问

vector访问方式：下标访问、迭代器访问。

8.2.1、下标访问

和访问普通数组一样，下标从0~size()-1。

比如定义的：vector<typename> vi，使用vi[index](vi[0],vi[1])。

8.2.2、通过迭代器访问

迭代器（iterator）理解为类似指针的东西。

定义：vector<typename>::iterator it;//it是一个迭代器变量。

#include<stdio.h>

#include<vector>using namespace std;int main()

    vector<int> vi;

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

        vi.push_back(i);

    vector<int>::iterator it=vi.begin();//vi.begin()是vi的首元素地址，用迭代器变量it指向这个地址

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

        printf("%d\n",*(it+i));//输出vi[i];    }

    return 0;

注：vi[i]与*(vi.begin()+i)等价

end()函数：并不是取vi的尾元素地址，而是取尾元素的下一个地址。就相当于左闭右开区间。

#include<stdio.h>

#include<vector>using namespace std;int main()

    vector<int> vi;

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

        vi.push_back(i);

    vector<int>::iterator it=vi.begin();//vi.begin()是vi的首元素地址，用迭代器变量it指向这个地址

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

        printf("%d\n",*(it+i));//输出vi[i];    }

    //使用begin(),end()函数，访问

    for(vector<int>::iterator it=vi.begin();it!=vi.end();it++)

        printf("%d\n",*it);

    return 0;

注：在常用STL容器中，只有vector和string才可以使用vi.begin()+i这种迭代器加整数的写法，因为他们两个看做数组的下标的访问方式。

8.3、vector常用函数

8.3.1、push_back()函数

push_back(x)就是在vector后面添加一个元素x，时间复杂度为O(1)。

8.3.2、pop_back()函数

pop_back(x)就是删除vector的尾元素x，时间复杂度为O(1)。

8.3.3、size()函数

用来获得vector中元素的个数，时间复杂度为O(1)。

8.3.4、clear()函数

用来清空vector所有的元素，时间复杂度为O(N)，N为元素总个数。

8.3.5、insert()函数

用insert(it,x)往vector的任意迭代器it初传入一个元素x。时间复杂度为O(N)。

8.3.6、erase()函数

用erase()函数删除单个元素，或者一个区间的元素

#include<stdio.h>

#include<vector>using namespace std;

int main()

    vector<int> vi;

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

     vi.push_back(i);//jpush_back()函数应用    }

    vi.pop_back(i);//删除vi的尾部元素4

    int i=vi.size();//size()返回的unsingned类型

    vi.clear();//清空vector所有元素

    vi.insert(vi.begin()+2,23);//将23插入vi[2]的位置

    vi.erase(vi.begin()+1);//删除单个元素vi[1];

    vi.erase(vi.begin()+1,vi.begin()+3);//删除vi[1],vi[2],左闭右开区间    

    return 0;

8.4、vector常见用途

8.4.1、存储数据

vector本身可以作为数组使用，当元素个数不确定的时候，可以很好地节省空间。

有些时候需要把部分数据输出在同一行，用空格隔开数据。由于数据的个数不知道，

可以使用vector记录所有的需要输出的数据，然后一次性输出。

8.4.2、用邻接表存储图

可以使用vector实现邻接表，避免使用指针的邻接链表。

参考：https://blog.csdn.net/Honeycomb_1/article/details/104429740