C++中的STL(标准模板库)

简介: C++中的STL(标准模板库)STL概述STL: (Standard Template Library) 标准模板库

C++中的STL(标准模板库)


STL概述

STL: (Standard Template Library) 标准模板库


包含一些常用的算法如排序查找,还有常用的数据结构如可变长数组、链表、字典等。


使用方便,效率较高


要使用其中的算法,需要#include


C++中的STL(标准模板库)是一个非常强大的工具,为程序员提供了许多高效的数据结构和算法。在本文中,我们将探讨STL的基本概念、使用方法和一些常用的数据结构和算法。


STL的基本概念

STL是由一组C++模板类和函数组成的库,包含了许多不同的容器、算法和迭代器。容器是一种存储和管理数据的对象,算法是对数据进行操作的函数,迭代器则是容器和算法之间的桥梁。


[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QeBulCDo-1681822491040)(2023-04-18-20-30-09.png)]


用sort进行排序

对基本类型的数组从小到大排序:

sort(数组名+n1,数组名+n2);

n1和n2都是int类型的表达式,可以包含变量

如果n1=0,则 + n1可以不写

将数组中下标范围为[n1,n2)的元素从小到大排序。下标为n2的元素不在排序

区间内

用sort进行排序(用法一)

int a[] = {15,4,3,9,7,2,6};

sort(a,a+7); //对整个数组从小到大排序

int a[] = {15,4,3,9,7,2,6};

sort(a,a+3); // 结果:{3,4,15,9,7,2,6}

int a[] = {15,4,3,9,7,2,6};

sort(a+2,a+5); //结果:{15,4,3,7,9,2,6}

7

用sort进行排序(用法二)

对元素类型为T的基本类型数组从大到小排序:

sort(数组名+n1,数组名+n2,greater<T>());

int a[] = {15,4,3,9,7,2,6};

sort(a+1,a+4,greater<int>()); // 结果:{15,9,4,3,7,2,6}

8

用sort进行排序(用法三)

用自定义的排序规则,对任何类型T的数组排序

sort(数组名+n1,数组名+n2,排序规则结构名());

排序规则结构的定义方式:

struct 结构名

{

bool operator()( const T & a1,const T & a2) const {

//若a1应该在a2前面,则返回true。

//否则返回false。

}

}; 9

sort排序规则注意事项

struct 结构名

{

bool operator()( const T & a1,const T & a2) const {

//若a1应该在a2前面,则返回true。

//否则返回false。

}

};

排序规则返回 true,意味着 a1 必须在 a2 前面

返回 false,意味着 a1 并非必须在 a2 前面

排序规则的写法,不能造成比较 a1,a2 返回 true 比较 a2,a1 也返回 true

否则sort会 runtime error

比较 a1,a2 返回 false 比较 a2,a1 也返回 false,则没有问题

10

用sort进行排序(用法三)

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

struct Rule1 //按从大到小排序

{

bool operator()( const int & a1,const int & a2) const {

return a1 > a2;

}

};

struct Rule2 //按个位数从小到大排序

{

bool operator()( const int & a1,const int & a2) const {

return a1%10 < a2%10;

}

};

11

用sort进行排序(用法三)

void Print(int a[],int size) {

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

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

cout << endl;

}

int main()

{

int a[] = { 12,45,3,98,21,7};

sort(a,a+sizeof(a)/sizeof(int)); //从小到大

cout << "1) "; Print(a,sizeof(a)/sizeof(int));

sort(a,a+sizeof(a)/sizeof(int),Rule1()); //从大到小

cout << "2) "; Print(a,sizeof(a)/sizeof(int));

sort(a,a+sizeof(a)/sizeof(int),Rule2()); //按个位数从小到大

cout << "3) "; Print(a,sizeof(a)/sizeof(int));

return 0;

}

1) 3,7,12,21,45,98,

2) 98,45,21,12,7,3,

3) 21,12,3,45,7,98,

用sort对结构数组进行排序(用法三)

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

struct Student {

char name[20];

int id;

double gpa;

};

Student students [] = {

{"Jack",112,3.4},{"Mary",102,3.8},{"Mary",117,3.9},

{"Ala",333,3.5},{"Zero",101,4.0}};

