c++ - vector - ^(*￣(oo)￣)^

vector

标准库类型vector表示对象的集合，其中所有的对象的类型都相同（容器）。

c++语言既有类模板也有函数模板，vector是一个类模板。

模板本身不是类或函数，可将其视为生成类或函数的一份说明。编译器根据模板创建类或函数的过程称为实例化，当使用模板时，需要指出编译器应把类或函数实例化成何种类型。

对于类模板需提供额外信息指定模板到底实例化成什么样的类，需要提供哪些信息由模板决定。提供信息的方式：模板名称后跟一对尖括号，括号内放上信息。

vector<int> ivec; // ivec 保存int类型的对象
//vector<Sales_item> Sales_vec; // 保存Sales_item类型的对象
vector<vector<string>> file; // 该向量的元素是vector对象

vector是模板而非类型，由vector生成的类型必须包含vector中元素类型，例如vector。因引用不是对象，所以不存在包含引用的vector。早期的c++标准中外层vector对象的右尖括号和其元素类型之间必须添加一个空格。

vector<vector<int>> // c++11新标准
vector<vector<int> > // 早期版本

定义和初始化vector对象

方法名	描述
vector v1	空vector，元素类型为T，默认初始化
vector v2(v1)	v2中包含有v1所有元素的副本
vector v2=v1	等价于 v2(v1)
vector v3(n, val)	v3包含了n个重复元素，每个元素的值都是val
vector v4(n)	v4包含了n个重复地执行了值初始化的对象
vector v5{a,b,c...}	v5包含了初始值个数的元素，每个元素被赋予相应的初始值
vector v5={a,b,c...}	等价于v5{a,b,c...}

vector允许拷贝vector，新vector对象的元素就是原vector对象对应元素的副本。拷贝时两个vector对象类型必须相同。

一般情况下初始化时用花括号为列表初始化（直接取值），使用圆括号为构造vector对象（个数，值）。但当使用花括号时，提供的值不能用来列表初始化，此时编译器会尝试用默认值初始化vector对象（转为个数，值）。

vector对象添加元素

通过vector成员函数push_back向其中添加元素。

vector对象能高效增长，没必要在定义时设定大小，这样做性能可能更差。只有一种例外情况，所有元素的值都一样，值不同时最好定义空vector对象，运行时添加具体值。同大多数语言不同，指定初始容量并非好事。

不应在范围for语句体内改变所遍历序列的大小。

size()

vector 的size方法返回值类型为vector定义的size_type类型，类似string的size_type。使用此size_type需指定它是由哪种类型定义的。

vector<string>::size_type b = a.size();
// vector::size_type b2 = a.size(); 错误，模板必须加类型

迭代器

所有标准库容器都可以使用迭代器，其中只有少数几种才同时支持下标运算符。string对象严格来说不属于容器类型，但string支持很多与容器类型类似的操作（下标运算符、迭代器）。

迭代器提供了对对象的间接访问。获取迭代器不是使用取地址符，有迭代器的类型同时拥有返回迭代器的成员。这些类型都有名为begin和end的成员，begin成员负责返回第一个元素（或第一个字符）

auto b = ivec.begin(), e = ivec.end(); // b和e的类型相同

end成员负责返指向容器（或string对象）“尾元素的下一位置”的迭代器，该迭代器指示的是容器的一个本不存在的“尾后”元素。end仅是一个标记，表示处理完了容器的所有元素。end成员返回的迭代器常被称作尾后迭代器。当容器为空时，begin与end返回同一迭代器，都是尾后迭代器。

string s("some string");
if (s.begin() != s.end())
{
    auto it = s.begin();  // 获得s中第一个字符的迭代器
    *it = toupper(*it); // 解引用运算符修改内容
}
//Some string

迭代器通过递增(++)运算符来从一个元素移动到下一个元素。end返回的迭代器并不实际指示某个元素，不可使用递增或解引用操作（无意义）。

string s("some string");
for (auto it = s.begin(); it != s.end() && !isspace(*it); ++it)
{	
    *it = toupper(*it);
}
std::cout << s << std::endl;
// SOME string

c++语言在for循环中更愿意使用!=而非<，原因在于遍历时更愿意用迭代器而不是下标，因为迭代器在标准库的所有容器上都有效，而下标运算符并不是全都可以用。

迭代器分为iterator和const_iterator两种类型：

vector<int>::iterator it; //it能读写vector<int>的元素
string::iterator it2; //it2能读写string对象中的字符

vector<int>::const_iterator it3; //it3只能读的元素，不能写
string::const_iterator it4; //it4只能读字符，不能写

begin和end返回的具体类型由对象是否是常量决定，当对象是常量则返回const_iterator，否则返回iterator。

c++中新引入了cbegin和cend可以得到const_iterator类型的返回值。不需要修改元素时，可使用cbegin和cend。

for (auto it = s.cbegin(); it != s.cend(); ++it)
{
}

也可直接指定类型

for (string::const_iterator it = s.begin(); it != s.end(); ++it)
{
}

解引用和成员访问

解引用迭代器可获得迭代器所指的对象，当对象类型恰好是类时，可进一步访问对象的成员。

for (auto it=s.begin(); it!=s.end()&&!(*it).empty();++it)
// .优先级高于*故需要加()

