STL_note

  • STL中容器、分配器、算法、仿函数、适配器、迭代器底层实现
  • STL源码剖析

[TOC]

STL

headers,版本，资源

  • c++ standard library

    • 以header 文件实现
    • 包括standard template library

  • standard template library

    • 六大部件

  • cplusplus.com

  • cppreference.com

  • gcc.gnu.org

  • 《The C++ STANDARD LIBRARY》 & 《STL 源码剖析》

STL 体系结构

  • 容器

  • 分配器

  • 算法

  • 迭代器

  • 适配器

  • 仿函数

    vector 放东西，分配器提供内存支持，算法提供函数支持，迭代器提供算法的输入，仿函数一种函数，适配器对容器，仿函数，迭代器做转换

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    #include <vector>
    #include <algorithm>
    #include <functional>
    #include <iostream>
    using namespace std;//allocator
    int main()
    {
        int ia[6]={27,210};
        vector<int,allocator<int>> vi(ia,ia+6);
        cout<<count_if(vi.begin(),vi.end(),not1(bind2nd(less<int>(),40)));
        return 0;
    }

    复杂度：n 要很大,查网站

前闭后开区间

c.end最后一个元素的下一个位置

1
2
3
4
5
6
//container 遍历
Container <T> c;
....
Container<T>::iterator ite=c.begin();
for(;ite!=c.end();++ite)
    ...

c++11 range based for statement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (int i:{2,3,4,5})
{
    cout<<i;
}
for (auto elem: vec)
{
  cout<<elem;  
}
for (auto& elem: vec)
{
  elem*=3;  
}
list<string> c;
list<string>::iterator ite;
ite=::find(c.begin(),c.end(),target);
////
auto ite=::find(c.begin(),c.end(),target);

容器分类和测试

容器结构与分类

vector push_back 尾部 插入元素
pop_back 弹出最后一个元素
begin 指向第一个元素的迭代器
end 指向最后一个元素下一个的迭代器
size 元素个数
max_size 最大容量
capacity 当前开辟空间大小
empty 是否为空
front 第一个元素的引用
back 最后一个元素的引用
data 容器元素首地址，为指针
clear 清空容器
at
list push_back
pop_back
push_front
pop_front
begin
end
size
max_size
front
back
c.sort
deque push_back
push_front
pop_back
pop_front
begin
end
size
max_size
front
back
at
operator[]
set insert
clear 清空set
erase 删除某一迭代器指定元素，两个迭代器之间的元素，和key值相等的元素
c.find
count
lower_bound Returns an iterator pointing to the first element that is not less than key
upper_bound
contains
map insert
at access specified element with bounds checking
operator[] access or insert specified element
empty
size
max_size
clear
erase
c.find

  • Sequence container
    • Array,固定size
    • Vector可以自动增长，分配器设置
    • Deque两端可进可出
    • List
    • Forward-List
  • Associative container(大量查找)
    • Set,底层红黑树，Multiset,值可重复
    • Map，底层红黑树，Multimap，值可重复
  • Unordered containers (c++11)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
namespace bliss_test_array{
    
    void test_array(){
        //cout<<"test array start ...."<<endl;
        array <long,ASIZE> c;
        clock_t timestart=clock();
        srand(time(NULL));
        for(long i=0;i<ASIZE;i++)
            c[i]=rand()%ASIZE;//0-(ASIZE-1)
        cout<<"clock-timestart "<<(clock()-timestart)<<endl;
        cout<<"size: "<<c.size()<<endl;
        cout<<"front "<<c.front()<<endl;
        cout<<"back "<<c.back()<<endl;
        cout<<"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<<"cost time: "<<clock()-timestart<<" ms"<<endl;
        if(pitem!=NULL)
            cout<<"found, "<<*pitem<<endl;
        else
            cout<<"not found \n";
    }

}

vector test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//vector
namespace bliss_test_vector
{
    void test_vector(long& value){
        cout<<"\n test vector start ,,,\n";
        vector<string> c;
        char buf[10];
        clock_t timestart=clock();
        for(long i=0;i<value;i++)
        {
            try{
                snprintf(buf,10,"%d",rand()%ASIZE);
                c.push_back(buf);
            }
            catch(exception& p){
                cout<<"i: "<<i<<" "<<p.what()<<endl;
                abort();
            }
        }
        cout<<"cost time: "<<clock()-timestart<<endl;
        cout<<"size: "<<c.size()<<endl;
        cout<<"front: "<<c.front()<<endl;
        cout<<"back: "<<c.back()<<endl;
        cout<<"data: "<<c.data()<<endl;
        cout<<"capacity: "<<c.capacity()<<endl;
        string target=get_a_target_string();
        {
            timestart=clock();
            auto pitem=::find(c.begin(),c.end(),target);
            cout<<"find cost time ms "<<clock()-timestart<<endl;
            if(pitem!=c.end())
                cout<<"found, is "<<*pitem<<endl;
            else
                cout<<"not found "<<endl;
        }
        {
            timestart=clock();
            sort(c.begin(),c.end());
            string* pitem=(string*)bsearch(&target,c.data(),c.size(),sizeof(string),compareStrings);
            cout<<"sort+bsearch cost time ms "<<clock()-timestart<<endl;
            if(pitem!=NULL)
                cout<<"found, is "<<*pitem<<endl;
            else
                cout<<"not found "<<endl;
        }
    }
}

vector 内存增长方式为两倍增长,

假如c1已有2个元素，插入第三个时，vector扩展为4个，找到4个连续的空间，把前两个复制过去，把第三个填进去。

list 一个萝卜一个坑