13

用sort对结构数组进行排序(用法三)

struct StudentRule1 { //按姓名从小到大排

bool operator() (const Student & s1,const Student & s2) const {

if( stricmp(s1.name,s2.name) < 0)

return true;

return false;

}

};

struct StudentRule2 { //按id从小到大排

bool operator() (const Student & s1,const Student & s2) const {

return s1.id < s2.id;

}

};

struct StudentRule3 {//按gpa从高到低排

bool operator() (const Student & s1,const Student & s2) const {

return s1.gpa > s2.gpa;

}

};

14

用sort对结构数组进行排序(用法三)

void PrintStudents(Student s[],int size){

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

cout << "(" << s[i].name << ","

<< s[i].id <<"," << s[i].gpa << ") " ;

cout << endl;

}

15

用sort对结构数组进行排序(用法三)

int main()

{

int n = sizeof(students) / sizeof(Student);

sort(students,students+n,StudentRule1()); //按姓名从小到大排

PrintStudents(students,n);

sort(students,students+n,StudentRule2()); //按id从小到大排

PrintStudents(students,n);

sort(students,students+n,StudentRule3()); //按gpa从高到低排

PrintStudents(students,n);

return 0;

}

(Ala,333,3.5) (Jack,112,3.4) (Mary,102,3.8) (Mary,117,3.9) (Zero,101,4)

(Zero,101,4) (Mary,102,3.8) (Jack,112,3.4) (Mary,117,3.9) (Ala,333,3.5)

(Zero,101,4) (Mary,117,3.9) (Mary,102,3.8) (Ala,333,3.5) (Jack,112,3.4)



二分查找算法

STL中的二分查找算法

 STL提供在排好序的数组上进行二分查找的算法

binary_search

lower_bound

upper_bound

18

用binary_search进行二分查找(用法一)

在从小到大排好序的基本类型数组上进行二分查找

binary_search(数组名+n1,数组名+n2,值);

n1和n2都是int类型的表达式,可以包含变量

如果n1=0,则 + n1可以不写

查找区间为下标范围为[n1,n2)的元素,下标为n2的元素不在查找区间内

在该区间内查找"等于"值”的元素,返回值为true(找到)或false(没找到)

"等于"的含义: a 等于 B <=> a < b和b < a都不成立

19

用binary_search进行二分查找(用法二)

在用自定义排序规则排好序的、元素为任意的T类型的数组中进行二分查找

binary_search(数组名+n1,数组名+n2,值,排序规则结构名());

n1和n2都是int类型的表达式,可以包含变量

如果n1=0,则 + n1可以不写

查找区间为下标范围为[n1,n2)的元素,下标为n2的元素不在查找区间内

在该区间内查找"等于"值的元素,返回值为true(找到)或false(没找到)

查找时的排序规则,必须和排序时的规则一致!

"等于"的含义: a 等于 b <=> "a必须在b前面"和"b必须在a前面"都不成立20

用binary_search进行二分查找(用法二)

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

struct Rule //按个位数从小到大排

{

bool operator()( const int & a1,const int & a2) const {

return a1%10 < a2%10;

}

};

void Print(int a[],int size) {

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

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

}

cout << endl;

}

用binary_search进行二分查找(用法二)

int main() {

int a[] = { 12,45,3,98,21,7};

sort(a,a+6);

Print(a,6);

cout <<"result:"<< binary_search(a,a+6,12) << endl;

cout <<"result:"<< binary_search(a,a+6,77) << endl;

sort(a,a+6,Rule()); //按个位数从小到大排

Print(a,6);

cout <<"result:"<< binary_search(a,a+6,7) << endl;

cout <<"result:"<< binary_search(a,a+6,8,Rule()) << endl;

return 0;

}

22

3,7,12,21,45,98,

result:1

result:0

21,12,3,45,7,98,

result:0

result:1

"等于"的含义: a 等于 b <=> "a必须在b前面"和"b必须在

a前面"都不成立

用binary_search进行二分查找(用法二)

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

struct Student {

char name[20];

int id;

double gpa;

};

Student students [] = {

{"Jack",112,3.4},{"Mary",102,3.8},{"Mary",117,3.9},

{"Ala",333,3.5},{"Zero",101,4.0}};