c++中箭头运算符(->)将解引用和成员访问两个操作结合到了一起。it->empty() 与 (*it).empty() 意思相同。

vector<string> s{ "a","some string", "", "b" };
for (auto it=s.cbegin(); it!=s.cend()&&!it->empty();++it)
{
    std::cout << *it << std::ends;
}
// a some string

vector对象不可在for循环中添加元素;任何一种可能改变vector对象容量的操作，如push_back，都会使该vector对象的迭代器失效。

二分搜索

int main()
{
	vector<string> text{ "abc","acb","bac","bca","cab","cba" }; // 递增 有序
	string sought = "cab";
	// beg和end表示我们搜索的范围
	auto beg = text.begin(), end = text.end();
	auto mid = text.begin() + (end - beg) / 2; // 初始状态下的中心点  iter+3为bca
	// 当还有元素尚未检查且未找到sought时执行循环
	while (mid != end && *mid != sought)
	{
		if(sought < *mid) // 判断是否在前半
		{
			end = mid; // 忽略后半段
		}else  // 在后半
		{
			beg = mid + 1; // 在mid后寻找
		}
		mid = beg + (end - beg) / 2; // 新的中心点
	}
	if (mid < end) {
		std::cout << *mid << std::endl;
	}
	else 
	{
		std::cout << "未找到" << std::endl;
	}
	return 0;
}

迭代器支持的运算：加减整数；加减法的复合赋值语句；大小比较；两迭代器相减操作（二者的距离）。 不支持两迭代器相加，只能写成text.begin() + (end - beg) / 2;不能写成(beg + end) / 2;

数组

数组类似于标准库类型vector，也是用于存放类型相同的对象的容器，但是数组大小是固定的，不灵活但是性能会好些。

数组的声明形如a[d]，a是数组名，d是数组的维度，必须大于0。数组中元素个数为数组类型的一部分，故编译时维度应是已知的。维度必须是一个常量表达式，常量不总是常量表达式，需根据值的初始化时机来确定。

unsigned cnt = 42; // 非常量表达式
constexpr unsigned sz = 42; // 常量表达式
const unsigned ccnt = 42;
int arr[10]; // 含10个int的数组
int *parr[sz]; // 含42个int*的数组
//string bad[cnt]; // cnt 非常量表达式
string bad2[ccnt]; // const声明的不一定就是常量表达式，但此时绑定的是字面值故可以通过编译器。
// string strs[get_size()]; // 当get_size 是constexpr时正确

const unsigned ccnt2 = cnt; 
string bad3[ccnt2];// 此时会报错 cnt运行时才会获得值
const unsigned ccnt3 = ccnt; 
string bad4[ccnt3];// 此时可以，ccnt也是常量，编译时可获得值

定义数组同样必须指定类型，不允许用auto关键字根据初始值列表推断类型。数组的元素应为对象，因此不存在引用的数组。

int a2[] = {0, 1, 2}; // 维度为3
int a3[5] = {0, 1, 2}; // 0，1，2，0，0
string a4[3] = {"hi", "bye"}; // 等价于 "hi", "bye", ""
// int a5[2] = {0, 1, 2}; // 错误，初始值过多

字符数组可通过字符串赋值，但最后会添加一个空字符到字符数组。

char a1[] = {'C','+','+'}; // 维度为3,最后无空字符
char a2[] =  {'C','+','+','\0'}; // 维度为4,显式添加空字符
char a3[] = "C++"; // 等加入a2，会自动添加表示字符串结束的空字符
//char a4[3] = "C++"; // 错误，初始值过多，放不下空字符

拷贝和赋值

不能将数组的内容拷贝给其他数组作为初始值，也不能用数组为其他数组赋值：

int a[] = {0, 1, 2}; // 3个整数的数组
int a2[] = a; // 不可直接使用数组初始化数组
a2 = a; // 不可直接把数组赋值给数组

数组名表示的就是数组的首地址。

复杂的数组声明

int arr[10];
int *ptrs[10]; // ptrs是含有10个int指针的数组
//int &refs[10]; // 错误，不存在引用的数组
int(*Parray)[10] = &arr; // Parray指向一个含有10个int的数组
int(&arrRef)[10] = arr; // arrRef引用一个含有10个int的数组

默认情况下，类型修饰符从右向左绑定，但当包含圆括号时，应优先从内向外。

int *(&array)[10] = ptrs; // 引用一个数组，数组含有10个指针

按照由内向外顺序，可知array是一个引用，根据右侧可知arr引用的是一个数组，最后根据左侧可知数组元素类型为int * 。故array为包含10个int指针的数组引用。

访问数组元素

数组下标类型为size_t，一种和机器相关的无符号类型。

指针和数组

数组名为数组首元素的地址，故可以直接被指针指向。

指针也是迭代器，因此使用指针也能遍历数组中的元素。

int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
int *beg = std::begin(arr);
int *last = std::end(arr);
// const int *beg = std::cbegin(arr);
// const int *last = std::cend(arr);
while(beg != last)
{
    std::cout << *beg << std::endl;
    ++beg;
}

可使用begin、end 或 cbegin、cend函数来获取指向数组首元素和尾元素下一位置的指针。