主要介绍如下5个容器类——Vector, Stack,Queue,Map和Set,各个都表示一重要的抽象数据类型。另外,各个类都是一些简单类型的值的集合,所以称它们为容器类。

暂且我们先不需要知道它们是如何实现的,我们先来学习一下如何使用它们。

为了能使用这些容器类,必须包含适合的接口,就像包含相应的库一样。如下:

#include "vector.h"

就是包含了Vector类的接口,包含该头文件后,就可以在程序中使用Vector类了。

一、Vector类

Vector类类似于C++中数组,然后,C++中数组有如下的缺点:

  • 数组在定义时指定其大小,后续不能改变。
  • 尽管数组有固定的大小,但是程序员不能获取该大小。结果就是,需要一个额外的变量来跟踪数组中的元素数目。
  • 传统的数组不支持插入和删除元素。
  • C++中数组不能确保你选择的数据一定存在于数组中,例如,当一个数组保存了25个元素,当要选择索引为50的位置的元素时,C++将简单的查看内存位置,若存在则就查看到。

Vector类通过抽象数据类型来重新实现数组概念来解决这些问题,

1.指定Vector的基本类型

如Vector<int>表示一个Vector,其元素是整型。

Vector<char>表示一个Vector,其元素是单个字符

Vecotr<string>表示一个Vector,其元素是字符串。

尖括号里的类型,就表示为指定容器类的基本类型(Base Type)。

这种类中包含指定的基本类型在面向对象社区中称为参数化的类。在C++中,参数化的类另外称为模板(templates)。这反映了C++编译器把Vector<int>,Vector<char>,Vector<string>作为独立的类来共享共同的结构。

2.声明一个Vector对象

抽象数据类型背后的一个哲学原理是让Client认为它们就是内置的原始类型,就像如下声明一个整型变量一样

int n;

声明一个新的Vector变量写为:

Vecotr<int> vec;

在C++中,该声明的新变量vec,表示是一个整型的Vector。

3.Vector操作

1)add操作

当声明一个Vector变量时,其为一个空的Vector,表示它不包含任何元素,由于空的Vector并没有用,因此,首先我知道的是如何向Vector变量中加入元素。常用的方法是调用add方法,该方法是在Vector尾部加入一个新的元素。

例如,若vec是一个空的整型Vector,执行如下加入元素操作:

vec.add(10);

vec.add(20);

vec.add(40);

这样,vec中就包含了10,20,40这3个元素。现在vec看起来如下:

【stanford C++】容器III——Vector类-LMLPHP

跟原始的数组类型不同,Vector类的大小不是固定的,这意味着我们在任何时候加入其它元素。例如,现在我们再加入一个元素:

vec.add(50);

此时,加入50到vec的尾部,如下:

【stanford C++】容器III——Vector类-LMLPHP

2)insertAt方法

该方法允许在一个Vector类的中间位置加入一个元素,insertAt方法的第一个参数为索引号,其表示在该索引号位置前插入一个新元素,例如:

vec.insertAt(2, 30);

表示在位置2之前插入一个值30,执行该语句后,如下:

【stanford C++】容器III——Vector类-LMLPHP

3)removeAt方法

该方法表示从Vector变量中删除一个元素,例如:

vec.removeAt(0);

表示删除位置0处的元素,执行该语句后,如下:

【stanford C++】容器III——Vector类-LMLPHP

4)get方法和set方法

get方法和set方法用来选择和修改各个单独的元素,get方法通过一个索引号获取该索引位置的值。例如,对于上面最近显示的vec变量中的值。调用

vec.get(2)

将返回40。

相应地,可以使用set方法来改变已经存在的元素的值,例如,调用

vec.set(3, 70);

其改变索引位置3的值50为70,如下:

【stanford C++】容器III——Vector类-LMLPHP

get、set、insertAt和removeAt方法都会检查给其提供的索引值必须是有效的。例如,对于上面最近显示的Vector,若调用vec.get(4),则会有调用错误,因为索引值4太大了,因为vector的索引值从0~3。

这种检查索引值的操作是否有效的操作,称之为边界检查。边界检查可以更容易的获取到那些不容易注意的程序错误

4.选择Vector中的元素

尽管get和set方法容易使用,但并不是每个人都调用这些方法。

C++的一个特性是其定义的类可以重载标准操作符的定义。这让Vector类支持更多传统的使用方括号来指定要访问的索引的值的语法。

因此,选择位置i处的元素,可以使用表达式vec[i],就像访问传统的数组一样。

另外,可以通过赋值一个新的值给vec[i]来改变位置i处的值。可以通过如下:

vec[3] = 70;

来设置索引值3的处为70。

最常用的索引表达式之一就是for循环中的索引,其按序循环各个索引值。循环Vector中的索引位置的通常模式如下:

for(int i = 0; i < vec.size(); i++)
{
loop body
}

在循环实体内,可以应用当前的元素vec[i]。

例如,如下的代码把Vec变量中的内容,以方括号括起来,元素之间用逗号隔开来显示

cout << "[";
for(int i = 0; i < vec.size(); i++)
{
if(i > 0) cout << ",";
cout << vec[i];
}
cout << "]" << endl;

执行该段代码的输出结果将如下:

[20,30,40,70]

5.传递Vector对象作为一个参数

对于上面的打印Vector变量中的元素值使用的非常频繁,因此,可以把其定义为一个函数,后面若使用,直接调用该函数即可,那么在定义函数时,就涉及了Vector变量传递给函数参数的问题,一般Vector变量作为函数参数的定义如下:

void printVector(Vector<int> &vec)
{
cout << "[";
for(int i = 0; i < vec.size(); i++)
{
if(i > 0) cout << ",";
cout << vec[i];
}
cout << "]" << endl;
}

&表示此处参数通过引用来调用,

在C++中,引用调用比传值调用更有效,因为传值调用要求复制vector中的每个元素。

在printVector函数中,并没需要进行复制,所以引用调用是一个更加有效的设计。

引用调用的一个更加重要的特性就是可以直接改变Vector变量中的内容,例如,使用如何函数删除元素值为0的项。

void removeZeroElements(Vector<int> &vec){
for(int i = vec.size() - 1; i >= 0; i--)
if(vec[i] == 0)
vec.removeAt(i);
}
}

6.创建一个预先定义大小的Vector

到目前为止的例子,都是创建一个空Vector变量,然后一次加入一个元素到里面。然而,若提前知道要创建的vector变量的大小,则可以在声明时指定元素个数。如下代码:

const int N_HOLES = 18;
Vector<int> golfScores;
for(int i = 0; i < N_HOLES; i++)
{
golfScores.add(0);
}

一个较好的方法是在声明的时候包含一个大小的参数,如下:

Vector<int> golfScores(N_HOLES);

该声明创建一个Vector<int>变量指定大小为N_HOLES个元素,各个元素初始化为0.

04-21 05:00