list test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//list test
namespace bliss_test_list
{
    void test_list(long& value)
    {
        cout<<"\n test list start"<<endl;
        list <string> c;
        char buf[10];
        clock_t timestart=clock();
        for(long i=0;i<value;i++)
        {
            try{
            snprintf(buf,10,"%d",rand()%value);
            c.push_back(string(buf));
            }
            catch(exception& p){
                    cout<<"i "<<i<<"  "<<p.what()<<endl;
                    abort();
            }
        }
        cout<<"list cost time: "<<clock()-timestart<<endl;
        cout<<"list size "<<c.size()<<endl;
        cout<<"list max_size "<<c.max_size()<<endl;
        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<<"list find cost time ms "<<clock()-timestart<<endl;
            if(pitem!=c.end())
                cout<<"list found, is "<<*pitem<<endl;
            else
                cout<<"list not found "<<endl;
        }
        {
            timestart=clock();
            c.sort();
            //qsort(c.data(),value,sizeof(string),compareStrings);
            clock_t timestart2=clock();
            //string* pitem=(string*)bsearch(&target,c.data(),c.size(),sizeof(string),compareStrings);
            cout<<"list c.sort+bsearch cost time ms "<<clock()-timestart<<endl;
            //cout<<"c.sot cost time : "<<timestart2-timestart<<"\n ratio: "<<(timestart2-timestart)*1.0/(clock()-timestart)<<endl;
           // if(pitem!=NULL)
            //    cout<<"found, is "<<*pitem<<endl;
           // else
            //    cout<<"not found "<<endl;
        }
    }
}

deque test

一行一个buffer，分段连续，每一个buffer连续，不同buff虚连续，每次扩充一个buffer，如果往右插，插满，右扩一个buffer，左边类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

//deque
#include <deque>
namespace bliss_test_deque
{
    void test_deque(long& value)
    {
        cout<<"\n test deque start"<<endl;
        deque <string> c;
        char buf[10];
        clock_t timestart=clock();
        for(long i=0;i<value;i++)
        {
            try{
            snprintf(buf,10,"%d",rand()%value);
            c.push_back(string(buf));
            }
            catch(exception& p){
                    cout<<"i "<<i<<"  "<<p.what()<<endl;
                    abort();
            }
        }
        cout<<"deque cost time: "<<clock()-timestart<<endl;
        cout<<"deque size "<<c.size()<<endl;
        cout<<"deque max_size "<<c.max_size()<<endl;
        cout<<"deque front "<<c.front()<<endl;
        cout<<"deque back "<<c.back()<<endl;
        string target=get_a_target_string();
        {
            timestart=clock();
            auto pitem=::find(c.begin(),c.end(),target);
            cout<<"deque find cost time ms "<<clock()-timestart<<endl;
            if(pitem!=c.end())
                cout<<"deque found, is "<<*pitem<<endl;
            else
                cout<<"deque not found "<<endl;
        }
        {
            timestart=clock();
            ::sort(c.begin(),c.end());
            //qsort(c.data(),value,sizeof(string),compareStrings);
            clock_t timestart2=clock();
            //string* pitem=(string*)bsearch(&target,c.data(),c.size(),sizeof(string),compareStrings);
            cout<<"deque c.sort+bsearch cost time ms "<<clock()-timestart<<endl;
            //cout<<"c.sot cost time : "<<timestart2-timestart<<"\n ratio: "<<(timestart2-timestart)*1.0/(clock()-timestart)<<endl;
           // if(pitem!=NULL)
            //    cout<<"found, is "<<*pitem<<endl;
           // else
            //    cout<<"not found "<<endl;
        }
    }
}

stack test

stack 先进后出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
namespace bliss_test_stack
{
    void test_stack(long& value)
    {
        cout<<"\n test stack start"<<endl;
        stack <string> c;
        char buf[10];
        clock_t timestart=clock();
        for(long i=0;i<value;i++)
        {
            try{
            snprintf(buf,10,"%d",rand()%value);
            c.push(string(buf));
            }
            catch(exception& p){
                    cout<<"i "<<i<<"  "<<p.what()<<endl;
                    abort();
            }
        }
        cout<<"stack cost time: "<<clock()-timestart<<endl;
        cout<<"stack size "<<c.size()<<endl;
        cout<<"stack top "<<c.top()<<endl;
        cout<<"stack pop "<<endl;
        c.pop();
        cout<<"stack size "<<c.size()<<endl;
        cout<<"stack top "<<c.top()<<endl;
        //cout<<"deque max_size "<<c.max_size()<<endl;
        //cout<<"deque front "<<c.front()<<endl;
        //cout<<"deque back "<<c.back()<<endl;
        
    }
}

stack 和queue 不提供 iterator 函数。

没有讲find函数？？,找到后返回一个iterator

queue test

  • 先进先出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
namespace bliss_test_queue
{
    void test_queue(long& value)
    {
        cout<<"\n test queue start"<<endl;
        queue <string> c;
        char buf[10];
        clock_t timestart=clock();
        for(long i=0;i<value;i++)
        {
            try{
            snprintf(buf,10,"%d",rand()%value);
            c.push(string(buf));
            }
            catch(exception& p){
                    cout<<"i "<<i<<"  "<<p.what()<<endl;
                    abort();
            }
        }
        cout<<"queue cost time: "<<clock()-timestart<<endl;
        cout<<"queue size "<<c.size()<<endl;
        cout<<"queue front "<<c.front()<<endl;
        cout<<"queue back "<<c.back()<<endl;
        cout<<"queue pop "<<endl;
        c.pop();
        cout<<"queue size "<<c.size()<<endl;
        cout<<"queue front "<<c.front()<<endl;
        cout<<"queue back "<<c.back()<<endl;
        //cout<<"deque max_size "<<c.max_size()<<endl;
        //cout<<"deque front "<<c.front()<<endl;
        //cout<<"deque back "<<c.back()<<endl;
        
    }
}

multiset test

  • insert时，已排好序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
