• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

关于C++标准模板库(STL)的一些基本使用

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

vector

vector可以理解成变长数组,即长度根据需要而自动改变的数组

  • 头文件:#include <vector>
  • 定义:vector<typename>name;
  • vector内可以通过下标或者迭代器(iterator)访问(只有vector和string才允许使用v.begin()+3这种迭代器加整数的写法)
  • v.push_back(value) 时间复杂度:$O(1)$
  • v.pop_back() 时间复杂度:$O(1)$
  • v.size() 返回的是unsigned类型 时间复杂度:$O(1)$
  • v.clear() 时间复杂度:$O(N)$ $N$是vector中元素的个数
  • v.insert(it,value) 时间复杂度:$O(N)$
  • v.erase(it) 时间复杂度:$O(N)$
  • v.erase(first,last) 即删除[first,last)内元素 时间复杂度:$O(N)$

 

set

set可以理解成集合,一个内部自动有序且不含重复元素的容器

  • 头文件:#include <set>
  • 定义:set<typename>name;
  • set只能通过迭代器访问
  • s.insert(value) 时间复杂度:$O(logN)$ $N$为set内元素个数
  • s.find(value) 时间复杂度:$O(logN)$ $N$为set内元素个数
  • s.erase(it) 时间复杂度:$O(1)$
  • s.erase(value) 时间复杂度:$O(logN)$
  • s.erase(first,last) 时间复杂度:$O(last-first)$
  • s.size() 时间复杂度:$O(1)$
  • s.clear() 时间复杂度:$O(N)$
  • set中元素是唯一的,如果需要处理不唯一的情况,则需要使用multiset。另外,C++11标准中还增加了unordered_set,以散列代替set内部的红黑树(一种自平衡二叉查找树),使其可以用来处理只去重但不排序的需求,速度比set要快得多。

 

string

string是装载字符串的容器

  • 头文件:#include <string>
  • 定义:string str = "abcd";
  • string可以通过下标和迭代器进行访问
  • 可以使用c_str()将string类型转换为字符数组进行输出 printf("%s\n",str.c_str());
  • cin读入以遇到空格符便结束,getline(cin,str)以换行符为结束标志,因此可以读入空格
  • 使用'+' 可以拼接两个string。使用==,!=,<,<=,>,>=可以对两个string直接按照字典序进行比较
  • str.length() 或者 str.size() 可以返回string的长度 时间复杂度:$O(1)$
  • str.insert(pos,string) 时间复杂度:$O(N)$
  • str.insert(it,it2,it3) it为目的字符串的插入位置迭代器 it2和it3为待插字符串的首尾迭代器[it2,it3) 时间复杂度:$O(N)$
  • str.erase(it) 时间复杂度:$O(N)$
  • str.erase(first,last) 时间复杂度:$O(N)$
  • str.erase(pos,length) pos为开始删除的初始位置,length为删除字符的个数 时间复杂度:$O(N)$
  • str.clear() 时间复杂度:$O(1)$
  • str.substr(pos,len) 返回从pos开始,长度为len的子串 时间复杂度:$O(len)$
  • string::npos 这是一个常数,本身的值为-1,但由于是unsigned_int类型,因此也可以认为是unsigned_int类型最大值即4294967295。string::npos用作find()失配时的返回值。
  • str.find(str2) 返回str2在str中第一次出现的位置 或者 返回 string::npos 时间复杂度:$O(nm)$ 其中n和m分别为str和str2的长度
  • str.find(str2,pos) 从str的pos位开始匹配 同str.find(str2) 时间复杂度:$O(nm)$
  • str.replace(pos,len,str2) 把str从pos号位开始、长度为len的子串替换为str2 时间复杂度:$O(str.length())$
  • str.replace(it1,it2,str2) 把str[it1,it2)范围的子串替换为str2 时间复杂度:$O(str.length())$

 

map

map可以将任何基本数据类型(包括STL容器)映射到任何基本类型(包括STL容器),但若要表示字符串的话只能用string,而不能用char数组。

  • 头文件:#include <map>
  • 定义:map<typename1,typename2> m; typename1称为键 typename2称为值
  • map会按键的大小顺序自动排序,这是因为map内部是以红黑树实现的
  • m.find(key) 返回键为key的映射的迭代器,时间复杂度:$O(logN)$ N是map中映射的个数
  • m.erase(it) 时间复杂度:$O(1)$
  • m.erase(key) 时间复杂度:$O(logN)$ N是map中映射的个数
  • m.erase(first,last) 时间复杂度:$O(last-first)$
  • m.size() 时间复杂度:$O(1)$
  • m.clear() 时间复杂度:$O(N)$ N是map中元素的个数
  • mup的键和值是唯一的,如果一个键需要对应多个值,可以使用multimap。另外C++11标准中增加了unordered_map,以散列代替内部的红黑树实现,使其可以用来处理只映射而不按key排序的需求,速度比map要快得多

 

queue

