首页 > 代码库 > 回归季——C++ STL vector

回归季——C++ STL vector

博主从几年前开始脱离ACM大军,至今已经三个年头,花了点时间改善了一下环境。最近回归程序猿大军,发现代码力一落千丈,早已不是以前一晚上横扫OJ的程序猿预备军了。现在已经沦为代码渣渣。至此从新开始写博客,从新巩固代码力。会陆续的把学习的过程更新出来,希望代码力早日恢复T_T。

最近刷LeetCode,才发现原来在刷ACM的时候,用大量的C代替了STL的做法在leetcode上实行起来并不方便,所以痛定思痛。从很久以前不想学的STL开始入手,早就听说STL是个好东西,只是习惯了写C,就懒得去学C++的东西了。既然要踏实的学习,就好好研究,看看能否体会到STL的伟大之处。

博主学习东西比较随性,不会一板一眼的介绍概念什么的,通常都是想到什么就测试什么,然后贴出结论。当然如果有新概念就会进行阐述的。博客的主要目的就是给自己做笔记提醒用。

好啦,正式开始。


Vector,中文是“向量”,多么难懂的名字,向量明明是几何里的概念好吗?之前对vector还是云里雾里的时候,听同学吹牛说用向量做存储,着实的崇拜了一把,其实,这个东西说白了就是数组。不过它有一点特别就是,vector可以根据你的定义,做各种数据类型的数组。比如:

vector<int>
vector<string>
vector<struct a>
vector< vector<int> > //注意最后两个>之间要有空格

例子:

#include <cstdio>
#include <iostream>
#include <vector>
#include <string>

using namespace std;


struct a{
	int a;
	int b;
	char c;
};
	

void test(){
	vector<int> a;
	//cout << a.at(100) << endl; // When the index is greater than the range, it would show error.
	for (int i = 0; i < 100; i ++){
		a.push_back(i);
		cout << a[i];
	}
	cout << endl;

	vector<int> b;
	for (int i = 1; i < 100; i ++){
		b.push_back(i + 1);
	}
	cout << (a == b) << endl; // Tow vector

	struct a bb;
	bb.a = 1;
	bb.b = 2;
	bb.c = 'c';
	vector<struct a> strctv;
	strctv.push_back(bb);
	cout << (strctv[0].a == strctv[1].b);

	string str1, str2;
	str1 = "abcd";
	str2 = "zyxw";
	vector<string> vs;
	vs.push_back(str1);
	vs.push_back(str2);
	cout << vs[0] << vs[1] << endl;

	vector<vector<int> > vv;
	vv.push_back(a);
	vv.push_back(b);

	cout << vv[0][0] << vv[1][1] << endl;
}

int main(void){
	test();
	return 0;
}

简单的赋值和输出代码,展示vector可以装各种类型。以及vector变量之间可以进行 ==, !=, <=, >=, <, > 操作。但是如果vector包含的是结构体,需要重载这些操作符。

有一点需要注意,vector 可以作为几乎所有类型的容器,但是单个容器中的类型只能有一种。比如博主本来想要做vector<vector>,结果无情的被报错了。


知道了如何定义之后,我们来根据上面的例子说一下几个简单的操作,赋值、调用,状态。

赋值:

1, assign(int num, TYPE val);assign(input_iterator start, input_iterator end);

在定义某个vector之后或者是使用了一段时间后,清空之前的vector内容,利用assign重新赋值num个类型是TYPE的val。

vector<int> vi;
vi.assign(12, 1);
//这时,vi的内容就是{1,1,1,1,1...,1}
同样的还有另一种形式,如下,可以完成这个效果,结果一样。

vector<int> vi2(12, 1);

所以,assign是一个很好的初始化使用的函数,只是因为只是赋值同样的东西,所以可能并不是特别实用。

assign函数还有另一个重载assign(input_iterator start, input_iterator end),就是说,用另一个vector的iterator取某一个vector的一段赋值给另一个vector。