23

用binary_search进行二分查找(用法二)

struct StudentRule1 { //按姓名从小到大排

bool operator() (const Student & s1,const Student & s2) const {

if( stricmp(s1.name,s2.name) < 0)

return true;

return false;

}

};

struct StudentRule2 { //按id从小到大排

bool operator() (const Student & s1,const Student & s2) const {

return s1.id < s2.id;

}

};

struct StudentRule3 {//按gpa从高到低排

bool operator() (const Student & s1,const Student & s2) const {

return s1.gpa > s2.gpa;

}

};

24

用binary_search进行二分查找(用法二)

int main(){

Student s;

strcpy(s.name,"Mary");

s.id= 117;

s.gpa = 0;

int n = sizeof(students) / sizeof(Student);

sort(students,students+n,StudentRule1()); //按姓名从小到大排

cout << binary_search( students , students+n,s,

StudentRule1()) << endl;

strcpy(s.name,"Bob");

cout << binary_search( students , students+n,s,

StudentRule1()) << endl;

sort(students,students+n,StudentRule2()); //按id从小到大排

cout << binary_search( students , students+n,s,

StudentRule2()) << endl;

return 0;

}

用lower_bound二分查找下界(用法一)

在对元素类型为T的从小到大排好序的基本类型的数组中进行查找

T * lower_bound(数组名+n1,数组名+n2,值);

返回一个指针 T * p;

*p 是查找区间里下标最小的,大于等于"值" 的元素。如果找不到,p指向下标为n2的

元素

26

用lower_bound二分查找下界(用法二)

在元素为任意的T类型、按照自定义排序规则排好序的数组中进行查找

T * lower_bound(数组名+n1,数组名+n2,值,排序规则结构名());

返回一个指针 T * p;

*p 是查找区间里下标最小的,按自定义排序规则,可以排在"值"后面的元素。如果找

不到,p指向下标为n2的元素

27

用upper_bound二分查找上界(用法一)

在元素类型为T的从小到大排好序的基本类型的数组中进行查找

T * upper_bound(数组名+n1,数组名+n2,值);

返回一个指针 T * p;

*p 是查找区间里下标最小的,大于"值"的元素。如果找不到,p指向下标为n2的元素

28

用upper_bound二分查找上界(用法二)

在元素为任意的T类型、按照自定义排序规则排好序的数组中进行查找

T * upper_bound(数组名+n1,数组名+n2,值,排序规则结构名());

返回一个指针 T * p;

*p 是查找区间里下标最小的,按自定义排序规则,必须排在"值"后面的元素。如果找

不到,p指向下标为n2的元素

29

lower_bound,upper_bound用法示例

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

struct Rule

{

bool operator()( const int & a1,const int & a2) const {

return a1%10 < a2%10;

}

};

void Print(int a[],int size) {

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

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

}

cout << endl;

} 30

lower_bound,upper_bound用法示例

#define NUM 7

int main()

{

int a[NUM] = { 12,5,3,5,98,21,7};

sort(a,a+NUM);

Print(a,NUM); // => 3,5,5,7,12,21,98,

int * p = lower_bound(a,a+NUM,5);

cout << *p << "," << p-a << endl; //=> 5,1

p = upper_bound(a,a+NUM,5);

cout << *p << endl; //=>7

cout << * upper_bound(a,a+NUM,13) << endl; //=>21

31

lower_bound,upper_bound用法示例

sort(a,a+NUM,Rule());

Print(a,NUM); //=>21,12,3,5,5,7,98,

cout << * lower_bound(a,a+NUM,16,Rule()) << endl; // => 7

cout << lower_bound(a,a+NUM,25,Rule()) - a<< endl; // => 3

cout << upper_bound(a,a+NUM,18,Rule()) - a << endl; // => 7

if( upper_bound(a,a+NUM,18,Rule()) == a+NUM)

cout << "not found" << endl; //=> not found

cout << * upper_bound(a,a+NUM,5,Rule()) << endl; // =>7

cout << * upper_bound(a,a+NUM,4,Rule()) << endl; // =>5

return 0;

}



multiset

multiset用法


multiset<T> st;

