从零开始_学_数据结构(五)——STL(map、set、list、vector)

STL容器

 

前注:

STL(标准模板库)是一个C++的软件库,也是C++标准程序库的一部分。

这些容器,应该都是STL里面的一个类。

vector封装数组、list封装链表、map和set封装二叉树

 

一、list

在不懂的时候,list可以理解为双向链表(很像,但事实上不是)。

(1)声明一个list对象:

①包含头文件list:#include<list>

②声明他:std::list<int> one;
//声明一个list对象

③需要注意,list位于std名称空间之中,因此如果使用using namespace std,可以省略std::

(2)使用
迭代器

①迭代器,在不懂的时候,可以理解为指针,指向对象。但事实上,迭代器不是指针(例如,指针可以加一个int值,但迭代器是不可以的)。

②声明一个list类迭代器:std::list<int>::iterator pr = one.begin();
//一个迭代器,用于指向one的第一个对象

③迭代器可以使用++和--
这样的形式;

pr++;

pr--;

++pr;

--pr;

效果是:++(指向list对象内的下一项),--(指向上一个项);

Note:假如当前迭代器已经指向最后或最初,则不能超出界限,否则会出错(例如最后时不能+,第一个时不能-)

④利用迭代器插入一个成员(有疑问)。

int a = 1;

one.insert(pr, a);

//注意,根据观察,每添加一个对象,迭代器便会自动指向下一个位置。

 

⑤查询当前容器里有多少个项目:

cout << one.size();

⑥删除一个成员

 

更多的使用,参考链接:

http://www.cppblog.com/Lee7/archive/2008/04/14/47036.html

成员函数概观[编辑]

· 迭代
(Iterator)

· list.begin() 回传指向第一个元素的
Iterator。

· list.end() 回传指向最末元素的下一个位置的
Iterator。

· list.rbegin() 回传指向最末个元素的反向
Iterator。

· list.rend() 回传指向第一个元素的前一个位置的反向
Iterator。

· Capacity/Size:

· list.empty() 若list内部为空,则回传true值。

· list.size() 回传list内实际的元素个数。

· list.resize() 重新分派list的长度。

· 存取元素的方法

· list.front() 存取第一个元素。

· list.back() 存取最末个元素。

· Modify methods

· list.push_front() 增加一个新的元素在
list 的前端。

· list.pop_front() 删除
list 的第一个元素。

· list.push_back() 增加一个新的元素在
list 的尾端。

· list.pop_back() 删除
list 的最末个元素。

· list.insert() -
插入一个或多个元素至 list内的任意位置。

· list.erase() -
删除 list中一个或多个元素。

· list.clear() -
清空所有元素。

· 重新配置/重设长度

· list.reserve() -
如有必要,可改变 list的容量大小(配置更多的内存)。

· list.resize() -
改变 list目前持有的元素个数。

 

 

二、map

如代码:

#include<map>

map<char*,
int> MAP;
//声明一个map

MAP["first"] = 1;
//first是关键字key,1是值。值和key是成对出现的。可以把first理解为下标,只不过和平常的int下标不同

MAP["second"] = 2;

MAP["qqq"] = 3;

map<char*,
int>::iterator pr = MAP.begin();
//迭代器指向开始(first)

pr++;
//迭代器指向下一个

cout << pr->first
<< " : ";
//输出key值,注意不要括号

cout << pr->second
<< endl;
//输出值(在这里就是int值)

MAP.erase(pr++);
//删除当前迭代器指向的元素,需要使用pr++,如果在这行之后使用的话,迭代器会无法使用(除非重新赋值)

cout << pr->first
<< " : ";
//此时迭代器指向的原本的第三个(当前的第二个)

cout << pr->second
<< endl;

pr--;
//此时迭代器指向原本的第一个(当前第一个),原本第二个被删除了

MAP.insert(pr,{ "ww",4 });
//插入一个(插入位置是最后,第三个),当目前迭代器还指向的是第一个

pr++;

pr++;
//

cout << pr->first
<< " : ";
//此时迭代器指向的原本的第三个(当前的第二个)

cout << pr->second
<< endl;

 

 

 

三、vector

如代码:

#include<vector>

vector<int>abc(10);
//类型为int,数量为10

abc[1] = 1;
//第二个元素赋值为1

cout << abc[1] << endl;
//输出第二个元素

vector<int>::iterator pr = abc.begin();
//迭代器指向第一个元素

