STL--向量（vector）

STL的组成

标准模板库STL关注的重点是泛型数据结构和算法，其关键组成部分是容器(containers)、算法(algorithms)、迭代器(iterators)、函数对象(Function Object)、适配(Adaptor)。 本文地址：http://www.cnblogs.com/archimedes/p/Cpp-STL-Vector.html，转载请注明源地址。 容器(containers)：容器是数据在内存中组织的方法，例如，数组、堆栈、队列、链表或二叉树(不过这些都不是STL标准容器)。 STL 中的容器是一种存储T (Template)类型值的有限集合的数据结构, 容器的内部实现一般是类。这些值可以是对象本身，如果数据类型T代表的是Class的话。 算法(algorithms)：算法是应用在容器上以各种方法处理其内容的行为或功能。例如，有对容器内容排序、复制、检索和合并的算法。在 STL中，算法是由模板函数表现的。这些函数不是容器类的成员函数。相反，它们是独立的函数。它们不仅可以将其用于STL容器，而且可以用于普通的C++ 数组或任何其他应用程序指定的容器。 迭代器(iterators) ：一旦选定一种容器类型和数据行为(算法)，那么剩下唯一要他做的就是用迭代器使其相互作用。可以把迭代器看作一个指向容器中元素的普通指针。可以如递增 一个指针那样递增迭代器，使其依次指向容器中每一个后继的元素。迭代器是STL 的一个关键部分，因为它将算法和容器连在一起。 函数对象(Function Object)：定义了函数调用操作符(operator())的类 适配器(adaptor)：封装一个部件以提供另外的接口(例如用list实现stack) 容器的分类: 序列式容器（Sequence containers） 每个元素都有固定位置－－取决于插入时机和地点，和元素值无关。 vector(向量)、deque(双端队列)、list(表) 关联式容器（Associated containers） 元素位置取决于特定的排序准则，和插入顺序无关 set(集合)、multiset(多重集合)、 pmap(映射)、multimap(多重映射) 向量（vector） 向量(vector 容器类):#include vector ，vector 是一个能够存放任意类型的动态数组，是基本数组的类模板。其内部定义了很多基本操作。 内部实现: 数组 vector T, Alloc 可以随机存取数据（用索引直接存取）。 向量尾部添加或删除数据,耗时O(1)。但是在中部或头部插入或删除数据需要移动后面数据,耗时O(N)。 vector 类中定义了4 中种构造函数： 默认构造函数，构造一个初始长度为0 的空向量，如： vector int v1 ; 带有单个整形参数的构造函数，此参数描述了向量的初始大小。这个构造函数还有一个可选的参数，这是一个类型为T的实例，描述了这个向量中各成员的初始值；如： vector int v2(n,0); 如果预先定义了 n, 他的成员值都被初始化为0； 复制构造函数，构造一个新的向量，作为已存在的向量的完全复制，如： vector int v3(v2) ; 带两个常量参数的构造函数，产生初始值为一个区间的向量。区间由一个半开区间 [ first,last ) 来指定。如： vector int v4(first,last)
vector int vec1(ar, ar + 10); // first=ar,last=ar+10, 不包括ar+10 vector char vec2(str, str + strlen(str)); // first=str,last= str+strlen(str) cout "vec1:" endl; // 打印vec1 和vec2 ，const_iterator 是迭代器，后面会讲到 // 当然，也可以用for (int i=0; i vec1.size(); i++)cout vec[i]; 输出 //size() 是vector 的一个成员函数 for (vector int ::const_iterator p = vec1.begin();p != vec1.end(); ++p) cout *p; cout \n "vec2:" endl; for (vector char ::const_iterator p1 = vec2.begin();p1 != vec2.end(); ++p1) cout *p1; cout \n; return 0; }

vector操作：

myvec.clear()              移除容器中所有数据。 myvec.push_back(elem)        在尾部加入一个数据elem。 myvec.pop_back()  删除最后一个数据。 myvec.size()         返回容器中实际数据的个数,类型为size_type。 myvec.erase(pos)        删除pos位置的数据，返回下一个数据的位置。 myvec.insert(pos,cnt,elem)  在pos位置插入cnt个数据elem。 myvec.begin()       返回的指针指向数组中的第一个数据。 myvec.end()          实际上是取末尾加一，以便让循环正确运行--它返回的指针指向最靠近数组界限的数据。 myvec.empty()          判断容器是否为空。 operator[]                  返回容器中指定位置的一个引用
typedef vector int INTVECTOR;// 自定义类型INTVECTOR int main() { // 测试vector 容器的功能 INTVECTOR vec1;//vec1 对象初始为空 INTVECTOR vec2(10, 6);//vec2 对象最初有10 个值为6 的元素 INTVECTOR vec3(vec2.begin(), vec2.begin() + 3);//vec3 对象最初有3 个值为6 的元素，拷贝构造 INTVECTOR::iterator i;// 声明一个名为i 的双向迭代器 cout "vec1.begin()--vec1.end():" endl;// 从前向后显示vec1 中的数据 for (i = vec1.begin(); i != vec1.end(); ++i) cout *i " "; cout endl; cout "vec2.begin()--vec2.end():" endl;// 从前向后显示vec2 中的数据 for (i = vec2.begin(); i != vec2.end(); ++i) cout *i " "; cout endl; cout "vec3.begin()--vec3.end():" endl;// 从前向后显示vec3 中的数据 for (i = vec3.begin(); i != vec3.end(); ++i) cout *i " "; cout endl; // 测试添加和插入成员函数，vector 不支持从前插入 vec1.push_back(2); // 从后面添加一个成员 vec1.push_back(4); vec1.insert(vec1.begin() + 1, 5);// 在vec1 第一个的位置上插入成员5 vec1.insert(vec1.begin() + 1, vec3.begin(), vec3.end());// 从vec1 第一的位置开始插入vec3 的所有成员 cout "after push() and insert() now the vec1 is:" endl; for (i = vec1.begin(); i != vec1.end(); ++i) cout *i " "; cout endl; // 测试赋值成员函数 vec2.assign(8, 1); // 重新给vec2 赋值，8 个成员的初始值都为1 cout "vec2.assign(8,1):" endl; for (i = vec2.begin(); i != vec2.end(); ++i) cout *i " "; cout endl; // 测试引用类函数 cout "vec1.front()=" vec1.front() endl;// vec1 第零个成员 cout "vec1.back()=" vec1.back() endl;// vec1 的最后一个成员 cout "vec1.at(4)=" vec1.at(4) endl;// vec1 的第五个成员 cout "vec1[4]=" vec1[4] endl; // 测试移出和删除 vec1.pop_back();// 将最后一个成员移出vec1 vec1.erase(vec1.begin() + 1, vec1.end() - 2);// 删除成员 cout "vec1.pop_back() and vec1.erase():" endl; for (i = vec1.begin(); i != vec1.end(); ++i) cout *i " "; cout endl; // 显示序列的状态信息 cout "vec1.size(): " vec1.size() endl;// 打印成员个数 cout "vec1.empty(): " vec1.empty() endl;// 清空 return 0; }
C++ STL学习之【vector的使用】 vector 是表示可变大小数组的序列 容器，其使用的是一块 连续 的空间，因为是动态增长的数组，所以 vector 在空间不够时会扩容；vector 优点之一是支持 下标的随机访问，缺点也很明显，头插或中部插入效率很低，这和我们之前学过的 顺序表 性质很像，不过在结构设计上，两者是截然不同的