定义了一个multiset变量st,st里面可以存放T类型的数据,并且能自

动排序。开始st为空

排序规则:表达式 “a < b” 为true,则 a 排在 b 前面

可用 st.insert添加元素,st.find查找元素,st.erase删除元素,复杂度

都是 log(n)

multiset 用法

#include <iostream>

#include <cstring>

#include <set> //使用multiset和set需要此头文件

using namespace std;

int main()

{

multiset<int> st;

int a[10]={1,14,12,13,7,13,21,19,8,8 };

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

st.insert(a[i]); //插入的是a [i]的复制品

multiset<int>::iterator i; //迭代器,近似于指针

for(i = st.begin(); i != st.end(); ++i)

cout << * i << ",";

cout << endl;

输出:1,7,8,8,12,13,13,14,19,21,

40

multiset 用法

i = st.find(22); //查找22,返回值是迭代器

if( i == st.end()) //找不到则返回值为 end()

cout << "not found" << endl;

st.insert(22); //插入 22

i = st.find(22);

if( i == st.end())

cout << "not found" << endl;

else

cout << "found:" << *i <<endl;

//找到则返回指向找到的元素的迭代器

输出:

not found

found:22

41

i = st.lower_bound(13);

//返回最靠后的迭代器 it,使得[begin(),it)中的元素

//都在 13 前面 ,复杂度 log(n)

cout << * i << endl;

i = st.upper_bound(8);

//返回最靠前的迭代器 it,使得[it,end())中的元素

//都在 8 后面,复杂度 log(n)

cout << * i << endl;

st.erase(i); //删除迭代器 i 指向的元素,即12

for(i = st.begin(); i != st.end(); ++i)

cout << * i << ",";

return 0;

}

输出:

13

12

1,7,8,8,13,13,14,19,21,22,

42

1,7,8,8,12,13,13,14,19,21,

multiset 上的迭代器

multiset<T>::iterator p;

p是迭代器,相当于指针,可用于指向multiset中的元素。访问multiset中的元素要通

过迭代器。

与指针的不同:

multiset上的迭代器可 ++ ,--, 用 != 和 == 比较,不可比大小,不可加减整数,不

可相减

multiset 上的迭代器

multiset<T> st;

st.begin() 返回值类型为 multiset<T>::iterator,

是指向st中的头一个元素的迭代器

st.end() 返回值类型为 multiset<T>::iterator,

是指向st中的最后一个元素后面的迭代器

对迭代器 ++ ,其就指向容器中下一个元素,-- 则令其指向上一个元素

44

自定义排序规则的multiset 用法

#include <iostream>

#include <cstring>

#include <set>

using namespace std;

struct Rule1 {

bool operator()( const int & a,const int & b) const {

return (a%10) < (b%10);

}//返回值为true则说明a必须排在b前面

};

int main() {

multiset<int,greater<int> > st; //排序规则为从大到小

int a[10]={1,14,12,13,7,13,21,19,8,8 };

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

st.insert(a[i]);

multiset<int,greater<int> >::iterator i;

for(i = st.begin(); i != st.end(); ++i)

cout << * i << ",";

cout << endl;

45 输出:21,19,14,13,13,12,8,8,7,1,

自定义排序规则的multiset 用法

multiset<int,Rule1 > st2;

//st2的元素排序规则为:个位数小的排前面

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

st2.insert(a[i]);

multiset<int,Rule1>::iterator p;

for(p = st2.begin(); p != st2.end(); ++p)

cout << * p << ",";

cout << endl;

p = st2.find(133);

cout << * p << endl;

return 0;

}

输出:

1,21,12,13,13,14,7,8,8,19,

13 46

自定义排序规则的multiset 用法

multiset<int,Rule1 > st2;

//st2的元素排序规则为:个位数小的排前面

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

st2.insert(a[i]);

multiset<int,Rule1>::iterator p;

for(p = st2.begin(); p != st2.end(); ++p)

cout << * p << ",";

cout << endl;

p = st2.find(133);

cout << * p << endl;

return 0;

}

输出:

1,21,12,13,13,14,7,8,8,19,

13 47

find(x): 在排序容器中找一个元素y,使得

