• 欢迎光临~

STL源码剖析笔记:Vector、List

开发技术 开发技术 2022-07-19 次浏览

一、Vector

特点:连续线性空间

<stl_vector.h>

 1 typedef T value_type;
 2 typedef value_type* pointer;
 3 typedef value_type* iterator;     //vector的迭代器是普通指针 => vector<int>::iterator ite;   ite的类型是int*
 4 typedef value_type& reference;
 5 typedef size_t size_type;
 6 typedef ptrdiff_t difference_type;
 7 
 8 iterator start;                   //空间头
 9 iterator finish;                  //空间尾
10 iterator en_of_storage;     //可用空间尾
11 
12 iterator begin() {return start;}
13 iterator end() {return finish;}
14 size_type size() const {return size_type(end()-begin());}
15 size_type capacity() const {return size_type(end_of_storage-begin());}
16 bool empty() const {return begin() == end();}
17 reference operator[] (size_type n){return *(begin()+n);}
18 
19 reference front(){return *begin();}         //第一个元素
20 reference back(){return *(end()-1);}      //最后一个元素
21 void push_back(const T& x){                  //将元素插入尾端
22     if(finish != end_of_storage){
23         construct(finish,x);
24         ++finish;
25     }
26     else
27         insert_aux(end(),x);
28 }     
29 void pop_back(){                                   //尾端元素取出
30     --finish;
31     destory(finish);
32 }   
33 iterator erase(iterator position){             //清除某位置上的元素
34     if(position+1 != end())
35         copy(positon+1,finish,position);     //后续元素往前移动
36     --finish;
37     destory(finish);
38     return position;
39 }
40 void resize(size_type new_size, const T& x){
41     if(new_size<size())
42         erase(begin()+new_size,end());
43     else
44         insert(end(),new_size-size(),x);    
45 }
46 void resize(size_type new_size) {resize(new_size,T());}
47 void clear() {erase(begin(),end());}

Q. 增加新元素时超容会怎样?

A. 增加新元素时,如果超容,会重新配置一块2倍容量的空间。(为什么要重新配置?因为无法保证原空间还有可使用的连续内存空间)

然后将原内容拷贝到新空间,再构造新元素。

最后释放原空间。

时间复杂度:

插入 删除 访问

push_back

O(1)

pop_back

O(1)

O(1)

insert

O(n)

erase

O(n)

 

注意:插入操作要注意,一旦引起空间重新配置,指向原vector的迭代器就失效了。

 

二、List

特点:空间不连续;插入删除永远是常数时间;访问效率低。

注意:list节点和list本身是不同的结构

1 //双向链表
2 struct __list_node{      
3     typedef void* void_pointer;
4     void_pointer prev;    
5     void_pointer next;
6     T data;
7 }
 1 //双向迭代器
 2 struct __list_iterator{
 3     typedef __list_iterator<T,T&,T*>  iterator;
 4     typedef __list_iterator<T,Ref,Ptr>  self;
 5 
 6     typedef bidirectional_iterator_tag iterator_category;
 7     typedef T value_type;
 8     typedef Ptr pointer;
 9     typedef Ref reference;
10     typedef __list_node<T>* link_type;
11     typedef size_t size_type;
12     typedef ptrdiff_t difference_type;
13 
14     link_type node;    //普通指针,指向list节点
15 
16     ...
17 }
 1 //list 是一个双向环状链表,一个指针就可以遍历
 2 typedef __list_node<T> list_node;
 3 typedef list_node* link_type;
 4 link_type node;     //指向尾端空白节点,符合“前闭后开”
 5 
 6 iterator begin() {return (link_type)((*node).next);}
 7 iterator end() {return node;}
 8 bool empty() {return node->next == node;}
 9 size_type size() const {
10     size_type result=0;
11     distance(begin(),end(),result);
12     return result;
13 }
14 reference front() {return *begin();}
15 reference back() {return *(--end());}
 1 void push_front(const T& x) {insert(begin(),x);}
 2 void push_back(const T& x) {insert(end(),x);}
 3 iterator erase(iterator position){
 4     link_type next_node = link_type(position.node->next);
 5     link_type prev_node = link_type(position.node->prev);
 6     prev_node->next = next_node;
 7     next_node->prev = prev_ndoe;
 8     destory_node(position.node);
 9     return iterator(next_node);
10 }
11 void pop_front() {erase(begin());}
12 void pop_back() {
13     iterator tmp = end();
14     erase(--temp);
15 } 
16 void list<T,Alloc>::clear(){           //清空链表
17     link_type cur = (link_type) node->next;
18     while(cur != node){
19         link_type tmp = cur;
20         cur = (link_type) cur->next;
21         destory_node(tmp);
22     }
23     node-> next = node;
24     node -> prev = node;
25 }
26 void list<T,Alloc>::remove(const T& value){   //移除所有值为value的元素
27     iterator first = begin();
28     iterator last = end();
29     while(first != last){
30         iterator next = first;
31         ++next;
32         if(*first == value) erase(first);
33         first = next;
34     }
35 }
36 void list<T,Alloc>::unique(){                     //数值相同的连续元素只保留1个
37     iterator first = begin();
38     iterator last = end();
39     if(first == last) return;        //空链表,返回
40     iterator next = first;
41     while(++next != last){
42         if(*first == *next)
43             erase(next);
44         else
45             first=next;
46         next = first;
47     }
48 }

 迁移操作   transfer:

 1 //将[first,last)内的所有元素搬移到position之前
 2 void transfer(iterator position, iterator first, iterator last) {
 3     if (position != last) {
 4         (*(link_type((*last.node).prev))).next = position.node;  
 5         (*(link_type((*first.node).prev))).next = last.node;  
 6         (*(link_type((*position.node).prev))).next = first.node; 
 7         link_type tmp = link_type((*position.node).prev);   
 8         (*position.node).prev = (*last.node).prev;        
 9         (*last.node).prev = (*first.node).prev;    
10         (*first.node).prev = tmp;   
11     }
12 }

接合  splice

STL源码剖析笔记:Vector、List

 merge()、reverse()、sort()

 STL源码剖析笔记:Vector、List

  Q. vector可以用普通指针做迭代器,list可以吗?

A. 不行,因为vector内存连续所以可以。list内存不连续,list是一个双向链表,迭代器要具备前移、后移,所以list是双向迭代器(Bidirectional iterator)。

 时间复杂度:

插入 删除 访问

push_front

O(1)

pop_front

O(1)

O(n)

push_back

O(1)

pop_back

O(1)

insert

O(1)

erase

O(1)

程序员灯塔
转载请注明原文链接:STL源码剖析笔记:Vector、List
喜欢 (0)