pr++;

cout << *pr
<< endl;
//输出该元素的值

cout << abc.size()
<< endl; //数组元素数量

abc.front(); //数组第一个元素的引用

abc.back(); //数组最后一个元素的引用

 

 

其他用法:

https://zh.wikipedia.org/wiki/Vector_(STL)

成员函数概观[编辑]

vector 类是以容器(Container) 模式为基准设计的,也就是说,基本上它有 begin(),end(),size(),max_size(),empty() 以及 swap() 这几个方法。

· 访问元素的方法

· vec[i] - 访问索引值为 i 的元素引用。 (索引值从零起算,故第一个元素是vec[0]。)

· vec.at(i) - 访问索引值为 i 的元素的引用,以 at() 访问会做数组边界检查,如果访问越界将会抛出一个例外,这是与operator[]的唯一差异。

· vec.front() - 回传 vector 第一个元素的引用。

· vec.back() - 回传 vector 最尾元素的引用。

· 新增或移除元素的方法

· vec.push_back() - 新增元素至 vector 的尾端,必要时会进行内存配置。

· vec.pop_back() - 删除 vector 最尾端的元素。

· vec.insert() - 插入一个或多个元素至 vector 内的任意位置。

· vec.erase() - 删除 vector 中一个或多个元素。

· vec.clear() - 清空所有元素。

· 获取长度/容量

· vec.size() - 获取 vector 目前持有的元素个数。

· vec.empty() - 如果 vector 内部为空,则传回 true 值。

· vec.capacity() - 获取 vector 目前可容纳的最大元素个数。这个方法与内存的配置有关,它通常只会增加,不会因为元素被删减而随之减少。

· 重新配置/重置长度

· vec.reserve() - 如有必要,可改变 vector 的容量大小(配置更多的内存)。在众多的 STL 实做,容量只能增加,不可以减少。

· vec.resize() - 改变 vector 目前持有的元素个数。

· 迭代 (Iterator)

· vec.begin() - 回传一个Iterator,它指向 vector 第一个元素。

· vec.end() - 回传一个Iterator,它指向 vector 最尾端元素的下一个位置(请注意:它不是最末元素)。

· vec.rbegin() - 回传一个反向Iterator,它指向 vector 最尾端元素的。

· vec.rend() - 回传一个Iterator,它指向 vector 的第一个元素。

 

 

 

四、set

(1)set以结点的方式来存储。

(2)插入和删除之后,iterator可能失效。

(3)set中使用二分查找法,效率是f(n)=log n;

(4)常用代码:

#include<set>

set<int>abc;
//声明一个set对象

abc.insert(1); //插入一个

abc.insert(100); //再插入一个

abc.insert(50); //插入第三个

set<int>::iterator pr = abc.begin();
//迭代器指向第一个

pr++;
//指向下一个,注意,不是插入的第二个(100),而是值从小到大的第二个50

cout << *pr
<< endl;
//输出50

cout << abc.size()
<< endl; //abc总共的元素个数

cout << abc.count(50)
<< endl; //输出值50在整个abc里面出现的次数

cout << abc.max_size()
<< endl; //abc的最大能容纳的个数(很多很多),大概是INT_MAX的1/10

 

 

 

 

时间: 2024-02-19 06:46:35

从零开始_学_数据结构(五)——STL(map、set、list、vector)的相关文章

从零开始_学_数据结构(一)——算法的基本概念

从零开始_学_数据结构(一)--算法   算法的定义: 解决问题的方法. 对于同一个问题,一个好的算法比一个差的算法,效率更高,更节约资源.   For Computer:算法是解决特定问题的求解步骤的描述,在计算机中,表示指令的有限序列,每条指令表示一个或者多个操作. 简单来说,算法就是输入代码,告诉计算机,你应该怎么解决这个问题.     算法的特性: (1)输入和输出.        光算出结果但不输出结果,跟没算没区别:要计算,总得有数据,不然没法计算. (2)有穷性:        能

从零开始_学_数据结构(三)——树的初步应用

