走进STL - 序列式容器（常用篇）
【摘要】 本篇属于容器进阶部分，如果需要快速上手，可以看： 走近STL - vector，初次见面 走近STL - 你好，list 走近STL - map，只愿一键对一值
文章目录
1、vector1.1 vector类设计1.2 vector其他 2、list2.1 节点设计2.2 迭代器设计2.3 数据结构
在序列式容器的大家庭里，比较常用的还是...
本篇属于容器进阶部分，如果需要快速上手，可以看：
走近STL - vector，初次见面
走近STL - 你好，list
走近STL - map，只愿一键对一值
1、vector
文字表诉的部分文章开头的那篇博客基本讲完了，我们直接来看vector的定义摘要。
代码中没见过的函数，一般都可以在前一篇博客中找到答案：走进STL - 空间配置器，STL背后的故事
哈哈，先把工具包都备齐。然后看代码：
1.1 vector类设计
/*alloc是SGI STL的空间配置器*/
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; //以下simple_alloc属于SGI STL 空间配置器
typedef simple_alloc<value_type,Alloc> data_allocator;
iterator start; //表示目前使用的空间的头
iterator finish;//表示目前使用的空间的尾
iterator end_of_storage; //表示目前可用的空间的尾
void insert_aux(iterator position,const T& x);
void deacllocate()
{
if(start) data_allocator::deallocate(start,end_of_storage - start);
}
void fill_initialize(size_type n,const T& value)
{
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 - end();}
bool empty() const {return end_of_storage == end();}
reference operate[](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_initialize(n,T());}
~vector()
{
destroy(start,finish);
deallocate();
} reference front(){return *begin();}
reference back(){return *end();}
void push_back(const T& x)
{
if(finish !=end_of_storage)
{ construct(finish,x); ++finish;
}
else insert_aux(end(),x);
}
void pop_back()
{
--finish;
destroy(finish);
}
//从这里可以看出是直接覆盖原位置数据，然后回收最后一个节点
iterator erase(iterator position)
{
if(position +1 != end()) copy(position + 1,finish,position); //这个函数属于算法 将后续元素前移
--finish;
destroy(finish);
return position;
} void resize(size_type new_size,const T& x)
{
if(new_size<size()) erase(begin()+new_size,end());
else insert(end(),new_size - size(),x);
} void resize(size_type new_size){resize(new_size,T());}
void clear(){erase(begin(),end());}
protect:
//配置空间并填满
iterator allocate_and_fill(size_type n,const T& x)
{
iterator result = data_allocator::allocate(n);
uninitialized_fill_n(result,n,x); //内存配置函数，不过那篇太长了，我就吧un-这一块给咔嚓了
return result；
}
}
- 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
1.2 vector其他
源码之前，了无秘密。我还能补充啥？还能补充的在文章开头那篇关于vector的文章里面也都说完了。。。
2、list
关于list的节点设计、迭代器设计、数据结构，题头那篇已经详尽。
list增删的坑，可以看：走近STL - 填上List删除的大坑
好，我们也是直接看源码吧，其实和上面的vector有很多相通之处的。
2.1 节点设计
//为了完整性，我们还是先看一下节点设计
template <class T>
struct __list_node
{
typedef void * void_pointer;
void_pointer prev;
void_pointer next;
T data;
} //显然，这是一个双向链表，图就不再画一遍了
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
2.2 迭代器设计
//list的迭代器不像vector，普通指针是不行的
//以下是list迭代器的设计
template <class T,class Ref,class Ptr>
struct __list_iterator
{
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type; typedef __list_node<T>* link_type;
typedef __list_iterator<T,T&,T*> iterator;
typedef __list_iterator<T,Ref,Ptr> self;
typedef bidirectional_iterator_tag iterator_category; link_type node; //用于指向内部节点 //构造函数
__list_iterator(link_type x):node(x){}
__list_iterator(){}
__list_iterator(const iterator& x):node(x.node){}
//运算符重载
bool operator==(const self& x) const {return node == x.node}
bool operator!=(const self& x) const {return node != x.node} reference operator*() const {return (*node).data;}
pointer operator->() const {return &(operator*());}
self& operator++() //对节点进退操作，vector中并没有重载这些
{
node = (link_type)((*node).next);
return *this;
}
self& operator++(int)
{
self tmp = *this;
++*this;
return tmp;
}
self& operator--()
{
node = (link_type)((*node).prev);
return *this;
}
self& operator++(int)
{
self tmp = *this;
++*this;
return tmp;
}
}
- 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
2.3 数据结构
SGI list 不止是一个双向链表，它还是环状的。所以它只要一个指针便可以遍历整个链表。
如果让指针node指向刻意置于尾端的一个空白节点，node便能符合STL“前闭后开”的原则。
至于和vector重复的方法像begin()这些的就不再提一遍了。
对于list的构造与管理如果想再试一下可以看文章头那篇 《你好，list》,里面已经写好了测试代码。
我们来看看list特有的方法：
//首先争议比较大的删除函数先看
//都没必要争议，源码之前，了无秘密
iterator erase(iterator position)
{
link_type next_node = link_type(position.node->next);
link_type prev_node = link_type(position.node->prev);
//先吧前后都接管了
//接下来把前后无缝对接
prev_node->next = next_node;
next_node->prev = prev_node;
//然后把那个节点回收
destory_node(position.node);
return iterator(next_node); // 看清楚返回值
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
算了，算法部分放到后面算法区写吧
这篇就到这里啦
- 1
文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。
原文链接：lion-wu.blog.csdn.net/article/details/105495905
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）