c++模板：容器list、vector

c++模板容器

• 类型模板
• • 实例化
  • 方法（函数）模板
• 泛型编程
• • 概述
  • 关联特性Traits
  • 迭代器iterator
• 容器
• • 动态数组vector
  • 队列deque
  • 链表list

模板是c++的特性，通过泛型实现。主要有两种表现形式：类型模板、和方法模板。

类型模板 实例化

• 显示实例化，初始化告诉类型。
• 隐示实例化，根据参数判别。

方法（函数）模板

参数化的一族函数（A family of function)
模板会被编译两次，第一次检查语法，第二次实例化期间检查调用是否合法。
模板实例化，如果需要不一样的类型，显示指定T的型别为长精度的类型，或者可以使用static_cast强制转换为不会丢失精度的类型，如：

Max<double>(1,2.0);
Max(static_cast<double>(1),2.0);

泛型编程 概述

• to-be-specified-later
• c++,Java，c#等OO language 都支持泛型编程思想
• c++泛型思想是通过模板及相关特性表现的。

关联特性Traits

associate关联的型别，可以看做型别T的一种特性.

template <typename T>
inline typename SigmaTraits<T> :: ReturnType Sigma(const T const *start,const T const *end){

	typedef typename SigmaTraits<T> :: ReturnType ReturnType;
	ReturnType rs = ReturnType();
	while(start!=end){
		rs += *start++;
	}
	return rs;
}

迭代器iterator

迭代器是指泛化的指针。
STL中迭代器是容器与算法之间的接口，分离容器与算法，粘合容器与算法。

template <typename _itr, typename _ty>
inline _itr find(_itr start, _itr end, _ty _val){
	while(start!=end)
	{
		if(*start==_val){
			return start;
		}else{
			start++;
		}
	}
}

容器

c++ STL 容器主要有vector、list、set、map、deque、queue、stack，现主要介绍两种

动态数组vector

vector和array的区别在于，array的数量是固定的栈内存，而vector是可以动态 *** 作的堆内存。

• 添加元素 .push_back(T)
• 访问元素v[0]效率高，不做越界处理，可能出现越界访问；.at(0)越界抛异常，效率低一些。
• 删除元素.erase(it+1)，删除尾部元素.pop_back()， 批量删除.erase(myint.begin(),myint.end()-1);

队列deque

和vector很像。双向队列，增加了从头部插入和删除的方法：push_front(T),pop_front(T)

链表list

双向的链表。list *** 作添加、删除都只是指针指向的内存地址的改变，不需要复制内存，非常迅速。但是查找和随机存储比较慢。

• 添加元素push_front(T)、push_back(T)
• 判断是否为空empty()或者变量size()
• 删除元素，除了前删后删pop_back(T)、pop_front(T)，还可以删除指定元素remove(T)，删除指定位置的元素.erase(it+1)
• 粘接list2.splice(list1.begin(),list2):讲list2粘接到list1的头部，同时情况list2；