一、 认识headers、版本、重要资源
c++标准库体系结构与内核分析
1. Generic Programming（GP，泛型编程），就是使用template（模版）为主要工具来编写程序
2. 使用c++标准库
1) c++标准库：以若干头文件的方式呈现，可看到源代码
c++标准库的head files不带（.h），#include<vector>；
新式c头文件不带.h，#include<cstdio>；
2) 旧式c头文件带有.h仍然可用，#include<stdio.h>；
3) 命名空间namaspace，标准库把自己写的放到一个namespace中。新式headers内的组件封装于namespace “std” using namespace std；（把标准库打开，之后使用无需加std::）
using std::cout; （不把标准库全打开，打开个别）
4) 旧式的headers（头文件）内的组件不封装于namespace “std”
#include<string>
using namespace std;
5) 重要网页：要用到标准库的东西要去查他的规格
www.cplusplus.com
en.cppreference.com
gcc.gnu.org
《THE C++ STANDARD LIBRARY》《STL源码剖析》
3. STL，标准模板库：STL（含有6大成分）和一部分小组件构成了c++标准库
二、STL体系结构基础介绍
1. STL六大部件：
容器（Containers）
分配器（Allocators）
算法（Algorithms）
迭代器（Iterators）
适配器（Adapters）
仿函式（Functors）
一个程序是由数据结构/容器和算法构成。
六大部件关系如下：
分配器支撑容器，容器中操作使用算法；数据在容器中，操作在其他地方，这区别于面向对象编程，都放到类中；数据和操作之间的桥梁是迭代器（一种泛化的指针）
使用容器 vector，需要引入头文件#include<vector>; vector<> 容器后面<>表示模版vector<int,allocator<int>> vi(ia, ia+6); // int表示容器中元素类型是int，allocator表示分配器类型（大多情况下不写，直接使用默认值）；元素是int类型的容器vector，使用allocator分配器为其分配内存，每一个分配值都是int型 。int, allocator<int>前后int处类型要相同，vi（定义对象/变量），vi初值查手册。
count_if是算法，可以计算出所给条件下个数有多少个。
cout << count_if(vi.begin()，vi.end(), not1(bind2nd(less<int>(),40))); //bind2nd第二个参数绑定为40，not1否定，粗体部分为条件>=40。
2. 复杂度 O(n)----n要超级大
根据不同情况选择适合的容器
3. “前闭后开”区间 [ )
c.begin()指向容器的第一个元素，c.end()指向容器最后一个元素的下一个位置
Container<T> c;
...
Container<T>::iterator ite = c.begin();
for(; ite != c.end(); ite++)
... //iterator是泛化指针，指针有的操作他都可以
range-based for statement (since c++11) ---------用来取代上述iterator循环写法
for(decl : coll) { statement } coll是容器
eg：
for( int i : {2,3,5,7,9,13,17,19} )
{ std::cout << i << std::endl; }
/*************************************/
std::vector<double> vec;
...
for(auto elem:vec) //auto让编译器去判断变量类型
{ std::cout << elem << std::endl; }
for(auo& elem:vec)
{ elem *= 3;} //使用引用elem元素本身值会有改变
/**************************************/
4. auto
list<string> c;
...
list<string>::iterator ite;
ite = ::find(c.begin(), c.end(), target);
使用auto之后，
list<string> c;
. . .
auto ite = ::find(c.begin(), c.end(), target);
5. 容器---结构与分类
容器分类：序列式，关联式（key, value）
unodered containers（c++11 不定序）属于关联式
1）序列式：Array（连续空间，固定大小）；vector（大小不定，会自动扩充）；Deque（双向队列，两端可进可出）；List（链表，双向环状链表）；Forward-List（单向链表）
32位电脑上一个指针占4个字节
2）关联式
Set中不分key，value
Map由key，value组成，可通过key寻找value
如元素内容可重复使用MultiSet/Multimap
hash table Separate Chaining，如果有碰撞，将其放到一个链表的篮子中，每个篮子链表不能太长
array<类型，大小> c； array<int, 30> a; #include<array>
bsearch() 使用之前需要进行排序qsort()
三、vector（在内存中是两倍扩展）
写测试程序希望每一块都非常独立，每段测试放到namespace中，与其他namespace没有冲突
测试程序中，变量的声明不做缩进，用的时候进行声明。
push_back()是vector放元素的函数，从后面开始放元素，空间两倍增长，需要去挖内存
size() 大小
capacity() 容量
try...catch //抓取异常，c++异常调用abort( )函数直接终止程序
算法都是全局函数 前面加:: ::find( )
四、容器分类与测试
1）list双向链表 （元素是动态分配的）
pushback() // 添加元素
2）forward_list 单向链表 c++11标准库中
forward_list<string> c; c.push_front( ); //单向列表，只能从一端向里面放元素
3）slist 单向链表（同forward_list）只是该链表是gnu c中的。需要 #include <ext\slist>
4）容器deque
双向开口，可进可出的
一个容器占用多少内存之后是不可以扩充，扩充就占用别人的地方了
vector扩充是占用别人的地方。
deque两边都可以扩充，是分段连续，让使用者感觉是始终连续
里面分好多个buffer，添加内容时，可以前后扩充buffer
deque<string> c;
list和forward list都有自己的sort()函数，可以直接调用，其他容器没有要使用全局的，::sort()
关联式容器进行查找速度很快
5）容器stack： (先进后出)
放元素进去用push stack<string> c; c.push(); c.pop( ); //pop移除栈顶元素
6）容器queue （先进先出）
stack和queue属于deque，是适配器，可以叫容器
五、关联式容器 搜寻某些元素时比较适合使用。
1）multiset
key和value相同
multiset<string> c; c.insert( ); //插入元素，放到应该放的位置，没有前后。
2) multimap
通过key值进行找value
multimap<long, string> c; <type of key, type of value>
c.insert()
3) unordered_multiset( )
放东西进去用 insert()
4）容器set （set中key同value,不是multi，放进去的东西不可以重复）
5）map （放进去的东西不可以重复）
map<long, string> c;
c[i] = string(buf); // i是key，等号右边是value
六、分配器测试
容器背后需要分配器来支持其对内存的使用（容器有默认的分配器）
int* p;
allocator<int> alloc1; //创建一个分配器
p = alloc1.allocate(1);
alloc1.deallocate(p, 1); //释放要将创建的指针和分配的内存个数全部释放
建议：在程序中使用容器，需要小内存则用new/delete，malloc/free，不建议使用分配器，要记住分配内存个数
网友评论