namespace bliss_test_multiset
{
    void test_multiset(long& value)
    {
        cout<<"\n test multiset start"<<endl;
        multiset <string> c;
        char buf[10];
        clock_t timestart=clock();
        for(long i=0;i<value;i++)
        {
            try{
            snprintf(buf,10,"%d",rand()%value);
            c.insert(string(buf));   
            }
            catch(exception& p){
                    cout<<"i "<<i<<"  "<<p.what()<<endl;
                    abort();
            }
        }
        cout<<"multiset cost time: "<<clock()-timestart<<endl;
        cout<<"multiset size "<<c.size()<<endl;
        cout<<"multiset max_size "<<c.max_size()<<endl;
         string target=get_a_target_string();
        {
            timestart=clock();
            auto pitem=::find(c.begin(),c.end(),target);
            cout<<"multiset find cost time ms "<<clock()-timestart<<endl;
            if(pitem!=c.end())
                cout<<"multiset found, is "<<*pitem<<endl;
            else
                cout<<"multiset not found "<<endl;
        }
        {
            cout<<"find cost time :"<<clock()-timestart<<endl;
            timestart=clock();
           
            auto pitem=c.find(target);
            cout<<"c.find cost time :"<<clock()-timestart<<endl;
            if(pitem != c.end())
                cout<<"found "<<*pitem<<endl;
            else
                cout<<"not found!"<<endl;
        }
        
    }
}

multimap test

multiset，multimap底层红黑树，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <map>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime>
namespace bliss_test_multimap
{
    void test_multimap(long &value)
    {
        cout<<"test multimap start..."<<endl;
        multimap<long,string> c;
        char buf[10];
        clock_t timestart=clock();
        for(long i=0;i<value;i++){
            try{
                snprintf(buf,10,"%d",rand()%value);
                c.insert(pair<long,string> (i,buf));
            }
            catch(exception& p){
                cout<<"i: "<<i<<" "<<p.what()<<endl;
                abort();
            }
        }
        cout<<"inset cost time "<<clock()-timestart<<endl;
        cout<<"multimap size "<<c.size()<<endl;
        cout<<"multimap maxsize "<<c.max_size()<<endl;
        long target=get_a_target_long();
        timestart=clock();
        auto pitem=c.find(target);
        cout<<"c.find cost time "<<clock()-timestart<<endl;
        if(pitem!=c.end())
            cout<<"find "<<(*pitem).first<<" : " <<(*pitem).second<<endl;
        else
            cout<<"not found !"<<endl;
    }
}

unordered_multiset test

seperated chaining 底层hashtable

bucket 一定比数据多

每一个bucket一定不太长，如果元素个数>=bucket个数，这个bucket拆开。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <unordered_set>
namespace bliss_test_umultiset
{
     void test_umultiset(long& value)
    {
        cout<<"\n test unordered multiset start"<<endl;
        unordered_multiset <string> c;
        char buf[10];
        clock_t timestart=clock();
        for(long i=0;i<value;i++)
        {
            try{
            snprintf(buf,10,"%d",rand()%value);
            c.insert(string(buf));   
            }
            catch(exception& p){
                    cout<<"i "<<i<<"  "<<p.what()<<endl;
                    abort();
            }
        }
        cout<<"unordered multiset cost time: "<<clock()-timestart<<endl;
        cout<<"unorderedmultiset size "<<c.size()<<endl;
        cout<<"unordered multiset max_size "<<c.max_size()<<endl;
        cout<<"unordered multiset c.bucket_count "<<c.bucket_count()<<endl;
        cout<<"unordered multiset c.max_bucket_count "<<c.max_bucket_count()<<endl;
        cout<<"unordered multiset c.load_factor "<<c.load_factor()<<endl;
        cout<<"unordered multiset c.max_load_factor "<<c.max_load_factor()<<endl;
        
        for(unsigned i=0;i<20;i++){
            cout<<"bucket "<<i<<" has "<<c.bucket_size(i)<<" elements!"<<endl;
        }
          string target=get_a_target_string();
        {
            timestart=clock();
            auto pitem=::find(c.begin(),c.end(),target);
            cout<<"unordered multiset find cost time ms "<<clock()-timestart<<endl;
            if(pitem!=c.end())
                cout<<"unordered multiset found, is "<<*pitem<<endl;
            else
                cout<<"unordered multiset not found "<<endl;
        }
        {
           // cout<<"find cost time :"<<clock()-timestart<<endl;
            timestart=clock();
           
            auto pitem=c.find(target);
            cout<<"unordered multiset c.find cost time :"<<clock()-timestart<<endl;
            if(pitem != c.end())
                cout<<"found "<<*pitem<<endl;

            else
                cout<<"not found!"<<endl;
        }
    }
}

unordered_multimap test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <unordered_map>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime>
namespace bliss_test_umultimap
{
    void test_umultimap(long &value)
    {
        cout<<"test unordered multimap start..."<<endl;
        unordered_multimap<long,string> c;
        char buf[10];
        clock_t timestart=clock();
        for(long i=0;i<value;i++){
            try{
                snprintf(buf,10,"%d",rand()%value);
                c.insert(pair<long,string> (i,buf));
            }
            catch(exception& p){
                cout<<"i: "<<i<<" "<<p.what()<<endl;
                abort();
            }
        }
        cout<<"unordered multimap inset cost time "<<clock()-timestart<<endl;
        cout<<"unordered multimap size "<<c.size()<<endl;
        cout<<"unordered multimap maxsize "<<c.max_size()<<endl;
        long target=get_a_target_long();
        timestart=clock();
        auto pitem=c.find(target);
        cout<<"unordered multimap c.find cost time "<<clock()-timestart<<endl;
        if(pitem!=c.end())
            cout<<"unordered multimap find "<<(*pitem).first<<" : " <<(*pitem).second<<endl;
        else
            cout<<"unordered multimap not found !"<<endl;
    }
}

set test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
namespace bliss_test_set{
    void test_set(long& value)
    {
        cout<<"test set start .."<<endl;
        set <string> c;
        char buf[10];
        clock_t timestart=clock();
        for(long i=0;i<value;i++)
        {
            try{
            snprintf(buf,10,"%d",rand()%value);
            c.insert(buf);
            }
            catch(exception & p){
                cout<<"i: "<<i<<p.what()<<endl;
            }
        }
        cout<<"set insert cost time : "<<clock()-timestart<<endl;
        cout<<"set size "<<c.size()<<endl;
        string target=get_a_target_string();
        {
            timestart=clock();
            auto pitem=::find(c.begin(),c.end(),target);
            cout<<".find cost time "<<clock()-timestart<<endl;
            if(pitem!=c.end())
                cout<<"set find "<<*pitem<<endl;
            else    
                cout<<"not find !"<<endl;
        }
        {
            timestart=clock();
            auto pitem=c.find(target);
            cout<<"set c.find cost time "<<clock()-timestart<<endl;
            if(pitem!= c.end())
                cout<<" find "<<*pitem<<endl;
            else    
                cout<<"not find !"<<endl;
        }
    }

}

map test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <map>
namespace bliss_test_map
{
    void test_map(long& value)
    {
        cout<<"test map start .."<<endl;
        map<long,string> c;
        char buf[10];
        clock_t timestart=clock();
        for(long i=0;i< value;i++){
            try{
                snprintf(buf,10,"%d",rand()%value);
                c[i]=string(buf);// key=,value= string(buf);
            }
             catch(exception & p){
                cout<<"i: "<<i<<p.what()<<endl;
            }
        }
        cout<<"map insert cost time : "<<clock()-timestart<<endl;
        cout<<"map size "<<c.size()<<endl;
        long target = get_a_target_long();		
        timestart = clock();		
        auto pItem = c.find(target);								
	    cout << "c.find(), milli-seconds : " << (clock()-timestart) << endl;		 
	    if (pItem != c.end())
    	    cout << "found, value=" << (*pItem).second << endl;
  	    else
    	    cout << "not found! " << endl;			
    	
        c.clear();	
    }
}

hash_set -> unordered set

hash_map -> unordered map

hash_multiset -> unordered multiset

hash_multimap -> unordered multimap

分配器测试

gnuc c 编译器

对vector 支持对内存的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//通过容器使用分配器
//不能在 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 														
	 
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;		
//直接使用 分配器
int* p; 	
    allocator<int> alloc1;	
	p = alloc1.allocate(1);  //要 1个
	alloc1.deallocate(p,1); 	//还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?

malloc free

  • 不建议直接分配器，

  • 直接用容器，小内存用malloc free

源代码分布(vc gcc)

////gnuc 2.91

visiual studio 2013/include

dev-c++ 5.11 with gnu 4.92//4.9.2 include /c++

OOP VS GP

  • OOP 将datas 和methods 关联在一起
  • GP 将datas和methods分开
    • 容器和algorithm可以分开来独立开发，以Iterator沟通即可
    • Algorithms 通过Iterator确定操作范围，通过iterator获取container、元素
  • list 不能直接调用全局sort,自己类内定义有sort，全局sort 需要有randomaccess iterator,list iterator 迭代器指向上一个，下一个，不能随便跳。
  • 所有algorithms, 最终涉及的元素本身的操作，就是比大小

操作符重载和模板

  • ：： ，. ,* ,?:,不能被重载
1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T>
class complex
{
    public:
    	complex(T r=0,T i=0)
            :re(r),im(i){}
    private:
    	T re,im;
}
{
    complex<double> c1(2.5,1.5);
    complex<int>c2(2,6);
}

在声明模板的时候使用typename而不是class –effectve stl

1
2
3
4
5
6
7
8
template <class T>
inline 
const T& min(const T& A, const T& B)
{
	return b<a?b:a;    
}
stone s1,s2;
min(s1,s2)//实参推导 到 stone类内的 操作符重载 stone::operator<

成员模板。。。。。

模板特化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//泛化
template <class type>
struct __type_traits{
	typedef __true_type this_dummy_member_must_be_first;
	typedef __false_type has_trivial_default_constructor;
	
};
//int 特化
template <> 
struct __type_traits<int>
{

}；
//double 特化
template <> 
struct __type_traits<double>
{

}；
//使用
__type_traits<Foo>::this_dumy;
__type_traits<int>::
__type_traits<double>::
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//偏特化
//个数偏特化
template<class T,class Alloc=alloc>
class vector{};

template <class Alloc>
class vector<bool,Alloc>
{};

///////////////////////////////////////////////
//范围偏特化
template <class Iterator>
struct iterator_traits{

};
template <class T>
struct iterator_traits<T*>{

};
template <class T>
struct iterator_traits<const T*>{

};

分配器 Allocator

operator new() 和malloc()

VC6 allocator使用

debug 模式下=debug内存+内存+pad+cookie

1
2
int *p=allocator<int>().allocate(512,(int* )0);
allocator<int>().deallocate(p,512);

VC6* 的allocator 只是以::operator new 和::operator delete 完成allocat() 和deallocate()，没有任何特殊设计。

BC5 STL 对allocator 使用

BC++ 的allocator 只是以::operator new 和::operator delete 完成allocat() 和deallocate()，没有任何特殊设计。

G2.9 对allocator使用

GCC2.9 的allocator 只是以::operator new 和::operator delete 完成allocat() 和deallocate()，没有任何特殊设计。

GCC2.9 实际使用 SGI版本的allocator。

  • 尽量减少调用malloc次数，调用malloc有额外开销。

  • cookie记录整块大小，容器每个元素大小相同，不必对每个元素都记录大小

  • 设计16条链表，每一条负责特定大小的区块，用链表串起来。

  • 第7个负责7*8=56个字节大小，第一个负责8个byte，第二个16个。

  • 容器需要内存时，向这个分配器要内存，容器的元素大小被调整到8的倍数，50->56，第七个负责，看这个链表有没有挂内存块，如果没有向操作系统要内存(malloc),切出来的内存用单向链表存，整块内存还是带cookie，整块中每个小块不带cookie，1个cookie 8个字节。

  • 一个容器有1百万个元素，可以省去开销8百万个字节（最多），alloc分配器。

  • GCC2.91 allocator 采用上述分配器 alloc。

