C++ Standard Library--architecure & sources1

三月份开始复习泛型编程和STL的体系结构和内核分析,记录今天学的东西。

1. C++ Standard Library VS Standard Template Library

• 标准库是以head files的形式呈现的

• C++的标准模板库 >= STL

2. STL六大部件

1. 容器（Containers）
2. 分配器（Allocators）
3. 迭代器（Iterators）
4. 适配器（Adapters）_变压器
5. 算法（Algorithms）
6. 仿函式（Functors）

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;
int main()
{
    int ia[6] = {27, 48, 166, 78, 14, 227};
    vector<int, allocator<int>> vi(ia, ia+6);
    // predicate：判断式
    cout << count_if(vi.begin(), vi.end(), not1(bind2nd(less<int>(), 40)));
    return 0;
}

注：

• count_if：algorithm
• not1:function adapter(negator)
• bind2nd:function adapter(binder)
• less:function object

3. Container——前闭后开区间 [ )

4. range-based for loop(since C++11)

// 格式
for (decl : coll){
    statement
}

//demo1
for (int i: {1, 2, 3, 4, 5, 6, 7}){
    std::cout << i << std::endl;
}
//demo2
std::vector<double> vec;
...
    // 按值传递
    for (auto elem : vec){
        std::cout << elem << std::endl;
    }
	// 按引用传递
	for (auto& elem : vec){
    	elem *=3;
	}

5. auto keyword (since C++ 11)

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);

6.容器的结构与分类

• 不定序容器是红黑树

• Set、Map中的key——不可重复

• Multiset、Multimap中的key——不可重复

辅助函数

using std::cout;
using std::cin;
using std::string;
using std::array;
using std::endl;
const long ASIZE  =   500000L;

long get_a_target_long()
{
long target = 0;
	cout << "target (0~" << RAND_MAX << "): ";
	cin >> target;
	return target;
}


string get_a_target_string()
{
long target = 0;
char buf[10];
	
	cout << "target (0~" << RAND_MAX << "): ";
	cin >> target;
	snprintf(buf, 10, "%d", target); // 作用：模拟object的感觉，不能总传value
	return string(buf);
}


//  下面两个配合qsort使用 
int compareLongs(const void* a, const void* b)
{
    return (*(long*)a - *(long*)b);
}



int compareStrings(const void* a, const void* b)
{
    if (*(string*)a > *(string*)b)
        return 1;
    else if (*(string*)a < *(string*)b)
        return -1;
    else 
        return 0;
}

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;	
}
}

技巧：

• 测试代码最好也要封装成函数；
• 用namespace可以避免变量冲突
• 变量随用随定义是最好顶格写，这样方便查找！

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();
//-------------find: 循序查找, 看运气------------
    {
	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;
    }

 //-----------sort后bresearch：二分查找-----------------   
	{
	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);	
}	
}

说明：

• 容器的capacity的是成倍数增长的，在另外的地方开辟内存然后再将原来的复制到新的，过程比较慢
• 循序查找不一定比sort后bresearch慢，由此思考时间复杂度
• 所有的算法都是全局函数
• 容器的定义都有第二参数分配器，一般用默认