给一个例子:

void test1(){
	vector<int> vi;
	for (int i = 0; i < 12; i++){
		vi.push_back(i);
	}
	for (int i = 0; i < 12; i++){
		cout << vi[i];
	}
	cout << endl;

	std::vector<int>::iterator it;
	it = vi.begin() + 3;

	vector<int> vi2;
	vi2.assign(it, vi.end() - 3);
	std::vector<int>::iterator it2;
	for (it2 = vi2.begin(); it2 != vi2.end(); it2++){
		cout << *it2;
	}
	cout << endl;

<span style="white-space:pre">	</span>vi.assign(vi.begin() + 3, vi.end() - 3);
<span style="white-space:pre">	</span>for (it2 = vi2.begin(); it2 != vi2.end(); it2++){
<span style="white-space:pre">		</span>cout << *it2;
<span style="white-space:pre">	</span>}
<span style="white-space:pre">	</span>cout << endl;
}
输出结果是:

01234567891011
345678
345678

首尾各3个值被拿掉,因为迭代器it = vi.begin() +3,而assign的第二个参数也是vi.end() - 3。这就表示assign的迭代器使用很灵活,可以直接通过vector实例的begin(),end()等作为参数,也可以通过迭代器变量作为参数。 大家注意一下第三个输出,这个是vi使用assign作用于自己。也就是说,可以用assign()不断的缩小vector自身。

其实在定义vector的时候,vector的构造函数可以完成和assign几乎相同的功能。主要形式有如下四种:

(1)vector()

(2)vector(size_type n, const TYPE &v);

(3)vector(const vector &from)

(4)vector (input_iterator start, input_iterator end);

vector<int> first;                                // 空向量
vector<int> second (12, 1);                       // 12个1
vector<int> third (second.begin(),second.end());  // 通过迭代器得到和second一样的third
vector<int> fourth (third);                       // 直接用third初始化fourth

2, push_back(), pop_back()。

这两个是配对的,所以一起说,void push_back(const TYPE val)是在vector的最后添加一个类型为TYPE的元素,值为val(TYPE必须是vector包含的类型)。而void pop_back()是删除掉vector最后的一个元素,注意这个地方没有返回值。

例子:

void test2(){
	vector<int> vi;
	std::vector<int>::iterator it;

	for (int i = 0; i < 12; i++){
		vi.push_back(i);
	}
	for (it = vi.begin(); it != vi.end(); it++){
		cout << *it;
	}
	cout << endl;	

	for (int i = 0; i < 10; i++){
		vi.pop_back();
	}
	for (it = vi.begin(); it != vi.end(); it++){
		cout << *it;
	}
	cout << endl;
}

输出结果:

01234567891011
01
push_back()了12次,pop_back()了10次,所以最后剩下两个值。

3. insert()

insert()有三种主要的形式:(1)iterator insert (iteartor loc, const TYPE &val); (2) void insert(iterator loc, size_type num, cost_TYPE &val); (3) void insert (iterator loc, input_iterator start, input_iterator end);

(1) 在loc迭代器所在的位置,插入单个值val,并且返回这个值所在的位置的迭代器。

(2) 在loc位置插入num个TYPE类型的值val;

(3) 在loc位置,插入迭代器start到end之间的值。

例子:

void test3(){
	vector<int> vi;
	std::vector<int>::iterator it;

	for (int i = 0; i < 12; i++){
		vi.push_back(i);
	}

	for (it = vi.begin(); it != vi.end(); it++){
		cout << *it << " ";
	}
	cout << endl;

	cout << *vi.insert(vi.begin(), 100) << endl;;

	vi.insert(vi.begin() + 10, 4, 200);
	for (it = vi.begin(); it != vi.end(); it++){
		cout << *it << " " ;
	}
	cout << endl;

	vi.insert(vi.begin(), vi.begin(), vi.end());
	for (it = vi.begin(); it != vi.end(); it++){
		cout << *it << " " ;
	}
	cout << endl;

}
输出结果:

0 1 2 3 4 5 6 7 8 9 10 11 
100
100 0 1 2 3 4 5 6 7 8 200 200 200 200 9 10 11 
100 0 1 2 3 4 5 6 7 8 200 200 200 200 9 10 11 100 0 1 2 3 4 5 6 7 8 200 200 200 200 9 10 11 

貌似很好理解。

调用:

vector的调用貌似很好用,如同最开所说vector其实就是一个数组,所以可以直接用数组的调用形式来做。

例如:a[0], a[1], a[2],这样。

at(int index):

还有一种形式是使用at(int index)函数,直接访问vector的index小标中的内容。

所以a[0] 等价于 a.at(0).区别在于,如果越界,at()函数会返回错误,[0]则不会返回错误。


(1)front(), back()

这是两个返回值的函数,分别返回第一个和最后一个vector内的元素的引用。

例子:

void test4(){
	vector<int> vi(10, 1);
	std::vector<int>::iterator it;
	int i = 0;
	for (it = vi.begin(); it != vi.end(); it ++){
		*it = i++;
		cout << *it << " ";
	}
	cout << endl;
	cout << "front: " << vi.front() << endl;
	cout << "back: " << vi.back() << endl;
	vi.front() += 10;
	vi.back() -= 10;
	for (it = vi.begin(); it != vi.end(); it ++){
		cout << *it << " ";
	}
	cout << endl;
}

输出结果:

void test4(){
	vector<int> vi(10, 1);
	std::vector<int>::iterator it;
	int i = 0;
	for (it = vi.begin(); it != vi.end(); it ++){
		*it = i++;
		cout << *it << " ";
	}
	cout << endl;
	cout << "front: " << vi.front() << endl;
	cout << "back: " << vi.back() << endl;
	vi.front() += 10;
	vi.back() -= 10;
	for (it = vi.begin(); it != vi.end(); it ++){
		cout << *it << " ";
	}
	cout << endl;
}


(2)迭代器 iterator

迭代器是我自从接触STL之后一直很头痛的东西,因为名字太长了= =。。。没想到今天在整理前面的内容的时候,渐渐地已经把iterator的用法搞通了。

iterator其实你可以认为是一种遍历的工具。它有点像指针,指定在容器中的某一个位置,通过++遍历下一个。是一个很好用的工具,在STL中有不少函数返回值和参数也是用迭代器类型,方便我们操作。所以我会带着基本的迭代器函数一起介绍。

定义:std::vector<int>::iterator it; //名字很长,但不难记,std是namespace;vector<int>是迭代器所对应容器的类型,和它要操作的容器类型一定是相同的;iterator是固定的迭代器的英文;it是迭代器的变量名。

(2.1) begin(), end():

这两个函数会返回vector的开头元素所在位置和结尾元素所在位置的迭代器。


给个例子:

<span style="white-space:pre">	</span>vector<int> vi(10, 1);
	std::vector<int>::iterator it;
	int i = 0;
	for (it = vi.begin(); it != vi.end(); it ++){
		*it = i++;
		cout << *it << " ";
	}
相对应的有这另一对函数rbegin(), rend(): 他们会返回一个逆向的迭代器,rbegin()指向链表的末尾,rend()指向链表的开头。所以我们可以反向给vector赋值。

给一个例子:

<pre name="code" class="cpp">void test5(){
	vector<int> vi(12, 1), rvi(12, 1);
	std::vector<int>::reverse_iterator rit;
	std::vector<int>::iterator it;
	int i;

	for (i = 1, it = vi.begin(); it != vi.end(); it++){
		*it = i++;
	}
	for (i = 1, rit = rvi.rbegin(); rit != rvi.rend(); rit ++){
		*rit = i++;
	}

	for (int i = 0; i < 12; i++){
		cout << vi[i] << " " ;
	}
	cout << endl;
	for (int i = 0; i < 12; i++){
		cout << rvi[i] << " " ;
	}
	cout << endl;
}