queue实现了一个FIFO(先进先出)的容器

  • 头文件:#include <queue>
  • 定义:queue<typename> q;
  • queue中只能通过 q.front()来访问队首元素,q.back()来访问队尾元素 时间复杂度均为:$O(1)$
  • q.push(value) 时间复杂度:$O(1)$
  • q.pop() 时间复杂度:$O(1)$
  • q.empty() 时间复杂度:$O(1)$
  • q.size() 时间复杂度:$O(1)$
  • 使用q.front() 和 q.pop() 之前必须用q.empty()判断queue是否为空

 

priority_queue

priority_queue指优先队列,原理是用堆实现。在优先队列中,队首元素一定是优先级最高那个,然后这个优先级可以自己定义。

  • 头文件:#include <queue>
  • 定义:priority_queue<typename> pq;
  • priority_queue只能通过pq.top()来访问队首元素,之前要用pq.empty()进行判断 时间复杂度:$O(1)$
  • pq.push(value) 时间复杂度:$O(logN)$ N是当前队列里的元素个数
  • pq.pop() 记得之前要用pq.empty()进行判断 时间复杂度:$O(logN)$
  • pq.empty() 时间复杂度:$O(1)$
  • pq.size() 时间复杂度:$O(1)$
  • 当优先队列里面的元素为基本数据类型(int,double,char等等)时,默认是数字或字典序越大优先级越高所以越排在前面,而且以下两种定义是等价的:priority_queue<int> pq  以及 priority_queue<int,vector<int>,less<int> > pq,可以发现第二种定义方法多了两个参数,vector<int>是用来承载底层数据结构堆(heap)的容器,vector的数据类型与优先队列的保持一致,less<int>则是对第一个参数的比较类,less<int>表示数字越大优先级越大,相反,greater<int>表示数字越小优先级越大。
  • 然后讲如果数据类型是一个结构体的时候怎样设置优先级,当然当前类型即使是基本数据类型也可以使用这种方法,只不过第三个参数的写法不一样了。

 

struct fiuit
{
    string name;
    int price;
    friend bool operator < (fruit f1,fruit f2)
    {
        return f1.price < f2.price;
    }
};

 

 

 

现在希望按水果的价格高的为优先级高,那么就需要重载小于号"<",注意重载大于号会编译错误,因为从数学上来说只需要重载小于号,即$f1>f2$等价于判断$f2<f1$,而$f1==f2$等价于判断$!(f1<f2)\&\&!(f2<f1)$,函数内为return f1.price < f2.price ,因此重载后小于号还是小于号的作用。此时就可以直接定义fruit类型的优先队列:priority_queue<fruit> pq 其内部就是以价格高的水果为优先级高。相反,如果想以价格低的水果为优先级高,只要把return中的<改为>即可。没错,他们效果看上去与直觉相违背,不过语法上就是这样写的。我们可以理解成优先队列默认优先级高的在队首,那么假若我们把<改为>,则相当于把规则翻转了,那么原先大值优先也自然变成了小值优先。
还有一种方法是把重载的函数放在结构体外面:

 

struct cmp
{
    bool operator () (fruit f1,fuit f2)
    {
        return f1.price < f2.price;
    }
};

 

 

可以看到我们去掉了friend(友元),然后把<改为了一对小括号,记得要用struct把所有包起来。
还有在这个时候我们就不能写priority_queue<fruit> pq 来定义优先队列了,要改为priority_queue<fruit,vector<fruit>,cmp > pq 可以看到这跟上面基本元素的定义方法其实是可以差不多的。哪怕数据类型是其他STL容器也可以用这种重载符号的方法来使用priority_queue。
最后,如果结构体内的数据较大(使用了字符串或者很大的数组),我们可以使用“引用”来提高效率,即加上const和&,如下:

 

friend bool operator < (const fruit &f1,const fruit &f2)
{
    return f1.price < f2.price;
}

// 两种重载方法 

bool operator () (const fruit &f1,const fruit &f2)
{
    return f1.price < f2.price;
}

 

 

 

stack

stack是一个实现LIFO(后进先出)的容器。

  • 头文件:#include <stack>
  • 定义:stack<typename> s
  • stack中只能通过s.top()来访问栈顶元素 时间复杂度:$O(1)$ 注意先用s.empty()检测是否栈为空
  • s.push(value) 时间复杂度:$O(1)$
  • s.pop() 时间复杂度:$O(1)$
  • s.empty() 时间复杂度:$O(1)$
  • s.size() 时间复杂度:$O(1)$

 

pair

pair相当于一个内部有两个可以自定类型的元素的结构体(而不是真的需要用struct去实现,pair使这看起来更优美)。

  • 头文件:#include <utility> 值得注意的是map头文件包含utility头文件,记不住可以用map头文件代替,这也说明了map的内部实现用到了pair
  • 定义:pair<typename1,typename2> p  也可以同时进行初始化:pair<string,int> p("hello",5);
    如果想临时构建一个pair有两种方法:pair<string,int>("hello",5) 或者使用自带的make_pair("hello",5)
  • 关于pair中元素的访问跟结构体差不多,p.first 和 p.second
  • 两个pair类型数据可以直接用==、!=、<、<=、>、>=比较大小,规则是先比较first的大小,只有当first相等的时候才会去比较second的大小
  • pair常用来作为map的键值对数据

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
syslog.c2发布时间:2022-07-14
下一篇:
(一)s3c2440地址分配讲解(很难很纠结)发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap