STL标准模板库

 

STL标准模板库中的底层数据结构是什么？STL模板提供：容器、迭代器、算法

1>  容器：用于管理对象集合

2>  迭代器：用于对象群集中遍历所有元素

3>  算法：用来搜所、排序、修改、使用群集元素。

STL中的通用容器：

1>  序列容器：vector（底层结构为数据）、list（双向循环状列表）、deque（队列FIFO先进先出线性表支持[]操作）

2>  关联容器：set、map（底层都为红黑树即自平衡二叉树）

3>  适配器：stack、queue、priory_queue（底层为序列容器中的某个）

STL迭代器：

1>  iterator：读写型

2>  const_iterator：只读型

STL常用算法：

1>  sort()

2>  find()

3>  reverse()

4>  copy()

1、Vector容器：底层数据结构为数组，是连续内存，支持[]操作，支持尾部操作push_back()

// Vector.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include

#include

#include

#include

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

       //vector iVct(11,9);   //vector 声明

       vector<int> iVct;

       vector<int>::iterator iT;   //迭代器声明

       int i=0;

       iVct.reserve(10);           //预留内存：reserve（10）

       cout<<"iVct.size()="<

       cout<<"use [] get data:"<

       for(i=1;i<=6;++i)

       {

              iVct.push_back(i);       //底层结构为数组类型，支持尾部快速插入

       }

       for(i=0;i

       {

              cout<"-";       //取址符：[]

       }

       cout<

       iVct.pop_back();              //在末尾增加元素：iVct.pop_back()

       iT = iVct.begin();            //迭代器赋址：iVct.begin()

       iVct.insert(iT+2,88);         //通过迭代器中间插入：insert

       //remove(iVct.begin(),iVct.end(),4);

       cout<<"use iterator get data:"<

       for(iT = iVct.begin();iT!=iVct.end();++iT)     //通过迭代器访问vector,

//数组型的容器可使用iT或iT!=iVct.end()

       {

              cout<<*iT<<"-";

       }

       cout<

       cout<<"use [] get data:"<

       for(i=0;i                   //通过取址符访问vector

       {

              cout<"-";                      //取址符：[]

       }

       cout<

       cout<<"capacity ="<   //预留内存：capacity

       cout<<"size ="<

       cout<<"assign data:"<

       iVct.clear();

       iVct.assign(10,8);                           //数值赋值操作：assign

       for(i=0;i

       {

              cout<"-";

       }

       cout<

       cout<<"iterator assign data:"<

       vector<int> iVct2;

       iT = iVct.begin();

       iVct2.assign(iT+1,iVct.end()-1);            //使用迭代器赋值操作：assign

       for(i=0;i

       {

              cout<"-";

       }

       cout<

       system("pause");

       return 0;

}

2、List容器：底层数据结构为双向环状链表，非连接内存不支持[]操作，支持任意位置增加删除。

// List.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include

#include

#include

#include

using namespace std;   //命名空间

int _tmain(int argc, _TCHAR* argv[])

{

       list<char> cList;

       for(char i='a';i<='z';++i)

       {

              cList.push_back(i);

       }

       list<char>::const_iterator pos;

       cout<<"use const_iterator show data:"<

       //通过迭代器访问list,数组型的容器可使用iT或iT!=iVct.end(),此处只能使用pos!=cList.end()

       for(pos=cList.begin();pos!=cList.end();++pos)     

       {

              cout<<*pos<<"-";

       }

       cout<

       system("pause");

       return 0;

}

3、Deque容器：底层数据结构为队列，连续内存，支持头部和尾部操作，支持[]，为FIFO先入先出线性列表，队头只允许删除，队尾只允许增加。

// deque.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include

#include

#include

#include

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

       deque<float> deq;

       deque<float>::iterator pos;

       for(int i=1;i<=6;++i)

       {

              //deq.push_front(i*1.2);

              deq.push_back(i*1.2);

       }

       cout<<"use const_iterator show data:"<

       //通过迭代器访问list,数组型的容器可使用iT或iT!=iVct.end()

       for(pos=deq.begin();pos!=deq.end();++pos)     

       {

              cout<<*pos<<"-";

       }

       cout<

       system("pause");

       return 0;

}

4、set/multiset关联容器：底层数据结构为红黑树（自平衡二叉树），内部元素按键值大小时自动排列。

// Set.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include

#include

#include

#include

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

       set<int> iSet;

       set<int>::iterator p;

      

       iSet.insert(3);

       iSet.insert(35);

       iSet.insert(2);

       iSet.insert(5);

       iSet.insert(345);

       iSet.insert(34);

        

       for(p = iSet.begin();p!=iSet.end();++p)

       {

              cout<<*p<<"-";

       }

       cout<

       system("pause");

       return 0;

}

5、map/multimap关联容器：底层数据结构为红黑树（自平衡二叉树），内部元素按键值大小时自动排列，map提供下标访问操作。

// map.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include

#include

#include

#include

using namespace std;

struct ltstr

{

       bool operator()(const char* s1,const char*s2)const

       {

              return strcmp(s1,s2)<0;

       }

};

void Test1MutliMap()

{

       multimap<int,const char*> m;

       multimap<int,const char*>::iterator pos;

       m.insert(m.begin(),pair<int, const char*>(1,"e"));

       //pair：一种含两个数的模板类型，如 pair("a",1)

       m.insert(pair<int, const char*>(21,"a"));

       m.insert(pair<int, const char*>(2,"a"));

       m.insert(pair<int, const char*>(9,"h"));

       m.insert(pair<int, const char*>(5,"c"));

       m.insert(m.begin(),pair<int, const char*>(2,"g"));

       //键值统计

       cout<<"Number of elements 9:"<

       cout<<"Number of elements 2:"<

       //遍历

       cout<<"elements in m:"<

       for(pos=m.begin();pos!=m.end();++pos)

       {

              cout<<(*pos).first<<"-"<<(*pos).second<

       }

}

void Test2MutliMap(void)

{

       multimap<const char*, int, ltstr> m;

       multimap<const char*, int, ltstr>::iterator pos;

       m.insert(m.begin(),pair<const char*,int>("e",1));

       //pair：一种含两个数的模板类型，如 pair("a",1)

       m.insert(pair<const char*,int>("a",21));

       m.insert(pair<const char*,int>("a",2));

       m.insert(pair<const char*,int>("h",5));

       m.insert(pair<const char*,int>("c",6));

       m.insert(m.begin(),pair<const char*,int>("g",20));

      

       //键值统计

       cout<<"Number of elements a:"<"a")<

       cout<<"Number of elements b:"<"b")<

       //遍历

       cout<<"elements in m:"<

       for(pos=m.begin();pos!=m.end();++pos)

       {

              cout<<(*pos).first<<"-"<<(*pos).second<

       }

}

int _tmain(int argc, _TCHAR* argv[])

{

       //数字做为key_value

       Test1MutliMap();

       //字符串做为key_value

       Test2MutliMap();

       system("pause");

       return 0;

}