vector使用指南-创新互联

首先说明vector与string肯定是不一样的，就相当于char arr[3] = {'a','b','c'} 和char* arr = "abc" 一样，前者不用 '\0'结尾，是字符数组，但是后者是字符串，需要'\0'结尾。因此两者之间是有差异的，不能代替。

第二个差异在于大小的比较，vector比较大小就是单纯按照数组字符个数，而string是字符串，按照ASCLL码进行比较，不按长度比较。

第三个差异在于接口上，它们之间的接口也有很大区别，功能的不同，实现上的不同等等。比如对于操作符+=的重载，string有+=，可以直接在字符串后面加字符\字符串，而vector则没有这个接口。

其它的不同更多体现在vector 与 string整体的不同上，后面讲接口的时候会顺带提出。

上面是vector与string的差异，容器本身还有很多异同之处。

string是早期设计的，与后面容器的实现有时代的隔阂，string的接口庞杂繁复，数量是vector的一倍，其实有很多接口是没有什么意义的或者基本不会使用的，但由于向前兼容的特性这些接口都保留了下来。

在insert、erase这些增删接口上面，string与其他容器(如：vector) 的标识也不同，string是使用下标标识位置的，而vector等容器是用迭代器标识位置的 (insert(v.begin()+4,1) )

reserve接口主要是扩容，通过改变capacity的大小达成目的。

接口本身很简单易懂，但既然能改变capacity能扩容，那能不能缩容呢？

————一般来说是不会实现缩容的，因为缩容是有代价的，不是想缩就缩的。

缩容实质上是开一块新空间拷贝数据，是以空间换时间的方式。

缩容需要先开新空间，拷贝数据过去，然后释放旧空间，频繁缩容就会反复开空间、释放和拷贝，会有较大代价所以一般不会缩容。

有人会问：为什么不能直接缩容释放不需要的一块空间给操作系统，要开新空间拷贝数据呢？

————这样当然是不行的，和内存管理机制有关。

类似malloc一块空间是不能分两次free还给操作系统的。

resize接口是个非常重要的接口，主要是改变size，它不改变capacity，有四种情况：

1、没有开空间时，resize开空间+初始化（一般里面元素初始化为0）常用

2、容量不够时，扩容。如capacity为9，resize(20)，此时空间不够会先扩容。

3、容量够时，会从初始size位置填数据直到当前size位置。

4、resize的size值比初始值小时会删除数据，注意不会删除空间！只是删除有效数据！

那么库里面给的接口，参数方面我们似乎看不懂，size_type 和 value_type是什么类型，这是由于库在里面再次typedef了这些类型，在Member types可以查到：

我们可以看到size_type 其实就是size_t类型

value_type则是第一个模板参数，也就是我们这里的T，class就是实例化对象类型。

所以库里面的函数定义翻译过来就是void resize(size_t n , T =T() )

n 是改变的size的大小，T = T() 是调用了系统默认构造函数。

由此可以应证C++内置类型也需要(也有)默认构造函数的概念，因为像这种类似的场景用得到。

如果T是内置类型不是自定义类型，如何调用默认构造，所以内置类型也有默认构造函数的概念。

上面我们说了一般来说不会轻易缩容，因为代价比较大，像reserve只扩不缩，resize、clear都不动capacity，但是shrink_to_fit 接口是实现来缩容的，与上面reserve、resize相反，是 “以空间换时间 ”。

扩容一般是实现两倍扩容，像Linux等平台下都是两倍，也有些平台是1.5倍扩容，像VS，具体看编译器实现，两倍扩容一般用的比较多一点。

两个接口都是用来遍历访问vector中的数据的，存在着一定差异。

相同之处是使用方式类似，都是通过下标获得数据。并且都提供了const和非const两个版本。

为什么要提供两个版本？————

1、只读接口函数只有const版本的（如：size函数）只能由const对象调用

