首页 > 代码库 > STL--向量(vector)

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)
举例:
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int ar[10] = {  12, 45, 234, 64, 12, 35, 63, 23, 12, 55  };
char* str = "Hello World";
int main()
{
    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操作:

头文件   #include<vector>
定义变量  vector<int> myvec;
主要成员函数
  • 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[]                  返回容器中指定位置的一个引用
vector举例:
#include <iostream>
#include <vector>
using namespace std;
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;
}