------------恢复内容开始------------

P2

　　1.container 需要有allocator帮助分配内存,即每种container都得搭配一个allocator

　　2. container.begin（） 表示容器第一个元素的起始地址（指向第一个元素）

　　　 container.end() 　　表示最后一个元素之后下一个元素的起始位置【*(container.end()) = 垃圾内存】

　　　综上iterator 本身类似一个指了针（可能本质就是指针实现的） 可以（*，->,++,--)  

　　　iterator本身是一个smart pointer【pointer like class】

P3 

　　1. Vector 只有一端可扩充，pushback（）静态数组实现，每次是两倍扩展（2，4，8，16.....）

　　3. Associative containers： set（key）/multiset.  (key:value)map/multimap 底部都是红黑树实现

　　4. multi-表示key值是否可重复

　　unordered container（hashtable实现） 一般是链式冲突解决法

P5  <List> C++ 的list是双向链表且是环状的实现。单向链表是forward—list

　　1. 全局sort VS 容器自带sort

　　2. 提供 push_back & push_front

　　<forward-list>：

　　3. only push_front //Prepends the given element value to the beginning of the container.

　　4. slist(GNU 独有) ===== forward-list

　　<deque双端队列> 分段连续，段间离散，段内连续（有次序）

　　deque-->可以重构成 stack & queue【更像是deque的adapter】

　　因为deque有 push_front[back] 以及 pop_front[back]顾可以提供stack与queue 的所有操作。

　　

 P 10 Allocator

　　：：operator new ， ：：Operator delete最终都是C的malloc和free来分配内存 

　　GNU2.9 alloc类：存在一个数组[0]->[15] [0]每个元素8个字节，[1]每个元素占16...8的倍数递增下去，导致每次为多个元素分配空间时，头部的cookie个数减少。

　　GNU4.9 allocator类 

 

P 11 容器之间的关系

　　array,vector--->都是连续的空间（静态数组实现）。 priority_queue 中composite 一个heap 而heap则composite 一个 vector（基础都是vector）

　　set,map,multiset,multimap -> 中含有rb_tree 为复合关系 。 hash_set, hash_map ==unordered_set , unordered_map

　　deque（分段连续空间） stack,queue中都含有一个双端队列.

　　一般容器的iterator都需要 重载++ -- * -> 这4个操作符重载

　　

　　postfix form  = i++（后置）fetch and increment  ---->重载  operator++(int)    return { self temp = *this; ++*this ; return temp; } //old value {return by value}  ->不提供 i++++

　　prefix form = ++i　（前置）增加然后取回值 ------>重载 operator++()　　       return { return (*this)++ ; }. 　　//{return by reference} -> 提供 ++++i

　　

P13 list（本质是一个前闭后开双向链表，之所以要成环状，是为了begin()和end()判断空和满逻辑要不同）

   begin指向当前表头，end指向尾部元素的下一个

