STL剖析(vector,string)

本文总阅读量次

STL概论

长久以来软件届一直希望建立一种可复用的东西，以及一种得以造出“可重复运用东西”的方法。

子程序、程序、函数、类别、函数库、类别库、组件、结构模块化设计、模式、面向对象 …

都是为了 复用性的提升

复用性必须建立在某种标准之上，但是在许多环境下开发最基本的算法和数据结构还迟迟不能有标准。大量程序员从事重复劳动，完成前人完成而自己不拥有的代码。

为了建立数据结构算法的标准，降低耦关系，提升独立性、弹性，交互操作性，诞生了STL

string

string类的实现是基础的题目,首先给出string的原型

1
2
3
4
5
6
7
8
9
10
11
12
class String{
public:
    String(const char* str = NULL）; //普通构造函数
    String(const String &other); //拷贝构造函数
    ~String(); //析构函数
    String & operator = (const String &other); //重载运算符
    String & operator + (const String &other); //重载运算符
    bool operator == (const String &other); //重载运算符
    int getLength(); //得到长度
private:
     char *m_data;
}
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
String::String(const char* str){
    if (str == NULL) {
        m_data = new char[1];
        *m_data = '\0';
    } else {
        int length = strlen(str);
        m_data = new char[length+1];
        strcpy(m_data, str);
    }
}

String::~String(){
    if (m_data) {
        delete[] m_data;
        m_data = 0;
    }
}
String::String(const String &other){
    if (!other.m_data){
        m_data = 0;
    }
    m_data = new char[strlen(other.m_data)+1];
    strcpy(m_data, other.m_data);
}
String& String::operator = (const String &other){
    if(this != &other){
        delete[] m_data;
        if(!other.m_data){
            m_data = 0;
        } else {
            m_data = new char[strlen(other.m_data)+1];
            strcpy(m_data, other.m_data);
        }
    }
}
String & String::opreator+(const String  &other){
    String newString;
    if(!other.m_data){
        newString = *this;
    }else if(m_data){
        newString=other;
    }else{
        newString.m_data = new char[strlen(m_data)+strlen(other.data)+1];
        strcpy(newString.m_data,m_data);
        strcat(newString.m_data,other.m_data);
    }
    return newString;
}

vector

vector 是线性容器，它的元素线性排列，和动态数组类似。它的元素储存在一块连续的空间中，这意味着他不仅可以用迭代器访问、还可以通过指针偏移访问，vector能自动储存元素

  • 下标访问个别元素
  • 不同的方式遍历元素
  • 容器末尾增加、删除元素
1
2
3
4
5
// 迭代器
vector<int>::iterator iter;
for(it = con.begin(); it!=con.end(); it++){
    cout<<*it<<endl;
}

关于STl容器，只要不超过最大值，其可以自动增长到足以容纳用户放进去的数据大小。（这个容量值，可以同过调用maxsize()来获得）

对于vector和string，如果需要更多的空间，类似realloc思想增长，vector支持随机访问，因此提高了效率，内部通过动态数组实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//vector 查找
vector<int>::iterator iter;
iter = find(vec.begin(),vec.end(),3);

//vector 删除
vector<int>::iterator iter;
while(iter!=vec.end()){
    if(*iter==target){
        iter = erase(iter);
    }else{
        iter++;
    }
}

//vector 增加
iterator insert(iterator loc, const TYPE &val);
void insert(itrator loc, size_type num, const TYPE &val);
void insert(itrator loc, itrator start, itrator end);

vector 的内存管理

1，使用reverse() 提前设定容量大小

STL最令人称赞的特性之一就是只要不超过最大值，其可以自动增长。如果需要更多空间就会类似realloc的思想来增长大小。vector容器支持随机访问，因此效率较高。 如果有大量的元素需要push_back，应提前使用reverse函数提前设定，避免多次的扩容操作，介绍一下只有vector与string提供的几个函数

函数名 介绍
size() 获得容器中的元素个数，但不能获得容器为他分配的容器大小
capacity() 获得容器已经分配的内存容纳多少元素。
resize() 用来强制把容器改为容纳n个元素。如果n小于当前大小，尾部元素会被销毁；如果n大于当前大小，默认构造元素添加到元素尾；如果大于当前容量，触发重新分配
reverse() 强制把容量改为不小于n，n不小于当前大小
  1. 交换技巧来修整内存
  2. swap强行释放内存
1
2
3
4
5
template<class T> void VlearVector(vector<T>& v)
{
    vector<T> vTemp;
    vTemp.swap(v);
}

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
template<typename T>
class myVector{
private:
    #define WALK_LENGTH 64;

public:
    // 构造函数
    myVector():array(0),theSize(0),theCapcity(0){}
    myVector(unsigned int n, const T& t):array(0),theSize(0),theCapacity(0){
        while(n--){
            push_back(t);
        }
    }
    // 拷贝构造函数
    myVector(const myVector<T>& other):array(0),theSize(0),theCapcity(0){
        *this = other;
    }
    