“x必须排在y前面”和 “y必须排在x前面”

都不成立

自定义排序规则的multiset 用法

#include <iostream>

#include <cstring>

#include <algorithm>

#include <set>

using namespace std;

struct Student {

char name[20];

int id;

int score;

};

Student students [] = { {"Jack",112,78},{"Mary",102,85},

{"Ala",333,92},{"Zero",101,70},{"Cindy",102,78}};

struct Rule {

bool operator() (const Student & s1,const Student & s2) const {

if( s1.score != s2.score) return s1.score > s2.score;

else return (strcmp(s1.name,s2.name) < 0);

}

}; 48

自定义排序规则的multiset 用法

int main()

{

multiset<Student,Rule> st;

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

st.insert(students[i]); //插入的是students[i]的复制品

multiset<Student,Rule>::iterator p;

for(p = st.begin(); p != st.end(); ++p)

cout << p->score <<" "<<p->name<<" "

<< p->id <<endl;

Student s = { "Mary",1000,85};

p = st.find(s);

if( p!= st.end())

cout << p->score <<" "<< p->name<<" "

<< p->id <<endl;

return 0;

} 49

92 Ala 333

85 Mary 102

78 Cindy 102

78 Jack 112

70 Zero 101

85 Mary 102



set

set的用法


set和multiset的区别在于容器里不能有重复元素

a和b重复  “a必须排在b前面” 和“b必须排在a前面”都不成立

set插入元素可能不成功

51

set的用法

#include <iostream>

#include <cstring>

#include <set>

using namespace std;

int main()

{

set<int> st;

int a[10] ={ 1,2,3,8,7,7,5,6,8,12 };

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

st.insert(a[i]);

cout << st.size() << endl; //输出:8

set<int>::iterator i;

for(i = st.begin(); i != st.end(); ++i)

cout << * i << ","; //输出:1,2,3,5,6,7,8,12,

cout << endl;

52

set的用法

pair<set<int>::iterator, bool> result = st.insert(2);

if( ! result.second ) //条件成立说明插入不成功

cout << * result.first <<" already exists."

<< endl;

else

cout << * result.first << " inserted." << endl;

return 0;

}

输出:

2 already exists.

53

pair<set<int>::iterator, bool>

struct {

set<int>::iterator first;

bool second;

};

pair模板的用法

pair<T1,T2>类型等价于:

struct {

T1 first;

T2 second;

};

例如:pair<int, double> a;

等价于:

struct {

int first;

double second;

} a;

a.first = 1;

a.second = 93.93;


STL容器

STL中的容器分为序列容器和关联容器两种类型。序列容器包括vector、deque和list,它们的主要区别在于它们的存储方式和访问元素的效率。关联容器包括set、map和multiset/multimap,它们使用的是二叉树结构来存储元素,因此能够快速地查找和插入元素。


STL算法

STL中的算法包括排序、查找、替换、合并、拷贝等,这些算法都是以泛型的方式实现的,即它们可以用于任何类型的数据,而不需要重复地编写代码。使用STL算法可以大大提高代码的可读性和可维护性。


STL迭代器

迭代器是STL容器和算法之间的桥梁,它们提供了一种统一的方式来访问容器中的元素。STL迭代器分为输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器五种类型,每种类型的迭代器都有其特定的功能和限制。


STL的使用方法

使用STL非常简单,只需要包含相应的头文件即可。例如,要使用vector容器,只需要包含头文件,就可以创建一个vector对象并进行各种操作。使用STL算法也非常简单,只需要调用相应的算法函数,并传递容器或迭代器作为参数即可。


常用的STL操作

下面列出了一些常用的STL操作:


1.创建容器对象:

vector<int> v;

set<string> s;

map<int, string> m;


2.往容器中添加元素:

v.push_back(10);

s.insert("hello");

m[1] = "world";


3.遍历容器中的元素:

for(auto it = v.begin(); it != v.end(); it++) {

   cout << *it << endl;

}


4.使用STL算法:

sort(v.begin(), v.end());

auto it = find(s.begin(), s.end(), "hello");

copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));



multimap

multimap的用法


multimap容器里的元素,都是pair形式的

multimap<T1,T2> mp;

