C++ STL库函数
p.s. 此文章为word直接复制粘贴生成,未对格式进行修正,请周知!
word版本下载请见:https://download.csdn.net/download/zjw1111/9979516
一.集合(set) 头文件<set>
定义:
由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种作用于元素对的谓词排列,没有两个不同的元素能够拥有相同的次序
注:
- 集合(set)默认按小于号排序(升序) set<int> st; ó set<int, less<int> > st;
使用降序排列 set<int, greater<int> >
greater, less需要包含 #include<functional> 头文件
所以涉及到重载运算符 < 的问题
- 将字符串存入集合,要使用C++ string类,不能使用char* 字符串 set<string> st;
- 定义集合时也可以采用如下方式:
int a[10]={2,3,4,5,6};
set<int> st(a,a+10);
set的各成员函数用法(Usage):
迭代器成员函数(Iterators)
begin()–返回指向第一个元素的迭代器
//输出时需要cout << *(st.begin()) << endl;
end()–返回指向最后一个元素后面的迭代器
//如果想输出最后一个元素,要使用cout << *(–st.end()) << endl;
find(…)–返回一个指向被查找到元素的迭代器 ——等价于count(…)
元素检索:若找到,返回该键值迭代器的位置,否则,返回最后一个元素后面一个位置。
set<int> s;
set<int>::iterator it;
it = s.find(5); //查找键值为5的元素
if (it != s.end()) cout << *it << endl; //找到
else cout << “未找到”; //未找到
::iterator — 迭代器变量
for(set<int>::iterator it=st.begin(); it!=st.end(); it++) cout<<*it;
::reverse_iterator — 反向迭代器变量
for (set<string>::reverse_iterator it=st.rbegin(); it != st.rend(); it++)
cout << *it;
或写作: set<int>::reverse_iterator rit;
for(rit=s.rbegin();rit!=s.rend();rit++) cout << *rit;
rbegin()–返回指向集合中最后一个元素的反向迭代器
rend()–返回指向集合中第一个元素的反向迭代器
upper_bound(…)–返回大于某个值元素的迭代器
//有超范围的可能,即指向st.end()
lower_bound(…)–返回指向大于(或等于)某值的第一个元素的迭代器
//有超范围的可能,即指向st.end()
swap()–交换两个集合变量 用法:set<int>s1,s2; s1.swap(s2);
元素操作成员函数
insert()–在集合中插入元素
clear()–清除所有元素
count(…)–返回某个值元素的个数 ——等价于find(…)
//集合中一个元素最多出现一次,所以它的返回值只有0和1
empty()–如果集合为空,返回true
erase(…)–删除集合中的元素
size()–集合中元素的数目
没有什么用的成员函数
equal_range()–返回集合中与给定值相等的上下限的两个迭代
get_allocator()–返回集合的分配器
key_comp()–返回一个用于元素间值比较的函数
value_comp()–返回一个用于比较元素间的值的函数
max_size()–返回集合能容纳的元素的最大限值
求集合的并、交、差、对称差
本代码中使用的std::copy, ostream_iterator左右是输出集合,等价于用迭代器*it循环输出
#include <iostream>
#include <iterator>
#include <set>
#include <algorithm>
using namespace std;
int main()
{
set<int> eg1;
eg1.insert(1); eg1.insert(100); eg1.insert(10); eg1.insert(9);
//遍历set,可以发现元素是有序的
set<int>::iterator set_iter = eg1.begin();
cout << “Set named eg1:” << endl;
for (; set_iter != eg1.end(); set_iter++) cout << *set_iter << ” “;
cout << endl;
set<int> eg2;
for (int i = 6; i < 15; i++) eg2.insert(i);
cout << “Set named eg2:” << endl;
for (set_iter = eg2.begin(); set_iter != eg2.end(); set_iter++) cout << *set_iter << ” “;
cout << endl;
//获得两个set的并
set<int> eg3;
set_union(eg1.begin(), eg1.end(),
eg2.begin(), eg2.end(),
insert_iterator<set<int> >(eg3, eg3.begin())
); //注意第五个参数的形式
copy(eg3.begin(), eg3.end(), ostream_iterator<int>(cout, ” “)); cout << endl;
//获得两个set的交,注意进行集合操作之前要调用clear()函数清空一下集合
eg3.clear();
set_intersection(eg1.begin(), eg1.end(),
eg2.begin(), eg2.end(),
insert_iterator<set<int> >(eg3, eg3.begin())
);
copy(eg3.begin(), eg3.end(), ostream_iterator<int>(cout, ” “)); cout << endl;
//获得两个set的差 A-B
eg3.clear();
set_difference(eg1.begin(),eg1.end(),
eg2.begin(), eg2.end(),
insert_iterator<set<int> >(eg3, eg3.begin())
);
copy(eg3.begin(), eg3.end(), ostream_iterator<int>(cout, ” “)); cout << endl;
//获得两个set的对称差,也就是假设两个集合分别为A和B那么对称差为AUB-A∩B
eg3.clear();
set_symmetric_difference(eg1.begin(), eg1.end(),
eg2.begin(), eg2.end(),
insert_iterator<set<int> >(eg3, eg3.begin()));
copy(eg3.begin(), eg3.end(), ostream_iterator<int>(cout, ” “)); cout << endl;
return 0;
}
二.映射(map) 头文件<map>
定义:
它是由{键,值}对组成的集合,
提供一对一(第一个称为关键字,第二个称为该关键字的值)的数据处理能力,
由于这个特性,在我们处理一对一数据的时候,它可以在编程上提供快速通道。
这里说下map内部数据的组织,map内部自建一颗红黑树(一种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,
所以在map内部所有的数据都是有序的,后边我们会见识到有序的好处。
注:
- map的内部是按键{key}升序排列的。
- 每个关键字{key}只能在map中出现一次。
- map中的元素其实就是一个pair。
- map的键不能是指针,比如int*,char*之类的, 会出错。常用的就用string了,int也行。
- 键本身是不能被修改的,除非删除。
- 在for循环迭代期间是不能删除元素的(只能用While循环删除)。
e.g. map<char,int>::iterator it=st.begin();
while(it!=st.end())
{
if (it->second > 5) it++;
else st.erase(it++);
}
- 可以直接进行赋值和比较: =, >, >=, <, <=, != 等等
e.g. if (mp[“a”] > mp[“b”]) {…};
用法(Usage):
- 定义
(1) map<string, int> mp;
(2) typedef map<string, int> MP; //用typedef定义
MP mp;
- 插入数据
(1) mp[“a”] = 1;
(2) mp.insert(map<string, int>::value_type(“b”,2));
(3) mp.insert(pair<string,int>(“c”,3));
(4) mp.insert(make_pair<string,int>(“d”,4));
- 查找数据和修改数据
(1) int i = mp[“a”]; //查找
mp[“a”] = 5; //修改
(2) MP::iterator Itr; //迭代器变量
Itr = mp.find(“b”);
int j = Itr->second; //查找
Itr->second = 4; //修改
不过注意,键本身是不能被修改的,除非删除。
- 删除数据
(1) mp.erase(Itr);
(2) mp.erase(“c”);
还是注意,(1)在for循环迭代期间是不能删除元素的(只能用while循环删除)。
- 迭代数据
for (Itr=mp.begin(); Itr!=mp.end(); ++Itr) {}
- 其它方法
mp.size() 返回元素数目
mp.empty() 判断是否为空
mp.clear() 清空所有元素
- map中的值{value}可以直接进行赋值和比较:=, >, >=, <, <=, != 等等
- map和set一样,也有swap, rbegin, rend, upper_bound, lower_bound等成员函数,不过没有什么用,就不介绍了。
三.堆栈(stack) 头文件<stack>
定义:
一个先进后出的数据结构(FILO)
用法(Usage):
stack<int> st; //定义一个stack
st.push(a); //a为元素,将a放入栈中
st.top(); //读取栈顶元素
st.pop(); //弹出栈顶元素
st.empty(); //判断栈是否为空bool型true为空
st.size(); //栈内还有多少个元素
注:
在使用.top()和.pop()时应注意栈是否为空。
while (!st.empty()) st.pop();
四.队列(queue) 头文件<queue>
定义:
一个先进先出的数据结构(FIFO)
用法(Usage):
queue<int> qu; //定义一个queue
qu.push(a); //a为元素,将a放入队列中
qu.front(); //读取队首元素
qu.back(); //读取队尾元素
qu.pop(); //弹出队尾元素
qu.empty(); //判断队列是否为空bool型true为空
qu.size(); //队列内还有多少个元素
注:
在使用.front()和.back()和.pop()时应注意队列是否为空。
while (!qu.empty()) qu.pop();
五.优先队列(priority_queue) 头文件<queue>
注:
- 默认输出时按降序排列,即堆顶(top)永远是最大元素
可以用greater改变顺序,使堆顶为最小元素 priority_queue<int,vector<int>, greater<int> > qu;
其中,第二个参数为容器类型,第三个参数为比较函数。
注意加载 <functional> 头文件
- 在使用.top()和.pop()时应注意队列是否为空。
while (!qu.empty()) qu.pop();
用法(Usage):
priority_queue<int> qu; //定义一个优先队列
qu.push(a); //a为元素,将a放入队列中
qu.top(); //读取队顶元素
qu.pop(); //弹出队顶元素
qu.empty(); //判断队列是否为空bool型true为空
qu.size(); //队列内还有多少个元素
注:重载运算符的问题
它可以这么写:
struct node { int priority, value; };
bool operator< (node n1, node n2) { return n1.priority < n2.priority; } |
可以这么写:
struct node{ bool operator< (node n2) const { return prio_ < n2.prio_; } int prio_, value; }; |
还可以这么写:
struct node{ friend bool operator< (node n1, node n2) { return n1.priority < n2.priority; } int priority, value; }; |
六.双端队列(deque) 头文件<queue>或<deque>
定义:
基本上与向量相同,唯一的不同是,其在序列头部插入和删除操作也具有常量时间复杂度。在队列的首端和尾端都可以进行插入和删除操作。
用法(Usage):
deque<int> de; //定义一个queue
成员函数:
de.clear(); | de.empty(); | de.size(); | |
::iterator | ::reverse_iterator | ||
de.begin(); | de.end(); | de.rbegin(); | de.rend(); |
de.front(); | de.push_front(); | de.pop_front(); | |
de.back(); | de.push_back(); | de.pop_back(); |
注:
- 在使用各种成员函数时应注意队列是否为空。
- 在使用.clear函数之后,队列内的数据不会被完全清空,front端的数据依旧存在。
用de.front()函数和de.pop_front()函数时,还可以正常的读取和弹出(pop)。
所以,使用deque时要注意,多调试,防止出bug!!!
七.数对(pair) (头文件<utiliy>)
注:
- 此头文件可以不包含,因为在algorithm,iostream头文件使用std命名空间时已经声明过了pair类。
- pair 可以用于子函数,当需要输出返回一对数时,就可以return pair类型的数对
用法(Usage):
- 定义变量
pair<int,int> p; // 组成pair的两个变量可以是任意类型的
pair<double,int> p; // 如,int,double,string
- 赋值
(1) pair<int,int> ll(5,3);
(2) pair<int,int> ll=make_pair(5,3);
(3) pair<int,int> ll;
ll=make_pair(5,3);
(4) pair<int,int> ll;
ll.first=5;ll.second=3;
- 用于子函数
pair<int, int> lo(int x,int y)
{
return make_pair(x*y,2*y);
}
- 想要输出它
p.first p.second
八.向量(vector) 头文件<vector>
定义:
它相当于一个动态的数组,当程序员无法知道自己需要的数组的规模多大时,用其来解决问题可以达到最大节约空间的目的.
用法(Usage):
vector <int> vt; //定义一个vector (相当于声明了一个int数组a[],大小没有指定,可以动态的向里面添加删除)
vector <int *> vt; //声明一个二维数组,只要声明一个地址的向量即可
vt.clear() //移除容器中所有数据
vt.empty() //判断容器是否为空
vt.erase(pos) //删除pos位置的数据
vt.erase(beg,end) //删除[beg,end)区间的数据
vt.front() //传回第一个数据
vt.insert(pos,elem) //在pos位置插入一个elem拷贝
vt.pop_back() //删除最后一个数据
vt.push_back(elem) //在尾部加入一个数据
vt.resize(num) //重新设置该容器的大小
vt.size() //回容器中实际数据的个数
vt.begin() //返回指向容器第一个元素的迭代器
vt.end() //返回指向容器最后一个元素的迭代器
插入数据与读取数据:
vt.push_back(5)
vt.push_back(8)
vt.push_back(12)
int a = vt[0], b = vt[1], c = vt[2]; //a=5, b=8, c=12
九.istringstream 头文件<sstream>
用途(Usage):
目前似乎只是分割字符串用的,把带空格的字符串按空格分割成小的字符串(即单词),用于拆分单词排序呀,词典呀之类的
示例代码:
#include<iostream>
#include<sstream> //istringstream必须包含这个头文件
#include<string>
#include<stdio.h>
using namespace std;
int main()
{
string str;
char s[505];
//读入字符串,方案一,用gets读入,然后把char*转化为string类!!!
gets(s);
str=s;
//方案二,用std::getline读入,但要注意cin读入的速度问题!!!
getline(cin,str);
istringstream flag(str);
string word;
while(flag>>word)
{
cout<<word<<endl;
}
}
Sample Input:
There is an apple.
Sample Output:
There
is
an
apple.
十.stringstream 头文件<sstream>
用途(Usage):
多用于字符串和数的类型转换,其中字符串可以用string和字符串数组,但注意,输入字符串时都可以,输出时字符串数组只能用char*,不能用char[]。因为缓冲区输出的是const char *类型。 (这句话先忽略,不知道怎么写上去的,似乎可以用char[]数组呀。)
示例代码:
#include <sstream>
#include <iostream>
using namespace std;
int main()
{
stringstream stream;
int first, second;
stream<< “456”; //插入字符串
stream >> first; //转换成int
cout << first << endl;
stream.clear(); //在进行多次转换前,必须清除stream
stream << true; //插入bool值
stream >> second; //提取出int
cout << second << endl;
}
Sample Input:
无
Sample Output:
456
1
注:
- 关于clear()清空缓冲区,实际上,如果读入的内容中包含\n或者endl,就已经更新缓冲区了。
- 缓冲区可以保存很多组数据。PS:但是不知道读取存入缓冲区的耗时情况如何L
e.g.
stream << 123 << “\n” << 456 << endl << “s”;
while(stream >> second) cout<<second<<endl;
Sample Output:
123
456
s
十一.关于类型转换
注:
- 可以使用atoi()函数,但不能使用itoa()函数
- 可以使用stream流来进行类型转换
- (慎用,可能会出bug)也可以使用sprintf()函数进行转换
用法(Usage):
- 数转字符串
int转char[],可以在主函数里直接写,也可以char*类型子函数,然后再strcpy复制为char[]数组。 | |
string itos(int n)
{ string sResult; stringstream stream; stream << n; stream >> sResult; return sResult; } |
string itos(int n)
{ stringstream stream; stream << n; return stream.str(); } |
char s[20]; double ll;
sprintf(s,”%.2f”,ll); |
- 字符串转数
char s[20];
i=atoi(s); t=atof(s); |
|
int stoi(const char* s)
{ stringstream stream; int Result; stream << s; stream >> Result; return Result; } |
double stof(const char* s)
{ stringstream stream; double Result; stream << s; stream >> Result; return Result; } |
注:1. const char* 中const可省略;
2. const char* 可改为string。 |
P.S.:关于string
ss.c_str()输出为char*类型
通过strcpy(s,ss.c_str());转换为char[]类型字符串
或者直接printf输出
十二.sort 头文件<algorithm>
注:
对于自定义(字符串之类的)排序, 可以使用cmp函数
对于结构体排序,可以使用重载运算符或者cmp函数
重载运算符(有3种方式)见Page 8,优先队列部分。
(同样,后续再补充)
发表评论