GCC4.9 allocator

GCC4.9 allocator回到从前allocator，extension allocators中 __poool_allloc 极为G2.9中 alloc。

GCC4.9使用较好版本alloctor.

1
vector <string,__gnu_cxx::__pool_alloc<string>> vec;

容器之间的实现关系和分类

heap 里有一个vector。

左右蓝色区域，为创建一个object需要内存，指的是需要控制所有元素所需的内存，那个对象本身。

list 深度探索

GCC2.9 list 只需一个Link_type node 4 个字节。

  • 灰色，环状，双向，实现所有容器在表现起begin end时，前闭后开。

  • end指向灰色。

  • 除vector array外所有容器，iterator 都必须class。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//一个node
template <class T>
struct __list_node{
        typedef void * void_pointer;
        void_pointer prev;
        void_pointer next;
        T data;
}
template <class T,class Alloc=alloc>
class list{
protected:
	typedef __list_node<T> list_node;
	typedef __list_iterator<T,T&,T*> iterator;
protected:
	link_type node;
};

template <class T,class Ref,class Ptr>
struct __list_iterator{
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef __list_node<T> * link_type;
	typedef ptrdiff_t difference_type;
}


//使用
list<Foo>::iterator it;

  • 每一个容器的iterator一定有 5个typedef。

  • 一堆操作符重载

  • iterator++,应找到next指针。

  • 两个版本,++i前置型,i++ 后置型;

  • 为区分，前++没有参数，i已经变为调用这个函数的object本身。

self tmp=*this,编译器首先遇到=,进行拷贝构造，

  • operator->() ？？？？？

新旧版本区别

  • __list_node 链表指针指向自己
  • _list_iterator 一个参数

​ G4.9 list大小为8，看base多大，看_list_impt多大，看_list_node_base，两个指针，八个字节。

list没有数据，继承自父类_list_base，_list_base 有数据 mimpl，数据类型为_list_impl。

list_impl有数据mmode,数据类型为_list_node_base,而list_node_base 包含两个指针。

## 迭代器的设计原则和iterator traits 的作用和设计

  • traits 萃取机，提取特征

  • pointer traits，character traits，等

    iterator 算法和容器之间桥梁。

    iterator associated types:

  • iterator_category: iterator 分类，移动性质，++,– ，+=5；

  • value_type: iterator 指向的object的元素的类型

  • difference_type: 两个iterator 之间距离用什么type表示。e.g uint

  • reference type 未使用

  • pointer type 未使用

  • std::ptrdiff_t is the signed integer type of the result of subtracting two pointers.

  • A BidirectionalIterator is a ForwardIterator that can be moved in both directions (i.e. incremented and decremented).

  • 只有class 才能做 typedef

  • 当算法收到的是指针而不是iterator（class）时。

    加上一层traits中间层，通过偏特化，分类。

1
2
3
4
5
6
typedef typename I::value_type value_type;
// I能也包含模板时，必须这样用
// 显然，iterator 本身是一个class，肯定带模板参数
//typedef  I::value_type value_type; xxxx
typedef 定义一个新的名字（同一个数据类型）
typename 把一个特殊的名字解释成一个类型

  • A RandomAccessIterator is a BidirectionalIterator that can be moved to point to any element in constant time.

    A pointer to an element of an array satisfies all requirements of RandomAccessIterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
  
  各种traits:
  
* type traits <.../c++/type_traits>
  
* iterator traits  <.../c++/bits/stl_traits.h>
  
* char traits   <.../c++/bits/char_traits.h>
  
* allocator traits <.../c++/bits/allocator_traits.h>
  
* pointer traits   <.../c++/bits/ptr_traits.h>
  
* array traits     <.../c++/array>

vector 深度探索

  • 一个vector三个变量记录，八个空间，目前已放6个元素，start,finish,end_of_storage

  • sizeof(vector())=12; protected 3个 数据。

  • 所有连续空间容器需要提供[]操作符重载,deque号称连续空间

mark

大量元素拷贝，引发拷贝构造函数，析构函数，成本很大。

  • 链表迭代器节点分离,iterator设计为class

  • vector 连续空间，iterator 指针

新版本大小

​

array forward_list 深度探索

  • c++1.0 1998

  • c++2.0 2011

  • TR1版本

iterator作为算法和容器之间的桥梁，需要给算法提供5个typedef，(value_type,reference_type,pointer,distance,category)iterator本身可以为class或者指针，这时就需要traitor萃取器，以偏特化的方式获取5个typedef。

forward list

deque queue stack 深度探索

deque:

  • 5个buffer(横条)
  • vector 将buffer串起来，vector元素为指针，指向buffer
  • pushback 将缓冲区填满时，右建一个buffer，右挂到vector上
  • pushfront将缓冲区填满时，左建一个buffer，左挂到vector上
  • 迭代器 为clas，内部有四个元素,cur,first,last,node
    • node 指向vector 中控制区
    • first last 指定buffer大小
  • 几乎所有容器都提供两个函数 begin end,。

* sizeof(dque<int>) 16*2+4+4= 40
* 一个iterator 16 4个指针

deque iterator 4个元素:

  • cur
  • first
  • last
  • node

​

​

size()函数：

  • start 指向的buffer有多少个元素+finish指向的buffer有多少个元素
  • 以及start和finish之间有多少个buffer，每个buffer

operator -，两个迭代器之间有多少个元素

  • i++(self operator++(int))，调用++i(self& operator++())；

  • i–,调用–i;

  • set_node() 移动到下一个缓冲区时，first,last需要重新设值。

一个deque包含4个：

  • mmap指向 控制中心
  • mmap_size 指定控制中心大小，可以容纳多少个指针，控制中心copy时copy到中心。
  • mstart 开始 迭代器
  • mfinish 结束

queue 也成为适配器

  • vector 只能在尾部添加元素
  • 如果没有调用c.pop()，那么queue用vector做底层是没有问题的（至少编译器不报错）。