(三) 树常用的基本方法: ①构建一个空树: ②销毁一个树: ③按给的树的定义,来构造一个树(不懂,不太明白这个如何给): ④若树存在,将树清为一个空树: ⑤若T为空树,返回true,否则返回false: ⑥返回树的深度: ⑦返回树的根节点: ⑧某结点cur_e是树T的一个结点,返回此结点的值(应该说的是结点的数据部分的值): ⑨给树T的结点cur_e赋值为value(这个value是我们给的): ⑩若cur_e是树T的非根结点,则返回它的父结点,否则返回空:(原文是双亲,但是树只有一个父结点,

从零开始_学_数据结构(零)——数据结构总述

参考文献:<大话数据结构>作者:程杰   写在最开始: 这是我自己学习的经验和记录,有的内容很容易理解,但又比较重要,我会直接摘抄书上的内容:有些比较复杂,我会写明自己的思考:有些我自己也没搞懂,我会用红色文字标明,写出自己的疑问,也许以后会解决.   数据结构的概念: 是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科. 注:这句话应该意思是,数据结构不是研究数值和数值计算的,而是研究对象(对象不止是数值,也可能是类对象或者其他),研究这些对象之间的关系

从零开始_学_数据结构(二)——树的基本概念

相比之前的帖子,对其进行了增添和完善. ps:本颜色的字体是后续添加内容 ------------------ 参考链接: 大话数据结构.pdf 图解数据结构(6)--树及树的遍历 http://www.cnblogs.com/yc_sunniwell/archive/2010/06/27/1766233.html   1.什么是树? 是一种数据结构,可以用来表示层次关系,因表示的样子很像一颗倒立的树而得名. 在数据结构中的特点,是一对多(链表是一对一,图是多对多)   最上面:树根 中间:树枝

从零开始_学_数据结构(六)——排序(冒泡、插入、希尔、简单选择、归并、快速)

一.冒泡排序: (1)思想是: 从第1个开始,1和2比,2和3比,3和4比,如果前面比后面大,则互相交换之,一直到n-1和n进行比.这是第一轮. 然后第二轮再从第1个开始,2和3比,3和4比,再一直比到n-1和n,比的时候符合条件(前大后小)则交换. 然后一直到从n-1个开始,最后比较一次n-1和n. 因此,时间复杂度是O(n2):   代码: #include<iostream> void maopao() { using namespace std; int n = 100; int m[

从零开始_学_数据结构(四)——查找算法、索引、二叉排序树

查找算法   基本概念: (1)关键字:假如有结构 struct Node //一个结点,存储数据和指针 { DATA data; //数据属性,用于存储数据 int key; //假设key为int值,其在整个表里是唯一的 //指针域,具体略,指向其他结点,或者是数组的下标 }; key值便是关键字,对于每一个结点而言,其key值都是不一样的(不一定必须是int值).因此,当我们查找数据时,只要知道其key值,然后对比key值和我们要查找的key值是否相同,便能判断是否是我们要查找的数据了.

表达式-数据结构_考试题_求大神帮助

问题描述 数据结构_考试题_求大神帮助 表达式axb+(c-d/e)xf的前缀表达式为什么啊! 大神知道的,帮助一下,万分火急啊 解决方案 有点不记得了,是不是+×ab×-c/def ,你可以参考下其他人的答案. 解决方案二: +*ab*-c/def 解决方案三: 前缀表达式最简单了,相当于改写成函数形式,脱掉括号 比如 a+b 前缀就是add(a, b),对吧,我们把add写作+,脱掉括号就是+ab 再比如 a+b*c 就是 add(a, mul(b, c)) 那么就是 +a*bc 解决方案四

数据结构_考试题_求大神相助

问题描述 数据结构_考试题_求大神相助 主题下载"> 图片说明](http://img.ask.csdn.net/upload/201501/21/1421830891_832514.png) A B c d E f g 试画出上图无向图的邻接表存储结构,并给出以定点A为出发点的深度优先遍历序列和广度优先遍历序列 解决方案 a b c d e f g a - b 1 - c 1 1 - d 0 0 1 - e 0 1 1 0 - f 0 0 0 0 1 - g 0 0 1 0 0 0 深度

从零开始学Xamarin.Forms(五) 技巧

原文:从零开始学Xamarin.Forms(五) 技巧        由于HTML5规范于2014年10月终于定稿,公司.net开发人员较少,国内外已有了较为成熟的UI框架.手机软件硬件的快速发展等等原因,所以我就不打算再使用Xamarin了,而是采用HTML5+CSS3+Javascript的方式来进行跨平台的开发.之前在探索Xamarin中积累了一些小经验也同时分享给大家,希望能给大家带来帮助. 1.TabbedPage中嵌入NavigationPage,NavigationPage中的Ro