则mp里的元素都是如下类型:

struct {

T1 first; //关键字

T2 second; //值

};

multimap中的元素按照first排序,并可以按first进行查找

缺省的排序规则是 "a.first < b.first" 为true,则a排在b前面

5

multimap的应用

一个学生成绩录入和查询系统,接受以下两种输入:

Add name id score

Query score

name是个不超过16字符的字符串,中间没有空格,代表学生姓名。id

是个整数,代表学号。score是个整数,表示分数。学号不会重复,分数

和姓名都可能重复。

两种输入交替出现。第一种输入表示要添加一个学生的信息,碰到这

种输入,就记下学生的姓名、id和分数。第二种输入表示要查询,碰到这

种输入,就输出已有记录中分数比score低的最高分获得者的姓名、学号

和分数。如果有多个学生都满足条件,就输出学号最大的那个学生的信

息。如果找不到满足条件的学生,则输出“Nobody”

输入样例:

Add Jack 12 78

Query 78

Query 81

Add Percy 9 81

Add Marry 8 81

Query 82

Add Tom 11 79

Query 80

Query 81

输出样例:

Nobody

Jack 12 78

Percy 9 81

Tom 11 79

Tom 11 79

#include <iostream>

#include <map> //使用multimap和map需要包含此头文件

#include <cstring>

using namespace std;

struct StudentInfo {

int id;

char name[20];

};

struct Student {

int score;

StudentInfo info;

};

typedef multimap<int,StudentInfo> MAP_STD;

// 此后 MAP_STD 等价于 multimap<int,StudentInfo>

// typedef int * PINT;

// 则此后 PINT 等价于 int *。 即 PINT p; 等价于 int * p;

int main() {

MAP_STD mp;

Student st;

char cmd[20];

while( cin >> cmd ) {

if( cmd[0] == 'A') {

cin >> st.info.name >> st.info.id >> st.score ;

mp.insert(make_pair(st.score,st.info ));

} //make_pair生成一个 pair<int,StudentInfo>变量

//其first 等于 st.score, second 等于 st.info

else if( cmd[0] == 'Q' ){

int score;

cin >> score;

MAP_STD::iterator p = mp.lower_bound (score);

if( p!= mp.begin()) {

--p;

score = p->first; //比要查询分数低的最高分

MAP_STD::iterator maxp = p;

int maxId = p->second.id;

for(; p != mp.begin() &&

p->first == score; --p) {

//遍历所有成绩和score相等的学生

if( p->second.id > maxId ) {

maxp = p;

maxId = p->second.id ;

}

}

if( p->first == score) {

//如果上面循环是因为 p == mp.begin() 而终止,则p指向的元素还要处理

if( p->second.id > maxId ) {

maxp = p;

maxId = p->second.id ;

}

}

cout << maxp->second.name << " "

<< maxp->second.id << " "

<< maxp->first << endl;

}

//lower_bound的结果就是 begin,说明没人分数比查询分数低

else cout << "Nobody" << endl;

}

}

return 0;

}



map

map的用法


和multimap区别在于:

 不能有关键字重复的元素

 可以使用 [] ,下标为关键字,返回值为first和关键字相同的元

素的second

 插入元素可能失败


#include <iostream>

#include <map>

#include <string>

using namespace std;

struct Student {

string name;

int score;

};

Student students[5] = {

{"Jack",89},{"Tom",74},{"Cindy",87},{"Alysa",87},{"Micheal",98}};

typedef map<string,int> MP;

int main()

{

MP mp;

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

mp.insert(make_pair(students[i].name,students[i].score));

cout << mp["Jack"] << endl; // 输出 89

mp["Jack"] = 60; //修改名为"Jack"的元素的second

for(MP::iterator i = mp.begin(); i != mp.end(); ++i)

cout << "(" << i->first << "," << i->second << ") ";

//输出:(Alysa,87) (Cindy,87) (Jack,60) (Micheal,98) (Tom,74)

cout << endl;

Student st;

st.name = "Jack";

st.score = 99;

pair<MP::iterator, bool> p =

mp.insert(make_pair(st.name,st.score));

if( p.second )

cout << "(" << p.first->first << ","

<< p.first->second << ") inserted" <<endl;

else

cout << "insertion failed" << endl; //输出此信息

mp["Harry"] = 78; //插入一元素,其first为"Harry",然后将其second改为78

MP::iterator q = mp.find("Harry");

cout << "(" << q->first << "," << q->second <<")" <<endl;

//输出 (Harry,78)

return 0;

}

