摘要

本文主要借助对C++的标准模板库STL中实现的数据结构的学习和使用来加深对数据结构的理解。即联系数据结构的理论分析和详细的应用实现（STL），本文是系列总结的第一篇，主要针对线性表中的顺序表（动态数组）STL vector进行分析和总结。

引言

因为前段时间对台大的机器学习基石和技法课程进行了学习，发如今详细的实现中经常涉及到各种类型的数据结构，比方线性表、二叉树、图等，在使用这些数据结构时感到有些吃力。主要是对一些主要的数据结构理解的不够。所以趁着暑假假期。近期一段时间总会抽出时间复习一下数据结构。參考的教材是王立柱编著的《C/C++与数据结构》，在详细的应用中採用的是C++标准模板库STL中相应实现的数据结构，主要參考的是MSDN文档。

正文

基本数据结构

数据结构中最简单的一个实现就是线性表中的顺序表，其数据结构如图所看到的：

数据结构上的实现为：

typedef struct

{

  DataType *m_pData;

    int m_nMax,m_nSize;

}SeqList;

typedef int DataType;

从结构上看。顺序表就是一个动态数组，须要有一个容量为m_nMax和一个用来记录表中已经有多少数据的m_nSize。而动态数组的容量在执行过程中是能够扩充和缩减的。因此也就比单纯的数组具有更加灵活的结构！

顺序表在C++的标准模板库中的实现

相应在C++的STL标准模板库中的实现是模板 vector：

<span style="font-size:18px;">template <
   class Type, 
   class Allocator = allocator<Type> 
>
class vector</span>

当中。Type是vector中存储的数据类型。使用时要包含头文件<vector>和命名空间std。

vector模板类中使用的数据类型

首先先认识一下vector模板类中最常使用的数据类型：

iterator 迭代器

用来提供对vector中元素随机訪问的一个数据类型，可读可改动。

const_iterator 常量迭代器

详细使用例如以下：

<span style="font-size:18px;">// vector_begin.cpp
// compile with: /EHsc
#include <vector>
#include <iostream>

int main()
{
    using namespace std;
    vector<int> c1;
    vector<int>::iterator c1_Iter;
    vector<int>::const_iterator c1_cIter;

    c1.push_back(1);
    c1.push_back(2);

    cout << "The vector c1 contains elements:";
    c1_Iter = c1.begin();
    for (; c1_Iter != c1.end(); c1_Iter++)
    {
        cout << " " << *c1_Iter;
    }
    cout << endl;

    cout << "The vector c1 now contains elements:";
    c1_Iter = c1.begin();
    *c1_Iter = 20;
    for (; c1_Iter != c1.end(); c1_Iter++)
    {
        cout << " " << *c1_Iter;
    }
    cout << endl;

    // The following line would be an error because iterator is const
    // *c1_cIter = 200;
}</span>

vector模板类的成员函数

assign 

<span style="font-size:18px;">// vector_assign.cpp
// compile with: /EHsc
#include <vector>
#include <iostream>

int main( )
{
   using namespace std;
   vector<int> v1, v2, v3;
   vector<int>::iterator iter;

   v1.push_back(10);
   v1.push_back(20);
   v1.push_back(30);
   v1.push_back(40);
   v1.push_back(50);

   cout << "v1 = " ;
   for (iter = v1.begin(); iter != v1.end(); iter++)
      cout << *iter << " ";
   cout << endl;

   v2.assign(v1.begin(), v1.end());
   cout << "v2 = ";
   for (iter = v2.begin(); iter != v2.end(); iter++)
      cout << *iter << " ";
   cout << endl;

   v3.assign(7, 4) ;
   cout << "v3 = ";
   for (iter = v3.begin(); iter != v3.end(); iter++)
      cout << *iter << " ";
   cout << endl;
}</span>

v1 = 10 20 30 40 50 
v2 = 10 20 30 40 50 
v3 = 4 4 4 4 4 4 4

front和back 

<span style="font-size:18px;">// vector_back.cpp
// compile with: /EHsc
#include <vector>
#include <iostream>

int main() {
   using namespace std;   
   vector <int> v1;
   
   v1.push_back( 10 );
   v1.push_back( 11 );

   int& i = v1.back( );
   const int& ii = v1.front( );

   cout << "The last integer of v1 is " << i << endl;
   i--;
   cout << "The next-to-last integer of v1 is "<< ii << endl;
}</span>

The last integer of v1 is 11
The next-to-last integer of v1 is 10

其它操作函数