　iterator萃取器【iterator_traits】:用于返回该容器的一系列属性：iterator_category（指针的移动性质指针向前与向后），difference_type(当需要知道两iterator之间的距离时该用哪种数据类型表示 一般unsigned int），value_type（容器的元素类型），reference，pointer。

　所以iterator就需要5种associated types!  但前提只有struct（iterator） 和 class这种能够提供typedef的才可以通过classname直接萃取回答。

　如果对象是一个native pointer的话则无法直接通过类名访问，而是通过增加中间层（即iterator-萃取机）（提供偏特化在遇到pointer时可识别）

 

 

 

 

函数指针 (与数组类似函数的名字就是指向该函数的指针)

函数指针的定义方式

data_types (*func_pointer)( data_types arg1, data_types arg2, ...,data_types argn);

例如：

1.int (*fp)(int a); // 这里就定义了一个指向函数(这个函数参数仅仅为一个 int 类型，函数返回值是 int 类型)的指针 fp。
2.int RecallFunc(int *start, int *end, bool (*pf)(int)) // 定义指向函数（返回值 为bool型，参数只有一个为int）的指针pf.

------------恢复内容结束------------

P 14 vector（size = 12bytes 三根指针）【前闭后开】

 

front vs begin //一个返回数值（reference）一个返回指针(iterator)

back vs end  //一个返回数值（reference）一个返回指针(iterator)

vector's iterator 本质就是一个指针

红黑树(RB-Tree)

 1 //rb_tree 红黑树 是set 和 map的底层实现 使得元素自动有序。可以用iterator来改变元素的data，但是不应该这样做。
 2 //insert_unique()//不允许插入相同，插入无效，但不报错 insert_equal()
 3 //key关键字   //@argus  vale = (key|data)       //KeyOfValue =如何从value决定key是多少。类似hashfunction
 4 template <class Key , class Value ,class KeyOfValue ,class Compare, class Alloc = alloc>
 5 class rb_tree{
 6             protected:
 7                 typedef _rb_tree_node<Value> rb_tree_node;
 8             public:
 9                 typedef rb_tree_node* link_type;
10             protected:
11                 //RB_tree 只含有三个data
12                 size_t node_count;       //unsigned integer
13                 link_type header;       //指向整棵树的pointer
14                 Compare key_compare;    //一个彷函数 function object key值之间比较的规则
15 }

 

23. hashtable

  Buckets vector 当需要插入的元素个数大于bucket的个数时，需要re-hash。bucket 数量往往是素数。GNU选的是53作为初始，且在rehash的时候✖️2找最近的质数。

----strcmp(char* s1, char* s2)

　　//lexicographical order 字典顺序 [大写字母before与小写字母

　　Negative value if lhs appears before rhs in lexicographical order.  // 

　　Zero if lhs and rhs compare equal.

　　Positive value if lhs appears after rhs in lexicographical order.

 

　　

In normal English usage, when we sort words alphabetically, we employ two rules:

• If two words have the same first letter, we compare the second. If the second letters are the same, we compare the third, etc. Finally, one word comes before the other if the first differing letter comes before the corresponding letter.

• If two words are identical up to the length of the shorter word, the shorter word comes first.

　　So "Tom" comes before "Tooth". The first letters are identical ("T"), the second letters are identical "o", but the third letters diff and "m" comes 　　before "o". Therefore "Tom" comes before "Tooth".

　　"Tom" comes before "Tomas" because the two words are identical through the first three letters "Tom" and "Tom" is shorter than "Tomas".

　　Lexicographic order is simply alphabetic ordering, generalized for non-letter values. Consider a sequence of values, not necessarily letters:

　　(1,5,10) comes before (1,6,3) because "5" comes before "6".

　　(1,5,10) comes before (1,5,10,15,20) because (1,5,10) is shorter than (1,5,10,15,20).

　　Lexicographic ordering is particularly useful if the elements of the sequence have some specific meaning, with the earlier values giving a higher 　　precedence. For example, consider these times: 9:13 AM and 8:25 AM. If we represent these with the sequence (9,13) and (8,25), then (8,25) comes 　　before (9,13) because 8 comes before 9. What if the hours are the same? For example, (9,13) comes before (9,45) because 13 comes before 45. As 　　you can see, lexicographic ordering allows the hour field to have a higher precedence than the minute field.

--->hash function

template <class Key> struct

 

C++ 11 unordered_set ---> set 

容器-->class template

Algorithm --> function template: algorithm看不见containers，算法所需的一切信息需要由iterators来提供，告知具体数据结构。 iterator由容器提供～

output_iterator(例 ostream_iterator)是write-only，无法像forward iterator那样 read （*forward_iterator!= *first)

 

--->rbegin() & rend() 

 

 rbegin() 与 end()的指向一致但行为方向相反

 rend() 与 begin()指向一致但行为方向相反

 

---->functor （与adaptor适配). functor 

　　　　模版函数两种调用方法1. 显式指明参数类型 func<int,char>(5,'s');

　　　　　　　　　　　　　　2. 隐式推倒 func(4,'s');

 

---->C11 新适配器 bind & placeholders. (_1, _2 , _3....)

　　　std::bind 1.functions 

　　　　　　　 2.function objects

　　　　　　　 3.member functions, _1

-----> 函数指针

   　　　　　　声明： 返回类型 (*指针名) (函数形参1，函数形参2....) 

　　　　　　　　　　//声明一种函数指针类型 ,typedef 定义出一个新的类型名

　　　　　　　　　　typedef int (* Calc)(int value1 , int value2);　　　　//　　 Calc 为指向该类函数 变量类型

　　　　　　　typename 解决问题的最终办法，就是显式地告诉编译器，T::bar是一个类型名（而不是一个变量名）。这就必须用typename关键字，　　　　

　　　　

 

--------> 勿在浮沙筑高楼