    // 重载赋值运算符
    myVector<T>& opreator = (myVector<T>& other){
        if(this == &ohter)
            return *this;
        clear();
        theSize
    }
}

第二版参考《stl源码》

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
template<class T, class Alloc=alloc>
class vector{
public:
	typedef T value_type;
	typedef value_type* pointer;
	typedef value_type* iterator;
	typedef value_type& reference;
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
protected:
	typedef simple_alloc<value_type, Alloc> data_allocator;
	iterator start;
	iterator finish;
	iterator end_of_storage;
	void insert_aux(iterator posotion, const T& x);
    void deallocate(){
    	if(start)
    		data_allocator::deallocate(start,end_of_storage-start);
    }
    void fill_initialize(size_type n, const T& vlaue){
    	start = allocate_and_fill(n, value);
    	finish = start + n;
    	end_of_storage = finish;
    }
public:
	iterator begin(){return start;}
	iterator end(){return finish;}
	size_type size() const {return size_type(end()-begin());}
	size_type capacity() const{return size_type(end_of_storage-begin());}
	bool empty() const {return engin()==end()}
	reference operator[](size_type n){return *(begin()+n);}
	vector():start(0),finish(0),end_of_storage(0){}
	vector(size_type n,const T& value){fill_initialize(n,value);}
	vector(int n,const T& value){fill_initialize(n,value);}
	vector(long n,const T& value){fill_initialize(n,value);}
	explicit vector(size_type n) {fill_initlialize(n,T());}
    ~vector(){
    	destroy(start,finish);
    	deallocate();
    }
    reference front(){ return *begin();}
    reference back() { return *(end()-1);}
    void push_back(const T& x){
    	if(finish!=end_of_storage){
    		construct(finish, x);
    		++finish;
    	}else
    		insert_aux(end(),x);
    }
    void pop_back(){
    	--finish;
    	destory(finish);
    }
    iterator erase(iterator position){
    	if(position+1 != end())
    		copy(position+1,finish,position);
    	--finish;
    	destory(finish);
    	return position;
    }
    void resize(size_type new_size, const T& x){
    	if(new_size<size())
    		erase(begin()+new_size(),end());
    	else
    		insert(end(),newsize()-size(),x);
    }
    void resize(size_type new_size){resize(new_size,T());}
    void clear(){erase(begin(),end());}
protected:
iterator allocate_and_fill(size_type n, const T& x){
		iterator result = data_allocatpr::
	}
}
template<class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x){
	if(finish != end_of_storage){
		construct(finish,*（finish-1));
		++finish;
		T x_copy = x;
		copy_backword(position, finish-2,finish-1);
		*position = x_copy;
    }else{
    	const size_type old_size = size();
    	const size_type len = old_size != 0?2*oldsize:1;
    	iterator new_start = data_allocator::allocate(len);
    	iterator new_finish = new_start;
        try {
        	new_finish = uninitialized_copy(start,posotion,new_start);
        	construct(new_finish, x);
        	++new_finish;
        	new_finish = uninitialized_copy(positon,finish,new_finish);
            } catch(...){
        	destroy(new_start,new_finish);
            data_allocator::deallocate(new_start,len);
            thow;
        }
        destroy(begin(),end());
        deallocate();
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start+len;
    }
}

map、set

  1. map的本质

map本质是一类关联式容器，属于模板类关联的本质在于元素的值与某个特点的键相关联，而并非通过元素在数组的位置获取。它的特点是增加和删除节点对迭代器的影响很小，除了要操作的节点，对其他节点都没什么影响。对迭代器来数不能修改键值，只能修改实值。map内部自建一颗红黑树（非严格意义的平衡二叉树），该树内部数据有序

  1. map的功能

自动建立Key-value的一一对应关系，map<int, string> mapStudent;

红黑树源码略（不研究了）

hashtable

hashtable被视为一种字典结构，提供对于任何有名项的存取操作和删除操作。

如何避免array过大？是用某种映射函数，使得元素映射至“大小可以接受的索引”，这个函数被称为散列函数。使用散列函数必然会带来一个问题：可能有不同的元素被映射到相同的位置，这便是所谓的碰撞问题。

碰撞问题一般有两种方案：拉链法、线性探测法

线性探测

提出一个名词：负载系数，元素个数除以表格大小。负载系数永远在0~1之间，

当 散列函数 计算某个位置，而该位置不可用该怎么办？ 最简单的方法就是循序接着往下找，只要表格足够大总会找到一个空间。而删除必须采取惰性删除（标记删除序号，实际删除待表格整理时再进行）

两个假设 1.表格足够大，2 每个元素独立 但实际情况往往不乐观，往往需要不断解决碰撞问题

二次探测

二次探测主要用来解决 主集团问题， 该方法描述很简单，碰撞时尝试 H+1*1，H+2*2, H+ 3*3来代替H+1, H+2,H+3 等。幸运的是，假设表格大小为质数，永远保持0.5以下的负载系数，每个新元素的插入查找不大于2

另外，二次探测有个简便的计算技巧

1
2
3
4
5
hi = h0 +  i\*i (MOD M)

hi-1 = h0 + (i-1) *(i-1) (MOD M)

整理得，hi = hi-1 + 2*i-1 (MOD M)

这样每一次迭代并不需要太大的计算资源。

开链

拉链法，在《源码》中被称为开链，及对于冲突的元素维护一个链表