stack 和queue 都不可用set 和map做底部支撑，编译器不会做全面检查，用到哪个，才会检查哪个。

rb tree深度探索

  • 小型数据库
  • key ->value
  • 插入快，搜寻快
  • 红黑树
    • 平衡二元搜寻树，排列有利于search和insert
    • begin() 最左边的节点，end()最右边的节点
    • 提供遍历，++ite时，从左边走，5->6->7->6>8->10->11->12->13->15
    • 不应该使用iterators改变元素值。map中key不可以改，但是value可以改变
    • 提供两种insertion
      • insert_unique() key 独一无二,放重复值时不会崩溃，不会异常，只是放不进去
      • insert_equal() 允许key重复，相同的值 相邻。
    • header 满足前闭后开

mark

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class Key,
          class Value,//(key|data)合起来 =value
          class KeyOfValue,//在这个value里，这个key要怎么拿到
          class Compare,// 两个元素比大小 函数
          class Alloc=alloc>
class rb_tree{
  protected:
    typedef _rb_tree_node<value> rb_tree_node;
  public:
    typedef rb_tree_node* link_type;
protected:
    size_type node_count;//rb_tree 大小 节点数量
    link_type header;
    Compare key_compare;//key 大小判定 函数
};

仿函数没有数据大小为0，对于大小为0的class，编译器实现出来大小为1；

2+3+1=9 ->12(4的倍数)

mark

五个模板参数怎么用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template <class Arg,class Result>
struct unary_function{
    typedef Arg argument_type;
    typedef Result result_type;
};
template <class T>//仿函数
    struct identity:public unary_function<T,T>{
        const T& operator()(const T&x){return x;}
    };
#endif // RB_TREE_HPP
    template <class Arg1,class Arg2,class Result>
    struct binary_function{
        typedef  Arg1 first_argument_type;
        typedef Arg2 second_argument_type;
        typedef Result result_type;
    };
template <class T>
struct less:public binary_function<T,T,bool>{
    bool operator()(const T& x,const T&y)
    {
        return x<y;
    }
};

rb_tree<int,
        int,
        identity<int>,
        less<int>,
        alloc>
mytree;

mark

测试:

mark

mark

set multiset深度探索

  • 以红黑树为底层，自动排序，排序依据为key
  • key 即为value，value即为key
  • 提供遍历操作，++ite，获得排序状态
  • 无法使用iterators改变元素的值，底层时RB tree的 const iterator
  • set key 独一无二 Insert ： rbtree insert_unique()
  • multiset key可以重复 insert : rbtree insert_equal()

mark

mark

map multimap 深度探索

mark

  • 通过select1st获取key
  • pair<const key,T>,不可以通过iterator修改key

mark

  • select1st 仿函数 重载operator()
  • multimap 不可用[] 做insertion

mark

mark

  • map.operator[]如果找到key，则返回，如果找不到插入这个key

  • 假设有7个hello，且这七个放在一起

  • lower_bound找到第一个hello，如果value不存在找到最适合安插这个值的迭代器

  • c.insert(pair<long,string>(i,buf))

  • c[i]=string(buf)

mark

hashtable 深度探索

  • 一个object对应一个数，数的范围0-2^32-1;需要N=sizeof(T)*2^32 个空间

  • N: 编号为T，将object放到第T个位置去

  • M<N

  • M:编号为H，放到第H%M个位置去，有可能冲突，冲突就放在一起成为要给链表

mark

  • separate chainging 方法：
    • 55%53=2
    • 2%53=2
  • 链表很长？？链表长时打散。
    • bucket为位置，篮子，多为质数，素数53
    • 当链表元素个书大于bucket个数，链表打散rehashing，bucket变为大约两倍，变为素数53左右的素数97
    • 53 97 193 389

mark

  • HashFcn 计算object编号 hashcode
  • ExtractKey 获得key的function
  • EqualKey key相等的定义
  • 3（hasher+key_equal+extractKey 三个0 大小的class）+3*4（vector）+4=19->20
  • vC链表双向，GCC单向链表
  • cur某一个结点，图错误！！

mark

  • 测试
    • 元素为char* string
    • hash 提供 hashcode
    • identity 提供 key的方法
    • eqstr key相等的方法
      • 判断两个字符串内容

mark

  • 模板偏特化
  • 仿函数
  • 如果是数值的话，就把该数值作为hashcode

mark

  • hash_code需要尽可能的不重复
  • 标准库没有提供针对c++字符串的hashstd::string
  • Zeal——–There is no specialization for C strings. std::hash<const char*> produces a hash of the value of the pointer (the memory address), it does not examine the contents of any character array.

mark

  • modulus 余数
  • 左边hash_table成员函数

mark

hash_set hash_multiset hash_map hash_multimap 概念

unordered 容器概念

mark

  • bucket 个数大于元素个数

mark

算法的形式

  • 算法是个函数模板，两个版本
    • 带compare
    • 不带compare
    • 算法如果知道容器，也许能够找到一些最优的方法，
    • 算法提问，迭代器回答，如果迭代器回答不了，则编译失败

mark

迭代器的分类

  • 5个typedef
  • 迭代器是由容器提供的
  • array /vector/ deque
    • random_access
  • list/ rb_tree（set/ map/ multiset /multimap）
    • bidirectional
  • forward-list
    • farward
  • hashtable
    • 根据底层的链表 实现
  • 以5个strut表示iterator的类别，而不是enum，或者5个数

mark

  • typename（） 创建一个临时对象
  • istream_iterator() input_iterator
  • ostream_iterator(cout,””) output_iterator

mark

  • 类型名称 typeid（iterator）.name
  • 一个class 命名abc ，编译器编译后增加东西

mark

  • 父类只有typedef ，子类相当于继承了这几个typedef
  • 不同版本接口一定一样，可以通过默认参数设置

mark

mark

