C++ STL库函数

  • 2018-03-30
  • 481
  • 0

p.s. 此文章为word直接复制粘贴生成,未对格式进行修正,请周知!

word版本下载请见:https://download.csdn.net/download/zjw1111/9979516

 


一.集合(set)    头文件<set>

定义:

由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种作用于元素对的谓词排列,没有两个不同的元素能够拥有相同的次序

 

注:

  1. 集合(set)默认按小于号排序(升序) set<int> st; ó set<int, less<int> > st;

使用降序排列 set<int, greater<int> >

greater, less需要包含  #include<functional>  头文件

所以涉及到重载运算符 < 的问题

  1. 将字符串存入集合,要使用C++ string类,不能使用char* 字符串 set<string> st;
  2. 定义集合时也可以采用如下方式:

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内部所有的数据都是有序的,后边我们会见识到有序的好处。

 

注:

  1. map的内部是按键{key}升序排列的。
  2. 每个关键字{key}只能在map中出现一次。
  3. map中的元素其实就是一个pair。
  4. map的键不能是指针,比如int*,char*之类的, 会出错。常用的就用string了,int也行。
  5. 键本身是不能被修改的,除非删除。
  6. 在for循环迭代期间是不能删除元素的(只能用While循环删除)。

e.g.    map<char,int>::iterator it=st.begin();

while(it!=st.end())

{

if (it->second > 5) it++;

else  st.erase(it++);

}

  1. 可以直接进行赋值和比较: =, >,  >=,  <,  <=,  != 等等

e.g.  if (mp[“a”] > mp[“b”]) {…};

 

用法(Usage):

  1. 定义

(1)   map<string, int>  mp;

(2)   typedef  map<string, int>  MP;   //用typedef定义

MP  mp;

 

  1. 插入数据

(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. 查找数据和修改数据

(1)   int  i = mp[“a”]; //查找

mp[“a”] = 5;     //修改

(2)   MP::iterator  Itr;   //迭代器变量

Itr = mp.find(“b”);

int  j = Itr->second;      //查找

Itr->second = 4;        //修改

  不过注意,键本身是不能被修改的,除非删除。 

 

  1. 删除数据

(1)   mp.erase(Itr);

(2)   mp.erase(“c”);

还是注意,(1)在for循环迭代期间是不能删除元素的(只能用while循环删除)。

 

  1. 迭代数据

for (Itr=mp.begin(); Itr!=mp.end(); ++Itr) {}

 

  1. 其它方法

mp.size()      返回元素数目

mp.empty()           判断是否为空

mp.clear()     清空所有元素

 

  1. map中的值{value}可以直接进行赋值和比较:=,   >,   >=,   <,   <=,   !=   等等

 

  1. 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>

 

注:

  1. 默认输出时按降序排列,即堆顶(top)永远是最大元素

可以用greater改变顺序,使堆顶为最小元素 priority_queue<int,vector<int>, greater<int> > qu;

其中,第二个参数为容器类型,第三个参数为比较函数。

注意加载 <functional> 头文件

  1. 在使用.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();

 

注:

  1. 在使用各种成员函数时应注意队列是否为空。
  2. 在使用.clear函数之后,队列内的数据不会被完全清空,front端的数据依旧存在。

用de.front()函数和de.pop_front()函数时,还可以正常的读取和弹出(pop)。

所以,使用deque时要注意,多调试,防止出bug!!!

 

 

 

 

 

 

七.数对(pair)   (头文件<utiliy>)

 

注:

  1. 此头文件可以不包含,因为在algorithm,iostream头文件使用std命名空间时已经声明过了pair类。
  2. pair 可以用于子函数,当需要输出返回一对数时,就可以return pair类型的数对

 

用法(Usage):

  1. 定义变量

pair<int,int> p;   // 组成pair的两个变量可以是任意类型的

pair<double,int> p; // 如,int,double,string

  1. 赋值

(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;

 

  1. 用于子函数

pair<int, int> lo(int x,int y)

{

return make_pair(x*y,2*y);

}

  1. 想要输出它

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

 

注:

  1. 关于clear()清空缓冲区,实际上,如果读入的内容中包含\n或者endl,就已经更新缓冲区了。
  2. 缓冲区可以保存很多组数据。PS:但是不知道读取存入缓冲区的耗时情况如何L

e.g.

stream << 123 << “\n” << 456 << endl << “s”;

while(stream >> second)  cout<<second<<endl;

Sample Output:

123

456

s

十一.关于类型转换

 

注:

  1. 可以使用atoi()函数,但不能使用itoa()函数
  2. 可以使用stream流来进行类型转换
  3. (慎用,可能会出bug)也可以使用sprintf()函数进行转换

 

用法(Usage):

  1. 数转字符串
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);

 

  1. 字符串转数
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,优先队列部分。

 

(同样,后续再补充)

评论

还没有任何评论,你来说两句吧

发表评论