2、只写函数接口只有非const版本的（如：push_back函数），只能由非const(普通）对象调用

3、可读可写接口函数，const+非const都提供（如：operator[]），两者都能调用

注意这里的[ ]是函数调用，不是单纯的操作符，与数组不同。

operator[ ]和at的区别在于越界的情况下，[ ] 内部实现的时候是assert断言下标位置pos< size的，

而at 则是通过抛异常的方式报错。（注：assert在debug下有效，relase下不产生效果）

assign 有2种用法：

用法 1、覆盖赋值，这种方式会覆盖掉之前所有数据。

vectora;
	a.resize(5);
	a.push_back(1);
	a.push_back(2);
	a.push_back(3);
	a.push_back(4);
	for (auto e : a)
	{
		cout<< e<< "";
	}
	cout<< endl;

	a.assign(9, 1);

	for (auto e : a)
	{
		cout<< e<< "";
	}
	cout<< endl;

从结果来看确实覆盖了之前的数据。

用法 2、支持迭代器区间

库里面给的接口参数就是迭代器区间  [first,last) \ [begin,end) ，是左闭右开的。

使用方式：

vectoraa;
	aa.resize(5);
	for (auto e : aa)
	{
		cout<< e<< " ";
	}
	cout<< endl;

	size_t i = 0;
	vectorbb;
	bb.resize(5);
	for (auto &e : bb)
	{
		e = i++;
	}
	aa.assign(bb.begin(), bb.end());
	for (auto e : aa)
	{
		cout<< e<< " ";
	}
	cout<< endl;

再看参数类型，我们发现库里给参数迭代器也写了一个模板，有人会问：直接写成iterator不就行了，为什么还要写个迭代器模板？

————因为如果单写迭代器就只支持vector下的迭代器区间，写成模板的话可以支持其他容器的迭代器区间，比如：

这样就支持了string容器的迭代器区间。

也可以这样使用：

与上面对比一下，发现区间确实像期望所改变了。

数据结构最重要的一环可以说是增删查改了。

增：最常用的是push_back，但是push_back适用于尾插，而在顺序表中一般不建议在中间位置插入（尤其是头插），因为这样会挪动数据，效率低下。所以insert接口使用没有push_back频繁。

另外insert可以插入一个元素，也可以插入一段数据。

删：最常用的是pop_back，但是pop_back适用于尾删，和增一样，其他情况会挪动数据，因此erase接口也使用不那么频繁。

另外删可以删除单个位置数据，也可以直接删除一段数据。

查：在vector容器库中发现没有期望的find接口，这是怎么回事？————因为这个接口在每个容器中实现的方式都是一样的，都是遍历迭代器，找到了就返回对应的迭代器位置，所以不会特地在每个容器中都写一个find，而是将它拉出来写个模板，使得每个容器都能直接使用。

可以看到find是从first位置开始查找，到 last位置结束，找到了返回此时的迭代器，没找到就返回last位置的迭代器（这也体现了迭代器区间左闭右开，last不在区间中）。

使用方式：

vector::iterator it = find(aa.begin(), aa.end(), 101);
	if (it != aa.end())
	{
		aa.insert(it, 0);
	}
	for (auto e : aa)
	{
		cout<< e<< " ";
	}
	cout<< endl;

这里找到了就在当前迭代器位置之前插入0，没找到就不插入。

改：改的话主要是通过operator[ ] 来实现。

vector中自己实现了一个swap函数，因为库里的swap函数交换代价太大，需要深拷贝。

容器中实现的可以直接完成交换，大大降低了代价开销。

vectorbb;
	bb.push_back(1);
	aa.swap(bb);
	for (auto e : aa)
	{
		cout<< e<< " ";
	}
	cout<< endl;

LeetCode118.杨辉三角

首先看到题目的图要明确一点：要实现的二维数组是每一行的元素个数不同，但并非按图上画的那般顺序排列，二维数组的图应该是这样的：

题中给的接口样式需要返回的是二维数组地址，传进来的是二维数组的行数。

对于这种问题，我们可以先创建一个二维数组模型，先建立行，再通过行来创建列，从而通过二维数组的下标访问每个元素。

创建二维数组模型：vector>vv;

建立行：vv.resize(numRows);  //传参行数为numRows

通过行建立列（通过for循环实现）:

for (int i = 0; i< vv.size(); ++i)
        {
            vv[i].resize(i + 1, 0);
        }

同时观察杨辉三角图，每行首末元素都为1，所以在循环中将首末元素赋值为1：

for (int i = 0; i< vv.size(); ++i)
        {
            vv[i].resize(i + 1, 0);
            vv[i][0] = vv[i][vv[i].size() - 1] = 1;
        }

此时二维数组建立完成，首末元素为1，其余元素为0. 再观察图，发现每行非1元素 = 上一行同列元素 + 上一行同列元素前一个；

于是用for循环将每个非1元素的值填上：

for (int i = 0; i< vv.size(); ++i)
        {
            for (int j = 0; j< vv[i].size(); ++j)
            {
                if (vv[i][j] == 0)
                {
                    vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
                }
            }
        }

最后返回二维数组首元素地址vv就可以了。

完整代码如下：

class Solution {
public:
    vector>generate(int numRows) {
        vector>vv;
        vv.resize(numRows);
        for (int i = 0; i< vv.size(); ++i)
        {
            vv[i].resize(i + 1, 0);
            vv[i][0] = vv[i][vv[i].size() - 1] = 1;
        }
        for (int i = 0; i< vv.size(); ++i)
        {
            for (int j = 0; j< vv[i].size(); ++j)
            {
                if (vv[i][j] == 0)
                {
                    vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
                }
            }
        }
        return vv;
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