输出结果为:

<pre name="code" class="cpp">1 2 3 4 5 6 7 8 9 10 11 12 
12 11 10 9 8 7 6 5 4 3 2 1 

(2.2) erase():

删除指定元素的函数。这个函数有两种形式:

iterator erase(iterator loc); //删除掉迭代器loc所指向的元素并返回后一个元素的迭代器

iterator erase(iterator start, iterator end); //删除[start, end)区间内的迭代器,并返回end的迭代器。 

例子:

<pre name="code" class="cpp">void test6(){
	vector<int> vi(12, 1);
	std::vector<int>::iterator it;
	int i;

	for (i = 1, it = vi.begin(); it != vi.end(); it++){
		*it = i++;
	}
	cout << "Original:";
	for (it = vi.begin(); it != vi.end(); it ++){
		cout << *it << " " ;
	}
	cout << endl;

	cout << "Delete: " << *(vi.begin() + 3) << endl;
	vi.erase(vi.begin() + 3);
	cout << "Erase1 Result: ";
	for (it = vi.begin(); it != vi.end(); it ++){
		cout << *it << " " ;
	}
	cout << endl;

	cout << "Delete from " << *(vi.begin() + 1) << " until " << *(vi.end() - 1) << endl;
	cout << "Stop at: " << *vi.erase(vi.begin() + 1, vi.end() - 1) << endl;
	cout << "Erase2 Result: ";
	for (it = vi.begin(); it != vi.end(); it ++){
		cout << *it << " " ;
	}
	cout << endl;
}


输出:

Original:1 2 3 4 5 6 7 8 9 10 11 12 
Delete: 4
Erase1 Result: 1 2 3 5 6 7 8 9 10 11 12 
Delete from 2 until 12
Stop at: 12
Erase2 Result: 1 12 

状态: 

(1)vector的容量相关:capacity(), size(), resize(), reserve(), 

capacity(void)是返回vector当前容量的函数。也就是说当前系统给vector分配的空间能够存储多大的容量。

reserve(type_size size) 是设定向量容量为size的函数。在没有给vector设定容量的时候,通常会根据放入的元素数量,由0, 1, 2, 4, 8, 16, 32, 64, 128,256... 这样倍数增长。例如,如果你用push_back()逐个给vector变量添加元素,这个变量的容量会在

插入第一个元素的时候变成1,
插入第二个元素的时候变成2,
插入第三个元素的时候变成4,
插入第五个元素的时候变成8,
插入第九个元素的时候变成16,
插入第十七个元素的时候变成32,
。。。。。。

但是如果你事先知道你可能只要插入50个元素,那么就直接用reserver(50), 之后除非元素总数超过50,否则向量的容量大小是不会变的。

引入c++网站上reserve()的例子,点击进入原地址。

// vector::reserve
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int>::size_type sz;

  std::vector<int> foo;
  sz = foo.capacity();
  std::cout << "making foo grow:\n";
  for (int i=0; i<100; ++i) {
    foo.push_back(i);
    if (sz!=foo.capacity()) {
      sz = foo.capacity();
      std::cout << "capacity changed: " << sz << '\n';
    }
  }

  std::vector<int> bar;
  sz = bar.capacity();
  bar.reserve(100);   // this is the only difference with foo above
  std::cout << "making bar grow:\n";
  for (int i=0; i<100; ++i) {
    bar.push_back(i);
    if (sz!=bar.capacity()) {
      sz = bar.capacity();
      std::cout << "capacity changed: " << sz << '\n';
    }
  }
  return 0;
}

输出是

making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128
making bar grow:
capacity changed: 100

size()是返回当前vector内的元素个数,而resize就是重新定义这个个数。

size_type size(void)用法简单,直接调用返回元素个数。

