四、模板特性 … 7.编译模型 … 导出模型：通过export关键字，将模板声明为导出，这样编译器在对模板进行一次编译时会将该模板内部表示，缓存在.o文件中，等到链接阶段，在结合实例化该模板的具体类型，补充做二次编译，得到相应的具体函数和具体类，最后完成二进制代码的链接。但是，很遗憾，目前阶段大部分C++编译器都不支持这种做法。因此，多数情况下依然采用包含模型或者预实例化模型，解决模板的分离编译问题。 代码：exp/ cmp.h
// 声明 export template<typename T> T const& min(T const& x, T const& y); export template<typename T> T const& max(T const& x, T const& y); export template<typename T> class Comparator { public: Comparator(T const& x, T const& y); T const& min(void) const; T const& max(void) const; private: T const& m_x; T const& m_y; };cmp.cpp
// 实现 #include "cmp.h" template<typename T> T const& min(T const& x, T const& y) { return x < y ? x : y; } template<typename T> T const& max(T const& x, T const& y) { return x < y ? y : x; } template<typename T> Comparator<T>::Comparator(T const& x, T const& y) : m_x(x), m_y(y) {} template<typename T> T const& Comparator<T>::min(void) const { return m_x < m_y ? m_x : m_y; } template<typename T> T const& Comparator<T>::max(void) const { return m_x < m_y ? m_y : m_x; }use.cpp
// 使用 #include <iostream> using namespace std; #include "cmp.h" int main(void) { int a = 123, b = 456; double c = 1.23, d = 4.56; string e = "world", f = "hello"; cout << ::min(a, b) << ' ' << ::max(a, b) << endl; cout << ::min(c, d) << ' ' << ::max(c, d) << endl; cout << ::min(e, f) << ' ' << ::max(e, f) << endl; Comparator<int> ci(a, b); cout << ci.min() << ' ' << ci.max() << endl; Comparator<double> cd(c, d); cout << cd.min() << ' ' << cd.max() << endl; Comparator<string> cs(e, f); cout << cs.min() << ' ' << cs.max() << endl; return 0; }8.预编译头文件 提升编译速度的技巧。 将一些公用头文件，或者是包含大量与模板实现有关的代码，放到一个独立的.h文件中，将该.h文件单独编译为一个.gch文件，即预编译头文件。编译任何包含此独立头文件的cpp文件时，都不再编译头文件，而是直接从.gch文件中读取内容，以此减少对相同代码重复编译的次数，提升编译速度，缩短编译时间。 代码：hello.h、hello.cpp 注意，一旦修改了与预编译头文件有关的文件内容，一定要重新编译生成预编译头文件，以反映所作出的改变。 五、容器、迭代器和泛型算法 容器：双向线性链表容器 迭代器：正向可写迭代器 泛型算法：线性查找算法 代码：list.cpp
#include <cstring> #include <iostream> #include <stdexcept> using namespace std; // 双向线性链表容器 template<typename T> class List { public: // 构造器、析构器、拷贝构造器、 // 拷贝赋值运算符 List(void) : m_head(NULL), m_tail(NULL) {} ~List(void) { clear(); } List(List const& that) : m_head(NULL), m_tail(NULL) { for (Node* node = that.m_head; node; node = node->m_next) push_back(node->m_data); } List& operator=(List const& that) { if (&that != this) { List list(that); swap(m_head, list.m_head); swap(m_tail, list.m_tail); } return *this; } // 获取首元素 T& front(void) { if (empty()) throw underflow_error( "链表下溢！"); return m_head->m_data; } T const& front(void) const { return const_cast<List&>( *this).front(); } // 向首部压入 void push_front(T const& data) { m_head = new Node(data, NULL, m_head); if (m_head->m_next) m_head->m_next->m_prev = m_head; else m_tail = m_head; } // 从首部弹出 void pop_front(void) { if (empty()) throw underflow_error( "链表下溢！"); Node* next = m_head->m_next; delete m_head; m_head = next; if (m_head) m_head->m_prev = NULL; else m_tail = NULL; } // 获取尾元素 T& back(void) { if (empty()) throw underflow_error( "链表下溢！"); return m_tail->m_data; } T const& back(void) const { return const_cast<List&>( *this).back(); } // 向尾部压入 void push_back(T const& data) { m_tail = new Node(data, m_tail); if (m_tail->m_prev) m_tail->m_prev->m_next = m_tail; else m_head = m_tail; } // 从尾部弹出 void pop_back(void) { if (empty()) throw underflow_error( "链表下溢！"); Node* prev = m_tail->m_prev; delete m_tail; m_tail = prev; if (m_tail) m_tail->m_next = NULL; else m_head = NULL; } // 删除所有匹配元素 void remove(T const& data) { for (Node* node = m_head, *next; node; node = next) { next = node->m_next; if (node->m_data == data) { if (node->m_prev) node->m_prev->m_next = node->m_next; else m_head = node->m_next; if (node->m_next) node->m_next->m_prev = node->m_prev; else m_tail = node->m_prev; delete node; } } } // 清空 void clear(void) { for (Node* next; m_head; m_head = next) { next = m_head->m_next; delete m_head; } m_tail = NULL; } // 判空 bool empty(void) const { return m_head == NULL && m_tail == NULL; } // 大小 size_t size(void) const { size_t nodes = 0; for (Node* node = m_head; node; node = node->m_next) ++nodes; return nodes; } // 插入流 friend ostream& operator<<(ostream& os, List const& list) { for (Node* node = list.m_head; node; node = node->m_next) os << *node; return os; } private: // 节点 class Node { public: // 构造器 Node(T const& data, Node* prev = NULL, Node* next = NULL) : m_data(data), m_prev(prev), m_next(next) {} // 插入流 friend ostream& operator<<( ostream& os, Node const& node) { return os << '(' << node.m_data << ')'; } T m_data; // 数据 Node* m_prev; // 前指针 Node* m_next; // 后指针 }; Node* m_head; // 头指针 Node* m_tail; // 尾指针 }; // 测试用例 void test1 (void) { List<int> list; cout << list << endl; // 空 list.push_front(30); list.push_front(20); list.push_front(10); cout << list << endl; // 10 20 30 --list.front(); cout << list << endl; // 9 20 30 List<int> const& cr = list; cout << cr.front() << endl; // 9 //cr.front()++; list.pop_front(); cout << list << endl; // 20 30 list.push_back(40); list.push_back(50); list.push_back(60); cout << list << endl; // 20 30 40 50 60 list.back()++; cout << list << endl; // 20 30 40 50 61 List<int> const* cp = &list; cout << cp->back() << endl; // 61 //--cp->back(); list.pop_back(); cout << list << endl; // 20 30 40 50 } void test2(void) { List<int> l1; l1.push_back(10); l1.push_back(20); l1.push_back(30); List<int> l2 = l1; // 拷贝构造 cout << "l1: " << l1 << endl; cout << "l2: " << l2 << endl; ++l1.front(); ++l2.back(); cout << "l1: " << l1 << endl; cout << "l2: " << l2 << endl; l1 = l2; // 拷贝赋值 cout << "l1: " << l1 << endl; cout << "l2: " << l2 << endl; ++l1.front(); ++l2.back(); cout << "l1: " << l1 << endl; cout << "l2: " << l2 << endl; } void test3(void) { int a[] = {10, 20, 30, 20, 40, 20, 50, 20, 20, 60}; List<int> list; for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i) list.push_back(a[i]); cout << list << endl; list.remove(20); cout << list << endl; } int main(void) { //test1(); //test2(); test3(); return 0; }六、标准模板库(STL) 1.主要内容 1)容器 A.线性容器：向量(vector)、双端队列(deque)、列表(list) B.适配器容器：堆栈(stack)、队列(queue)、优先队列(priority_queue) C.关联容器：映射(map)、多重映射(multimap)、集合(set)、多重集合(multiset) 2)迭代器： A.成员迭代器：正向和反向、可写和只读、随机和顺序 B.全局迭代器：插入迭代器、IO流迭代器 3)泛型算法 查找、排序、拆分、合并、交换、遍历，等等 2.向量(vector) 1)基本特性和实例化 向量中的元素被存储在一段连续的内存空间中，通过下标随机访问向量中的元素，其效率等价于数组。 向量的内存空间会随着新元素的加入而自动增长。 内存空间的连续性不会妨碍向量元素的持续增加。 在创建向量的时候，也可以提前预分配内存空间，只要这些空间够用就不再分配新的内存空间，除非使用用发现不够用了，再自动扩充内存。 #include vector<元素类型> 向量对象; vector vi; 空向量，占内存。 vector<元素类型> 向量对象(初始大小); vector vi(5); // 0 0 0 0 0 vector<元素类型> 向量对象(初始大小, 初值); vector vi(5, 10); // 10 10 10 10 10 vector<元素类型> 向量对象(起始迭代器, 终止迭代器); 凡是用起始迭代器和终止迭代器表示容器中的元素范围，终止迭代器时范围中最后一个元素的下一个位置的迭代器： [起始迭代器, 终止迭代器) 1 2 3 4 5 6 7 ^ ^ | | 起始 终止 -> 2 3 4 5 代码：vec1.cpp
#include <iostream> #include <vector> using namespace std; void print(vector<int> const& vec) { cout << "容量：" << vec.capacity() << endl; cout << "大小：" << vec.size() << endl; cout << "字节：" << sizeof(vec) << endl; cout << "元素："; for (size_t i = 0; i < vec.size(); ++i) cout << vec[i] << ' '; cout << endl; } int main(void) { vector<int> v1; print(v1); vector<int> v2(5); print(v2); vector<int> v3(5, 10); print(v3); v3.push_back(20); print(v3); int a[] = {1, 2, 3, 4, 5, 6, 7}; vector<int> v4(&a[2], &a[5]); print(v4); vector<int> v5(&a[0], &a[7]); print(v5); return 0; }2)迭代器 连续内存的容器->随机迭代器->处理顺序迭代器提供的功能以外还支持与整数的加减法运算，以及同类型迭代器之间的大小比较和减法运算。 iterator: 正向可写迭代器 const_iterator: 正向只读迭代器 reverse_iterator: 反向可写迭代器 const_reverse_iterator: 反向只读迭代器
