迭代器（iterator）
C++中的類模板（class template）與函數(shù)模板（funtion template）可以分別獨立完成數(shù)據(jù)容器（containers）和算法（algorithms）的設(shè)計飞涂，這樣就分別實現(xiàn)了容器與算法的泛型化较店，而這兩者之間的連接起來則依靠迭代器（iterators）實現(xiàn)容燕，因此一種算法可以通過迭代器的粘合而作用到不同的容器上梁呈。以下為應(yīng)用迭代器的簡單示例：
template <class InputIterator, class T>
InputIterator find(InputIterator first,
InputIterator last,
const T& value) {
while (first != last && *first != value) {
first++;
}
return first;
}
每種容器都有其對應(yīng)的迭代器官卡，下面定義的三種容器均有自身對應(yīng)的迭代器醋虏，上述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），因此可以像指針一樣進行內(nèi)容提領(lǐng)（deference）和成員訪問（member access）這兩項工作熔脂。
特性（traits）
算法中運用迭代器時，可能會用到其關(guān)聯(lián)型別（associated type）霞揉，包括以下五種：
- value_type
- difference_type
- pointer
- reference
- iterator_category
其中 value_type 是迭代器所指對象的型別晰骑。假設(shè)算法中需要聲明一個以 value_type 為型別的變量，由于沒有C++不支持 typeof()硕舆，且 RTTI 中的 typeid()只能獲取型別名稱，不能用于變量聲明扬跋，所以需要采取特定的解決方法凌节。第一種可供考慮的解決方案就是利用函數(shù)模板的參數(shù)推導（argument deducation）機制 ，程序示例如下：
template <class I, class T>
void func_impl(I iter, T t) {
T tmp; // T 就是迭代器所指對象的型別倍奢，以此解決了上述問題
... // 這里做原本 func( ) 應(yīng)該做的工作
}
template <class I>
inline
void func(I iter) {
func_impl(iter, *iter);
}
int main() {
int i;
func(&i);
}
如果需要以 value_type 作為函數(shù)返回值，則上述函數(shù)的參數(shù)推導機制將失效痪宰，此時可考慮聲明內(nèi)嵌型別來解決：
template <class T>
struct MyIter {
typedef T value_type; // 內(nèi)嵌型別聲明（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
當?shù)鞑皇?class type畔裕，而是原生指針時，上述方法再次失效柴钻。此時可考慮用一個專門的 class template 來萃取迭代器的特性，并且以模板偏特化來應(yīng)對獲取原生指針的型別的問題：
template <class I>
struct iterator_traits {
typedef typename I::value_type value_type;
};
應(yīng)對原生指針的特化版本如下：
template <class T>
struct iterator_traits<T*> {
typedef T value_type;
};
運用模板類 iterator_traits 之后靠粪，函數(shù) func 可以寫成如下形式：
template <class I>
typename iterator_traits<I>::value_type
func(I ite) {
return *ite;
}
Vector
Vector 是能夠存放任意型別的動態(tài)數(shù)組毫蚓，在內(nèi)存中是一段地址連續(xù)的空間，支持動態(tài)空間大小調(diào)整元潘，隨著元素的加入，vector 內(nèi)部會自動擴充內(nèi)存空間牲距。
- 創(chuàng)建 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 中元素
- 調(diào)用 vector::at()牍鞠，進行邊界檢查
- 調(diào)用 vector::operator[]，不進行邊界檢查
- 從 Vector 中刪除元素
- 清除整個 vector：clear
- 彈出 vector 尾部元素：pop_back
- 刪除 vector 中某一位置元素：erase
// 指定 iterator 處刪除某一元素
std::vector<int>::const_iterator it = v.begin();
v.erase(it + 1); //刪除第二個元素
// 通過某一條件函數(shù)找到 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 是一個能存放任意型別的雙向隊列萤晴，其提供的函數(shù)與 vector 類似胁后，采用了與 vector 不同的內(nèi)存管理方式：大塊分配內(nèi)存。Deque 新增了兩個函數(shù)：
- 在頭部插入元素：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）
- 優(yōu)點：
- 不使用連續(xù)內(nèi)存完成動態(tài)操作侣诺；
- 對于插入、刪除和替換等需要重排序列的操作剃氧，效率極高；
- 可在兩端隨意進行插入朋鞍、刪除操作妥箕；
- 缺點：
- 不能進行內(nèi)部的隨機訪問，即不像 vector 那樣支持 operator [] 和vector.at()畦幢；
- 相對于verctor占用內(nèi)存多。
- 創(chuàng)建 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()黍瞧，內(nèi)部調(diào)用 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 );
