Essential C++【读书笔记 思考总结】

3 泛型编程风格 Generic Programming

STL的主要组件：Container，generic algorithm。

顺序容器：顺序迭代访问。
关联容器：通过key访问。

map：key/value，key用来查找，value用来存储数据。
set：只有key。

通过 function template 实现 generic algorithm。
通过iterator 实现 Container 无关。
通过 template 实现 Container 元素类型无关。

3.1 指针的算术运算

vector 中查找元素：

#include <iostream>
#include <vector>using namespace std;void myFind(const vector<int>& vec, const int & value)
{for (int ix = 0; ix < vec.size(); ++ix){if (value == vec[ix]){cout << "find success:" <<vec[ix] << endl;return;}}cout << "find fail" << endl;
}int main()
{vector<int> vi;vi.push_back(1);vi.push_back(2);vi.push_back(3);myFind(vi, 2);return 0;
}

运行结果：

想办法让这个函数不仅可以处理整数，更可以处理任何类型——前提是该类型定义有equality（相等）运算符。

#include <iostream>
#include <vector>
#include <string>using namespace std;template<typename elemType>
void myFind(const vector<elemType>& vec, const elemType & value)
{for (int ix = 0; ix < vec.size(); ++ix){if (value == vec[ix]){cout << "find success:" <<vec[ix] << endl;return;}}cout << "find fail" << endl;
}int main()
{vector<int> vi;vi.push_back(1);vi.push_back(2);vi.push_back(3);myFind(vi, 2);vector<string> vs;vs.push_back("11");vs.push_back("22");vs.push_back("33");string s1 = "22";myFind(vs, s1);return 0;
}

让一个函数同时可以处理vector与array内的任意类型元素——当然该类型的equality运算符皆已定义。

#include <iostream>
#include <vector>
#include <string>
#include <iterator> using namespace std;template<typename elemType>
void myFind(const elemType* first, const elemType* last, const elemType& value) // 重命名为myFind
{if (!first || !last)return;for (; first != last; ++first){if (*first == value){cout << "find success:" << *first << endl;return;}}cout << "find fail" << endl;
}int main()
{int array[5] = { 1,2,3,4,5 };myFind(array, array + 5, 1);vector<int> vi;vi.push_back(11);vi.push_back(22);vi.push_back(33);myFind(vi.data(), vi.data() + vi.size(), 22);vector<string> vs;vs.push_back("111");vs.push_back("222");vs.push_back("333");string s1 = "333";myFind(vs.data(), vs.data() + vi.size(), s1);return 0;
}

数组的函数传参和函数返回，只有数组的第一个元素地址会被传递。

下标操作：起始地址 +索引 产生新地址，新地址提领获取对象。

指针算术运算中，需要考虑指针类型。

问题：如何扩展 myFind（）的功能，令它也能支持标准库所提供的 list 类别？
通过抽象，封装底层指针操作，一个 find实现所有容器的查找功能。

3.2 了解 Iterator（泛型指针）

如何取得iterator呢？
标准容器begin（）函数，返回指向第一个元素的iterator。
标准容器end（）函数，会返回指向最后一个元素的下一位置的iterator。

#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <list>using namespace std;template<typename IteratorType, typename elemType>
IteratorType myFind(IteratorType first, IteratorType last, const elemType& value) // 重命名为myFind
{for (; first != last; ++first){if (*first == value){cout << "find success:" << *first << endl;return first;}}cout << "find fail" << endl;return last;
}int main()
{int array[5] = { 1,2,3,4,5 };myFind(array, array + 5, 1);vector<int> vi;vi.push_back(11);vi.push_back(22);vi.push_back(33);// 使用begin和end函数来调用myFindmyFind(vi.begin(), vi.end(), 22);vector<string> vs;vs.push_back("111");vs.push_back("222");vs.push_back("333");string s1 = "333";// 使用begin和end函数来调用myFindmyFind(vs.begin(), vs.end(), s1);list<string> ls;ls.push_back("1111");ls.push_back("2222");ls.push_back("3333");ls.push_back("4444");string s2 = "4444";myFind(ls.begin(), ls.end(), s2);return 0;
}

现在的 myFind支持一对指针或一对容器的迭代器，同时支持 array，list，vector，有了更大的通用性。

问题：如果容器元素不支持相等运算符，或者用户想用其他条件find，如何增加弹性？

3.3 所有容器的共通操作

• ==
• !=
• =
• empty()
• size()
• clear()
• begin()
• end()
• insert()
• erase()