迭代器（iterator）
C++中的类模板（class template）与函数模板（funtion template）可以分别独立完成数据容器（containers）和算法（algorithms）的设计，这样就分别实现了容器与算法的泛型化，而这两者之间的连接起来则依靠迭代器（iterators）实现，因此一种算法可以通过迭代器的粘合而作用到不同的容器上。以下为应用迭代器的简单示例：
template <class InputIterator, class T>
InputIterator find(InputIterator first,
InputIterator last,
const T& value) {
while (first != last && *first != value) {
first++;
}
return first;
}
每种容器都有其对应的迭代器，下面定义的三种容器均有自身对应的迭代器，上述find 算法通过迭代器而能适用于不同的容器。
std::vector<int> v(...)
std::list<int> l(...)
std::deque<int> d(...)
...
std::vector<int>::iterator itv = find(v.begin(), v.end(), value)
std::list<int>::iterator itl = find(l.begin(), l.end(), value)
std::deque<int>::iterator itd = find(d.begin(), d.end(), value)
迭代器是一种行为类似指针的对象，迭代器这种类里面对 operator* 和 operator->进行了重载（overloading），因此可以像指针一样进行内容提领（deference）和成员访问（member access）这两项工作。
特性（traits）
算法中运用迭代器时，可能会用到其关联型别（associated type），包括以下五种：
- value_type
- difference_type
- pointer
- reference
- iterator_category
其中 value_type 是迭代器所指对象的型别。假设算法中需要声明一个以 value_type 为型别的变量，由于没有C++不支持 typeof()，且 RTTI 中的 typeid()只能获取型别名称，不能用于变量声明，所以需要采取特定的解决方法。第一种可供考虑的解决方案就是利用函数模板的参数推导（argument deducation）机制 ，程序示例如下：
template <class I, class T>
void func_impl(I iter, T t) {
T tmp; // T 就是迭代器所指对象的型别，以此解决了上述问题
... // 这里做原本 func( ) 应该做的工作
}
template <class I>
inline
void func(I iter) {
func_impl(iter, *iter);
}
int main() {
int i;
func(&i);
}
如果需要以 value_type 作为函数返回值，则上述函数的参数推导机制将失效，此时可考虑声明内嵌型别来解决：
template <class T>
struct MyIter {
typedef T value_type; // 内嵌型别声明（nested type）
T* ptr;
MyIter(T* p = 0) : ptr(p) { }
T& operator*() const { return *ptr; }
...
};
template <class I>
typename I::value_type // 用 typename 声明 func 的返回值型别
func(I ite) {
return *ite;
}
...
MyIter<int> ite(new int(8));
cout << func(ite); // 输出：8
当迭代器不是 class type，而是原生指针时，上述方法再次失效。此时可考虑用一个专门的 class template 来萃取迭代器的特性，并且以模板偏特化来应对获取原生指针的型别的问题：
template <class I>
struct iterator_traits {
typedef typename I::value_type value_type;
};
应对原生指针的特化版本如下：
template <class T>
struct iterator_traits<T*> {
typedef T value_type;
};
运用模板类 iterator_traits 之后，函数 func 可以写成如下形式：
template <class I>
typename iterator_traits<I>::value_type
func(I ite) {
return *ite;
}
Vector
Vector 是能够存放任意型别的动态数组，在内存中是一段地址连续的空间，支持动态空间大小调整，随着元素的加入，vector 内部会自动扩充内存空间。
- 创建 Vector
std::vector<T> v;
std::vector<T> v(n); // 容量为 n
std::vector<T> v(n, i) // 容量为 n，均初始化为 i
std::vector<T> copyOfV(v)
int array[] = {1,2,3,4,5,6,7,8,9,10}; std::vector<T> v(array, array + 10);
- 向 Vector 中添加元素
std::vector<std::wstring> v3;
for (std::size_t i = 0; i < 10; i++) {
std::wstringstream wss;
wss << TEXT("String[") << i << TEXT("]");
v3.push_back(wss.str());
}
- 判断 Vector 是否为空
std::vector<std::wstring> v3;
bool isEmpty = v3.empty();
- 获取 Vector 的大小
int array[] = {1,2,3,4,5,6,7,8,9,10};
std::vector<int> v(array, array + 10);
std::size vSize = v.size();
- 访问 Vector 中元素
- 调用 vector::at()，进行边界检查
- 调用 vector::operator[]，不进行边界检查
- 从 Vector 中删除元素
- 清除整个 vector：clear
- 弹出 vector 尾部元素：pop_back
- 删除 vector 中某一位置元素：erase
// 指定 iterator 处删除某一元素
std::vector<int>::const_iterator it = v.begin();
v.erase(it + 1); //删除第二个元素
// 通过某一条件函数找到 vector 中需要删除的元素
struct ContainString: public std::unary_function<std::wstring, bool> {
ContainString(const std::wstring& wszMatch): m_wszMatch(wszMatch) { }
bool operator() (const std::wstring& wszStringToMatch) const {
return (wszMatchToMatch.find(m_wszString) != -1);
}
std::wstring m_wszString;
}
v.erase(std::remove_if(v.begin(), v.end(), ContainsString(L"C++")), v.end());
Deque
Deque 是一个能存放任意型别的双向队列，其提供的函数与 vector 类似，采用了与 vector 不同的内存管理方式：大块分配内存。Deque 新增了两个函数：
- 在头部插入元素：push_front
- 在尾部弹出元素：pop_front
- 中间位置插入元素
dqInt.insert(dqInt.begin() + 1, 9); // 在第二个元素之前插入9 - 前向遍历与反向遍历
// 前向遍历
deque<int>::iterator i, iend;
iend = dqInt.end();
for (i = dqInt.begin(); i != iend; ++i) {
cout << *i << " ";
}
cout << endl;
// 反向遍历
deque<int>::reverse_iterator ri, riend;
riend = dqInt.rend();
for(ri = dqInt.rbegin(); ri != riend; ++ri) {
cout << *ri < " ";
}
cout << endl;
List
List 是一个能存放任意型别的双向链表（doubly linked list）。
- 可以向链表中接入一个子链表（sub-list）
- 优点：
- 不使用连续内存完成动态操作；
- 对于插入、删除和替换等需要重排序列的操作，效率极高；
- 可在两端随意进行插入、删除操作；
- 缺点：
- 不能进行内部的随机访问，即不像 vector 那样支持 operator [] 和vector.at()；
- 相对于verctor占用内存多。
- 创建 list
std::list<int> l;
std::list<int> l(n); // 容量为 n
std::list<int> l(n, x); // 容量为 n，均初始化为 x
std::list<int> copyOfList(l);
std::wstring array[] = {TEXT("Str-1"), TEXT("Str-2"), TEXT("Str-3")};
std::list<std::wstring> l(array, array+3);
- 向 list 添加元素
std::list<std::wstring> l;
l.push_back(TEXT("Some text pushed at back"));
l.push_front(TEXT("Some text pushed at front"));
- 判断 list 是否为空
std::list<std::wstring> l;
bool isEmpty = l.empty();
- 获取 list 大小
std::wstring array[] = {TEXT("Str-1"), TEXT("Str-2"), TEXT("Str-3")};
std::list<std::wstring> l(array, array+3);
std::size listSize = l.size();
- 删除 list 中元素
- 清除整个 list：clear()，内部调用 erase(begin(), end())
- 弹出 list 尾部元素：pop_back()
- 弹出 list 头部元素：pop_front()
- 删除 list 中指定元素：erase(), remove()，remove_if()
- 向 list 中插入元素
std::list<std::wstring>::const_iterator it = l.begin();
l.insert(it, anotherList.begin(), anotherList.end());
- 粘接 list：splice
// position为目标 list 位置，x 为源 list，first 与 last 限定源的范围
void splice ( iterator position, list<T, Allocator>& x );
void splice ( iterator position, list<T, Allocator>& x, iterator i );
void splice ( iterator position, list<T, Allocator>& x,
iterator first, iterator last );