map例题:单词词频统计程序

输入大量单词,每个单词,一行,不超过20字符,没有

空格。 按出现次数从多到少输出这些单词及其出现次数

。出现次数相同的,字典序靠前的在前面

输入样例:

this

is

ok

this

plus

that

is

plus

plus

输出样例:

plus 3

is 2

this 2

ok 1

that 1

#include <iostream>

#include <set>

#include <map>

#include <string>

using namespace std;

struct Word {

int times;

string wd;

};

struct Rule {

bool operator () ( const Word & w1,const Word & w2) const {

if( w1.times != w2.times)

return w1.times > w2.times;

else

return w1.wd < w2.wd;

}

};

int main()

{

string s;

set<Word,Rule> st;

map<string,int> mp;

while( cin >> s )

++ mp[s] ;

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

i != mp.end(); ++i) {

Word tmp;

tmp.wd = i->first;

tmp.times = i->second;

st.insert(tmp);

}

for(set<Word,Rule>::iterator i = st.begin();

i != st.end(); ++i)

cout << i->wd << " " << i->times << endl;

}



结论

STL是C++中非常强大的一个工具,它提供了一种统一的方式来处理数据结构和算法的实现。使用STL可以大大提高代码的效率和可读性,同时也能够减少错误和bug的出现。如果你还没有使用STL,那么现在是时候学习一下了!


目录
相关文章
|
8天前
|
并行计算 C++ Windows
|
6月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
172 2
|
6月前
|
存储 算法 C++
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现,内部元素按键自动升序排列,存储键值对,支持通过键访问或修改值;而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能,并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别,强调了`map`在处理键值关系时的优势。
327 73
|
3月前
|
存储 算法 安全
c++模板进阶操作——非类型模板参数、模板的特化以及模板的分离编译
在 C++ 中,仿函数(Functor)是指重载了函数调用运算符()的对象。仿函数可以像普通函数一样被调用,但它们实际上是对象,可以携带状态并具有更多功能。与普通函数相比,仿函数具有更强的灵活性和可扩展性。仿函数通常通过定义一个包含operator()的类来实现。public:// 重载函数调用运算符Add add;// 创建 Add 类的对象// 使用仿函数return 0;
121 0
|
3月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
89 0
|
6月前
|
编译器 C++
模板(C++)
本内容主要讲解了C++中的函数模板与类模板。函数模板是一个与类型无关的函数家族,使用时根据实参类型生成特定版本,其定义可用`typename`或`class`作为关键字。函数模板实例化分为隐式和显式,前者由编译器推导类型,后者手动指定类型。同时,非模板函数优先于同名模板函数调用,且模板函数不支持自动类型转换。类模板则通过在类名后加`&lt;&gt;`指定类型实例化,生成具体类。最后,语录鼓励大家继续努力,技术不断进步!
|
6月前
|
存储 算法 C++
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器,二者均为关联式容器,底层基于红黑树实现。`set`支持唯一性元素存储并自动排序,适用于高效查找场景;`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作(如`insert`、`erase`)、查找统计(如`find`、`count`)及`multiset`特有的区间操作(如`lower_bound`、`upper_bound`、`equal_range`)。最后预告了`map`容器的学习,其作为键值对存储的关联式容器,同样基于红黑树,具有高效操作特性。
267 3
|
7月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
3月前
|
存储 编译器 程序员
c++的类(附含explicit关键字,友元,内部类)
本文介绍了C++中类的核心概念与用法,涵盖封装、继承、多态三大特性。重点讲解了类的定义(`class`与`struct`)、访问限定符(`private`、`public`、`protected`)、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数(构造函数、析构函数、拷贝构造、赋值重载)以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员(变量与函数)、友元(友元函数与友元类)的概念及其使用场景,并简要介绍了内部类的特性。
167 0
|
5月前
|
编译器 C++ 容器
【c++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
175 12