resize()有几种变化,其函数形式为:void resize(size_type n, TYPE val = 0). n是将vector重置的目标数,而val是一个缺省参数,起默认为0.

当 n < size(), 则保留前n个元素;当n > size(), 则在vector末尾添加(n - size())个值为val的元素。

例子:

void test7(){
	vector<int> vi(1, 1);
	vector<int>::iterator it;

	cout << "1: Original size:" << vi.size() << endl;
	for (it = vi.begin(); it != vi.end(); it++){
		cout << *it << " ";
	}
	cout << endl;

	vi.resize(2, 2);
	cout << "2: New size:" << vi.size() << endl;
	for (it = vi.begin(); it != vi.end(); it++){
		cout << *it << " ";
	}
	cout << endl;

	vi.resize(3, 3);
	cout << "3: New size:" << vi.size() << endl;
	for (it = vi.begin(); it != vi.end(); it++){
		cout << *it << " ";
	}
	cout << endl;

	vi.resize(4, 4);
	cout << "4: New size:" << vi.size() << endl;
	for (it = vi.begin(); it != vi.end(); it++){
		cout << *it << " ";
	}
	cout << endl;

	vi.resize(1);
	cout << "5: End size:" << vi.size() << endl;
	for (it = vi.begin(); it != vi.end(); it++){
		cout << *it << " ";
	}
	cout << endl;


}

输出结果为:

1: Original size:1
1 
2: New size:2
1 2 
3: New size:3
1 2 3 
4: New size:4
1 2 3 4 
5: End size:1
1 

(2)swap()函数

swap(vector &from)函数就是当前向量和from向量交换所有的元素,无论size()各是多少,全部交换。相当于交换了指针内容。算是个非常简单的函数。

例子:

void test8(){
	vector<int> vi1(3, 3);
	vector<int> vi2;
	vector<int>::iterator it;

	for (int i = 0; i < 12; i++){
		vi2.push_back(i + 1);
	}
	cout << "Original: " << endl;
	cout << "vi1: " << endl;
	for (it = vi1.begin(); it != vi1.end(); it++){
		cout << *it << " ";
	}
	cout << endl;

	cout << "vi2: " << endl;
	for (it = vi2.begin(); it != vi2.end(); it++){
		cout << *it << " ";
	}
	cout << endl;

	cout << "Swap:vi1.swap(vi2); " << endl;
	vi1.swap(vi2);
		cout << "vi1: " << endl;
	for (it = vi1.begin(); it != vi1.end(); it++){
		cout << *it << " ";
	}
	cout << endl;

	cout << "vi2: " << endl;
	for (it = vi2.begin(); it != vi2.end(); it++){
		cout << *it << " ";
	}
	cout << endl;
}
输出结果:

Original: 
vi1: 
3 3 3 
vi2: 
1 2 3 4 5 6 7 8 9 10 11 12 
Swap:vi1.swap(vi2); 
vi1: 
1 2 3 4 5 6 7 8 9 10 11 12 
vi2: 
3 3 3 

(3) clear(), empty()

这两个函数用法和使用都不相同,放在一起说是因为他们两个的英文意义很像。而且是最后两个需要说明的函数了。

void clear(void)是清空vector内所有的元素。 

bool empty(void)是返回vector是否为空,若是则返回true,若不是则返回false。

很简单,不提供例子了。


vector是我第一个研究的STL,感觉通过这次踏踏实实的学习,对STL的用法和认识有了很全面的提高。不知道用vector的函数是否可以类推其他的STL容器的用法,应该可以为以后学习其他的STL节省不少时间。 STL我已经纠结了好几年了,虽然知道是简单的东西,虽然其实涉及到的语法和变化并不多,但是一直没有用心的去学习,每次用到都是去baidu相关用法,和查字典一般。感觉这样并不好,反而事倍功半。与其每次都查,不如一次性搞懂更加有效率。





回归季——C++ STL vector