迭代器分类对算法的影响

  • distance 得到两根指针的距离

  • 输入参数

    • iterator_traits::iterator_category category;
    • 把itertor 丢给iterator_traits 然后问
      • random_access
        • last-begin
      • input_iterator //// 慢
        • ++first, count(++)

  • 返回类型

    • inline iterator_traits::difference_type;

    • 把itertor 丢给iterator_traits 然后问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//qt msvc
template<class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
_distance(InputIterator first,InputIterator last,input_iterator_tag){
    typename iterator_traits<InputIterator>::difference_type n=0;//不一样！！！！
    while(first!=last)
    {
        ++first;
        ++n;
    }
    return n;
}

template<class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
_distance(InputIterator first,InputIterator last,random_access_iterator_tag){

    return last-first;
}


template<class InputIterator>
inline typename iterator_traits <InputIterator>::difference_type
distance(InputIterator first,InputIterator last){
    typename iterator_traits<InputIterator>::iterator_category category;/////!!!!!!!!不一样
    return _distance(first,last,category);
}

mark

  • 将迭代器i，丢给iterator_category（）函数，
  • 在iterator_category()函数里，通过traits函数获得category,返回一个category（）对象

mark

  • 左侧为想法，不是最终实现
  • 引发拷贝复制函数
    • has trival op=() 如果 op= 不重要
    • has non-trivial op=[] 如果op=重要
  • type traits 问iterator 你的op=是否重要
    • eg. complex 拷贝构造函数不重要

mark

mark

  • 算法的效率和它能不能判断迭代器的分类有很大关系

mark

  • unique_copy 如果重复的就不copy

mark

  • 算法可以接受任意type的iterator
  • 但是算法的参数class name可以暗示，需要的参数

mark

算法源代码剖析

  • c++ 算法，符合右侧定义

mark

  • accumulate 累计，不一定是+
  • iterator符合前闭后开区间
  • 一个函数对象，像函数的object，或者仿函数 重载opertor()

mark

  • 在一段区间，在一段范围，对每一个元素做一件事情

mark

  • replace 将旧值替换为新值
  • replace_if 根据条件， 条件为真，将该元素替换为value
  • replace_copy

mark

  • 左边全局函数，右边容器成员函数

  • count 相等 则加1

  • count_if 条件满足，则加1

mark

mark

  • myvec.rbegin() reverse iterator
  • myvec.rend()

mark

  • 不能违反前闭后开规则
  • rbegin 通过end() 套结一个适配器

mark

  • binary_search 必须之前先排序

  • lower_bound: 在不违反排序的情况下，20 能够安插进去的最低位置

  • upper_bound:在不违反排序的情况下，20 能够安插进去的最高位置

mark

仿函数和函数对象

mark

  • 重载operator()的class
  • 算术类
  • 逻辑运算类
  • 相对关系类

1541332986486

mark

  • less() 用默认的比较方式。()创建一个对象

  • 黄色binary_function

  • myclass 没有继承binary_function就没有融入STL
    mark

  • unary 一个操作数

  • binary 两个操作数

  • 如果有子类继承者两个0 class，这两个class的大小就真的为0

  • adapter 问functor问题，functor继承unary,binary 才能回答问题

  • 1
    //public std::binary_function  c++11中被废弃 c++17被删除

mark

多种adapter

  • 根据所要改造的object，命名相应的名字
  • functor adapter / iterator adapter/container adapter
  • A 改造B，A做主要的事由B做，B为幕后
    • A继承B
    • A内涵B composition 主要！！！
    • A 作为一个函数模板 里有B一个functor，

mark

mark

函数适配器

binder2nd

  • 绑定第二个参数

  • less()一个object

  • 修饰functor后，也要变成functor的样子，重载operator()

    • 修饰容器后，也要变成容器的样子

  • 模板类不能实参推导

  • 函数模板可以做实参推导，东西放到函数模板后，是什么类型type

    • 函数模板bind2nd里有个functor binder2nd

  • bind2nd 返回一个binder2nd object;

  • binder2nd(op,arg2_type(x)) 构造函数一个Object,记录到op,value

  • binder2nd重载 operator() 因为最终还是要通过operation()调用less 函数

  • 执行(pred(*first) 调用op(x,value))

  • typename Operation::second_argument_type 一个类型

    • 帮助编译器通过这个代码，编译时，不知道opertion::second_argument_type，

  • typedef typename Operation::second_argument_type arg2_type 将这个类型 重新起个名字

  • binder2nd 如果也要继续被adapter时，也要继承unary_function

mark

mark

  • 左边现在，右边过时

mark

not1

1541415116929

bind

  • _1 _2 _3占位符号 using namespace std::placeholders

    • 保留参数

  • my_divide ===function

  • std::dividemydivide ====function objects

  • bind 绑定返回类型

    • 如果没有返回类型就是它所绑定的 object的返回类型

member :

  • membe function—- &MyPair::multiply 隐藏argument this
  • cbegin const begin，不能改内容

bind(less,_1,50) //第一个参数不能给，是v.cbegin 到v.cend()之间的元素

mark

reverse_iterator

  • iterator adapter
  • 逆向取值= 正向-1 再取值

mark

ostream_iterator

  • x 未知 适配器

  • 不属于 container/functor/iterator/ adapter

  • “,” 作为分隔符

mark

istream_iterator

  • 创建一个对象时，就已经在读了。
  • operator++ 时在等待输入

mark

mark

万用的hash-function

  • 将customer 作为元素放入容器，设计hash_cunction

  • 一个class 重载operator()

    • Unordered_set<Customer,CustomerHash>

  • 一个函数 size_t(*)(const Customer&) 函数类型

    • unordered_set<Customer, size_t(*)(const Customer&)>
    • cutset(20,customer_hash_func)使用时，传递函数地址

mark

  • hash()(c.fname) 一个class对象调用operator()
  • TR1版本 1 2 3 4 .
  • template<typename… Types> 1 接收任意个数的模板参数
  • seed pass by reference

mark

