c++标准库体系结构与内核分析
第一讲：示范运用STL各大部件 (components)，并初步认识其体系结构
1.认识headers、版本、重要资源
所谓generic programing，GP泛型编程，就是使用template模板为主要工具来编写程序
根据源代码分析c++STL之体系结构
应具备的基础：c++基本语法，包括如何正确使用模板templates
-level0：使用c++标准库
-level1：深入认识c++标准库，清楚其在内存中的结构等
-level2：良好使用c++标准库
-level3：扩充c++标准库
c++标准库与STL
-c++ standard library：目前c++中已给的头文件
-standard template library：标准模板库，分为六大部件，标准库中大量存在STL
-标准库以Header files形式呈现，所以源代码可见
-headers中的组件封装于namespace std
using namespace std;
using std::cout;
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
不同版本标准库的用法基本相同
推荐网站：
-www.cplusplus.com
-en.cppreference.com
-gcc.gnu.org
2.STL体系结构基础介绍
STL六大部件：
-容器containers
-分配器allocators
-算法algorithms
-迭代器iterators
-适配器adapters
-仿函式functors
分配器用来支持容器存放
部分操作在容器本身操作另外部分放在算法操作
面向对象编程中鼓励将数据及函数放在类中，与STL不同
容器用来存放要处理的数据，算法对容器中的数据进行处理
迭代器是数据与操作的桥梁，是一种泛化的指针
仿函数作用像函数一样
适配器用来帮助转换，迭代器适配、仿函数适配、容器适配
#include <vector> //需要使用容器要引入对应的头文件
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;
int main()
{
int ia[6]={27,210,12,47,109,83};
vector<int,allocator<int>> vi(ia,ia+6);
//容器↑ 分配器↑
//模板：尖括号中第一个参数为类型，第二个参数允许放一个分配器帮助分配内存，不写的话使用默认
cout<<count_if(vi.begin(),vi.end,not1(bind2nd(less<int>(),40)));
// 算法↑ 迭代器↑ 适配器↑
//对数据的操作：需要用适配器来做容器和算法的接口
//predicate
return 0;
}
复杂度complexity
-O（1）、O（c）：常数时间 constant time
-O（n）：线性时间 linear time
-O（log2n）：次线性实践 sub-linear time
-O（n^2）：平方时间 quadratic time
-O（n^3）：立方时间 cubic time
-O（2^n）：指数时间 exponential time
-O（nlog2n）：介于线性及二次方成长的中间
“前闭后开”区间
标准库规定，容器中头指针指向第一个元素，尾指针所指为容器最后元素的下一个位置
容器中的空间并不一定连续，也可能是链表或者哈希表
Container<T> c;
...
Container<T>::iterator ite = c.begin();
//容器都有其专属的一个iterator，用其类型声明头指针
for(;ite!=c.end();ite++)
...
//对容器进行遍历
c++11新功能：
-对容器进行遍历
range-based "for" statement (since C++11)
for(decl:coll){statement}
for(int i : {2,3,5,7,9,13,17,19})
{
std::cout<<i<<std::endl;
}
std::vector<double> vec;
for(auto elem : vec)
{
std::cout<<elem<<std::endl;
}
for(auto& elem : vec)
{
elem *= 3;
}
-auto keyword
list<string> c;
...
list<string>::iterator ite;
ite=::find(c.begin(),c.end(),/*target*/);
↓
list<string> c;
...
auto ite = ::find(c.begin(),c.end(),/*target*/);
3.容器之分类与各种测试
容器-结构
-顺序表
-链表
-树
-堆
-哈希表
容器-分类
sequence containers
associative containers
unordered containers
hash table separate chaining
-array，固定大小，不可扩充
-vector，开头固定，尾可扩充
-list，双链表，双向都有指针
-forward_list，单链表，指针为单向
-slist
-deque，头尾可扩充
-stack
-multiset，集合中元素可重复
-multimap
-unordered_multiset，分散无序存放，
-unordered_multimap
-set，集合，一种平衡二叉树，每个元素中key和value为同一个，集合中元素不可重复
-map，图，通常用红黑树，每个元素中key和value为不同变量
-unordered_set
-unordered_map
-hash_set，哈希结构，目前最优
-hash_multiset
-hash_multimap
四个函数
-输入一个target
-输入一个字符串target
-比较两个long型大小
-比较两个字符串大小
使用容器array
#include <array>
#include <iostream>
#include <ctime>
#include <cstdlib> //qsort, bsearch, NULL
namespace jj01
{
void test_array()
{
cout << "\ntest_array().......... \n";
array<long,ASIZE> c;
clock_t timeStart = clock();
for(long i=0; i< ASIZE; ++i) {
c[i] = rand();
}
cout << "milli-seconds : " << (clock()-timeStart) << endl; //
cout << "array.size()= " << c.size() << endl;
cout << "array.front()= " << c.front() << endl;
cout << "array.back()= " << c.back() << endl;
cout << "array.data()= " << c.data() << endl;
long target = get_a_target_long();
timeStart = clock();
::qsort(c.data(), ASIZE, sizeof(long), compareLongs);
long* pItem = (long*)::bsearch(&target, (c.data()), ASIZE, sizeof(long), compareLongs);
cout << "qsort()+bsearch(), milli-seconds : " << (clock()-timeStart) << endl; //
if (pItem != NULL)
cout << "found, " << *pItem << endl;
else
cout << "not found! " << endl;
}
}
array
-尖括号中第一个参数为类型，第二个参数为容器大小
使用容器vector
#include <vector>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <iostream>
#include <ctime>
#include <algorithm> //sort()
namespace jj02
{
void test_vector(long& value)
{
cout << "\ntest_vector().......... \n";
vector<string> c;
char buf[10];
clock_t timeStart = clock();
for(long i=0; i< value; ++i)
{
try {
snprintf(buf, 10, "%d", rand());
c.push_back(string(buf));
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
//曾經最高 i=58389486 then std::bad_alloc
abort();
}
}
cout << "milli-seconds : " << (clock()-timeStart) << endl;
cout << "vector.max_size()= " << c.max_size() << endl; //1073747823
cout << "vector.size()= " << c.size() << endl;
cout << "vector.front()= " << c.front() << endl;
cout << "vector.back()= " << c.back() << endl;
cout << "vector.data()= " << c.data() << endl;
cout << "vector.capacity()= " << c.capacity() << endl << endl;
string target = get_a_target_string();
{
timeStart = clock();
auto pItem = find(c.begin(), c.end(), target);
cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, " << *pItem << endl << endl;
else
cout << "not found! " << endl << endl;
}
{
timeStart = clock();
sort(c.begin(), c.end());
cout << "sort(), milli-seconds : " << (clock()-timeStart) << endl;
timeStart = clock();
string* pItem = (string*)::bsearch(&target, (c.data()),
c.size(), sizeof(string), compareStrings);
cout << "bsearch(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != NULL)
cout << "found, " << *pItem << endl << endl;
else
cout << "not found! " << endl << endl;
}
c.clear();
test_moveable(vector<MyString>(),vector<MyStrNoMove>(), value);
}
}
-tips：测试程序的每一段归在一个namespace中
vector
-尖括号中的参数为类型
使用容器list
#include <list>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <algorithm> //find()
#include <iostream>
#include <ctime>
namespace jj03
{
void test_list(long& value)
{
cout << "\ntest_list().......... \n";
list<string> c;
char buf[10];
clock_t timeStart = clock();
for(long i=0; i< value; ++i)
{
try {
snprintf(buf, 10, "%d", rand());
c.push_back(string(buf));
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "milli-seconds : " << (clock()-timeStart) << endl;
cout << "list.size()= " << c.size() << endl;
cout << "list.max_size()= " << c.max_size() << endl; //357913941
cout << "list.front()= " << c.front() << endl;
cout << "list.back()= " << c.back() << endl;
string target = get_a_target_string();
timeStart = clock();
auto pItem = find(c.begin(), c.end(), target);
cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, " << *pItem << endl;
else
cout << "not found! " << endl;
timeStart = clock();
c.sort();
cout << "c.sort(), milli-seconds : " << (clock()-timeStart) << endl;
c.clear();
test_moveable(list<MyString>(),list<MyStrNoMove>(), value);
}
}
list
-尖括号参数为类型
循环存入数据
4.分配器之测试
使用分配器allocator
不同容器在声明时候的分配方式
-尖括号第二位置的参数即是所选用的分配器
#include <list>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <algorithm> //find()
#include <iostream>
#include <ctime>
#include <cstddef>
#include <memory> //內含 std::allocator
//欲使用 std::allocator 以外的 allocator, 得自行 #include <ext\...>
#ifdef __GNUC__
#include <ext\array_allocator.h>
#include <ext\mt_allocator.h>
#include <ext\debug_allocator.h>
#include <ext\pool_allocator.h>
#include <ext\bitmap_allocator.h>
#include <ext\malloc_allocator.h>
#include <ext\new_allocator.h>
#endif
namespace jj20
{
//pass A object to function template impl()，
//而 A 本身是個 class template, 帶有 type parameter T,
//那麼有無可能在 impl() 中抓出 T, 創建一個 list<T, A<T>> object?
//以下先暫時迴避上述疑問.
void test_list_with_special_allocator()
{
#ifdef __GNUC__
cout << "\ntest_list_with_special_allocator().......... \n";
//不能在 switch case 中宣告，只好下面這樣. //1000000次
list<string, allocator<string>> c1; //3140
list<string, __gnu_cxx::malloc_allocator<string>> c2; //3110
list<string, __gnu_cxx::new_allocator<string>> c3; //3156
list<string, __gnu_cxx::__pool_alloc<string>> c4; //4922
list<string, __gnu_cxx::__mt_alloc<string>> c5; //3297
list<string, __gnu_cxx::bitmap_allocator<string>> c6; //4781
int choice;
long value;
cout << "select: "
<< " (1) std::allocator "
<< " (2) malloc_allocator "
<< " (3) new_allocator "
<< " (4) __pool_alloc "
<< " (5) __mt_alloc "
<< " (6) bitmap_allocator ";
cin >> choice;
if ( choice != 0 ) {
cout << "how many elements: ";
cin >> value;
}
char buf[10];
clock_t timeStart = clock();
for(long i=0; i< value; ++i)
{
try {
snprintf(buf, 10, "%d", i);
switch (choice)
{
case 1 : c1.push_back(string(buf));
break;
case 2 : c2.push_back(string(buf));
break;
case 3 : c3.push_back(string(buf));
break;
case 4 : c4.push_back(string(buf));
break;
case 5 : c5.push_back(string(buf));
break;
case 6 : c6.push_back(string(buf));
break;
default:
break;
}
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "a lot of push_back(), milli-seconds : " << (clock()-timeStart) << endl;
//test all allocators' allocate() & deallocate();
int* p;
allocator<int> alloc1;
p = alloc1.allocate(1);
alloc1.deallocate(p,1);
__gnu_cxx::malloc_allocator<int> alloc2;
p = alloc2.allocate(1);
alloc2.deallocate(p,1);
__gnu_cxx::new_allocator<int> alloc3;
p = alloc3.allocate(1);
alloc3.deallocate(p,1);
__gnu_cxx::__pool_alloc<int> alloc4;
p = alloc4.allocate(2);
alloc4.deallocate(p,2); //我刻意令參數為 2, 但這有何意義!! 一次要 2 個 ints?
__gnu_cxx::__mt_alloc<int> alloc5;
p = alloc5.allocate(1);
alloc5.deallocate(p,1);
__gnu_cxx::bitmap_allocator<int> alloc6;
p = alloc6.allocate(3);
alloc6.deallocate(p,3); //我刻意令參數為 3, 但這有何意義!! 一次要 3 個 ints?
#endif
}
}
