全部博文（2759）
分类： C/C++
2014-02-21 13:04:46
原文地址：STL标准模板库 作者：Embedded_Li
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 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 { cout<<*iT<<"-"; }
cout<
cout<<"use [] get data:"<
for(i=0;i {
cout< }
cout<
cout<<"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 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 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 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 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:"<
cout<<"Number of elements 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; } |