mark

mark

  • hh()%11 得到元素应该放到第几个bucket

mark

  • 写一个hash版本

mark

mark

tuple 用例

  • 允许在声明一个组合体时，可以任意个数，任意类型

  • tuple<string,int,int,complex> t;

  • get<0>(t1)

  • auto t2=make_tuple(22,44,”stacy”);

  • get<1>(t1)=get<1>(t2);

  • 如果t1 t2 有相同成分，t1<t2

  • t1=t2

  • tie(i1,f1,s1)=t3;// assigns values of t3 to i1,f1,s1

  • typedef tuple<int,float,string>TupleType…… tuple_size(TupleType)::value

  • tuple_element<1,Tuple_Type>

mark

1
2
3
4
5
6
//继承方式实现递归
template <> class tuple(){}; // 终止条件
class tuple <Head,Tail...>：private tuple<Tail...>
{

}
  • typename Head::type head(){return m_head;} //
  • inherited & tail (){return *this;} //this 原来指三个元素，经inherited& tail 转型后，指两个元素

mark

type traits

  • G2.9版假设默认构造，复制构造，析构，拷贝赋值都重要
  • 特别class 带有指针。或者析构函数要关掉一个窗口，一个文件，一个锁
  • 算法 去问： _type_traits::has_trivial_destructor

mark

  • POD plain old data 没有function，只有数据，c版本的struct
  • 新版本 不需要对自己的class，不需要自己写偏特化

mark

mark

mark

mark

  • 丢进去一个string
  • 字符串不会当做父类，没有vitual destructor

mark

mark

mark

  • && move contstructor

  • Zoo(const Zoo&) =delete; 复制构造函数 没有

  • Zoo(Zoo&&) move constructor

  • mark

type_traits 实现

  • 模板+typedef

  • 移除const volatile _is_void_helper<typename remove_cv<__TP>::type>::type;

  • template

    • struct _is_void_helper: public false_type{};

  • template<>

    • struct _is_void_helper: public true_type{};

mark

mark

  • 可能 编译器 实现
  • grep 命令找

mark

cout

  • 一个对象object不是class
  • extern 这个东西可以被外界使用

mark

moveable 元素对容器速度效能影响

  • 元素类型加不加move这个功能，影响很大
  • 元素有move功能，调用Mctor 否则调用CCtor
  • MCtor move ctor vector两倍增长
  • CCtor

mark

  • list 一个萝卜一个坑
  • CCtor Mctor =300000
  • 之后的容器会扩充的是一个一个结点

mark

mark

  • 浅拷贝 就是Move的动作
  • 把原来的指针销掉，建立一个新的指针指向对象

mark

1541593229584

测试函数

  • std::move(c1) 调用move版本

  • 3百万个元素，3百万个指针，move版本

  • Move copy后，之前的那个指针就不能用了

    • 比如 临时对象temp
    • 见到临时对象，自动调用move版本 如果有的话
    • c1.insert(ite,V1type(buf))

  • M c11(c1) c1 不是临时对象，编译器不调用move版本

  • M c12(std::move(c1)) 强制调用move版本

mark

  • vector 深拷贝

  • vector 本身浅拷贝

  • M c12(std::move(c1) )

    • 把三根指针交换
    • unspecified 未指明的，未加规定的;未特别指定（规定）的;未详细说明的

1541636127973

1541636621199

本文标题:STL_note

文章作者:bliss7

发布时间:2018-11-08, 00:00:00

最后更新:2019-07-23, 11:14:11

原始链接:blissseven.top/2018/11/08/STL-note/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. STL
    1. 1.1. headers,版本，资源
    2. 1.2. STL 体系结构
      1. 1.2.1. 前闭后开区间
    3. 1.3. 容器分类和测试
      1. 1.3.1. 容器结构与分类
      2. 1.3.2. vector test
      3. 1.3.3. list test
      4. 1.3.4. deque test
      5. 1.3.5. stack test
      6. 1.3.6. queue test
      7. 1.3.7. multiset test
      8. 1.3.8. multimap test
      9. 1.3.9. unordered_multiset test
      10. 1.3.10. unordered_multimap test
      11. 1.3.11. set test
      12. 1.3.12. map test
    4. 1.4. 分配器测试
    5. 1.5. 源代码分布(vc gcc)
    6. 1.6. OOP VS GP
    7. 1.7. 操作符重载和模板
    8. 1.8. 分配器 Allocator
      1. 1.8.1. VC6 allocator使用
      2. 1.8.2. BC5 STL 对allocator 使用
      3. 1.8.3. G2.9 对allocator使用
      4. 1.8.4. GCC4.9 allocator
    9. 1.9. 容器之间的实现关系和分类
    10. 1.10. list 深度探索
    11. 1.11. vector 深度探索
    12. 1.12. array forward_list 深度探索
    13. 1.13. forward list
    14. 1.14. deque queue stack 深度探索
    15. 1.15. rb tree深度探索
    16. 1.16. set multiset深度探索
      1. 1.16.1. map multimap 深度探索
    17. 1.17. hashtable 深度探索
    18. 1.18. hash_set hash_multiset hash_map hash_multimap 概念
    19. 1.19. unordered 容器概念
    20. 1.20. 算法的形式
    21. 1.21. 迭代器分类对算法的影响
    22. 1.22. 算法源代码剖析
    23. 1.23. 仿函数和函数对象
    24. 1.24. 多种adapter
    25. 1.25. 函数适配器
      1. 1.25.1. binder2nd
      2. 1.25.2. not1
      3. 1.25.3. bind
      4. 1.25.4. reverse_iterator
      5. 1.25.5. ostream_iterator
      6. 1.25.6. istream_iterator
    26. 1.26. 万用的hash-function
    27. 1.27. tuple 用例
    28. 1.28. type traits
    29. 1.29. type_traits 实现
    30. 1.30. cout
    31. 1.31. moveable 元素对容器速度效能影响
    32. 1.32. 测试函数