【C++ 初阶】List底层框架模拟实现

目录

一、List框架搭建

1. List简介


  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代
  2. list的底层是带头双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。而forward_list是单链表,只能朝前迭代
  3. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率高。
  4. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,如访问中间的某个元素需要从头部或者未卜迭代到该位置,时间复杂度是O(N),list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

2. List的使用

【C++ 初阶】List底层框架模拟实现

3. List构造

3.1 构造一个空的list

list(){
    //带头双向循环
    _head = new Node(T()); //这里的构造不能传0,因此这里不一定是int类型的,这里T可能是vector,也可能是string对象
    _head->_next = _head;
    _head->_prev = _head;
}

3.2 拷贝构造

list(const list<T>& lt){
    //深拷贝
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    for(const auto& e : lt){
        push_back(e);
    }
}

3.3 用区间元素构造list

template<class InputIterator>
list(InputIterator first,InputIterator last){ //这里不仅仅支持链表的初始化,而且还支持string或者vector的迭代器
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    while(first != last){
        push_back(*first);
        ++first;
    }
}

【C++ 初阶】List底层框架模拟实现

4. List节点

template<class T>
struct __list_node{
    __list_node<T>* _next;
    __list_node<T>* _prev;
    T _data;
    
    __list_node(const T& x = T()) //给个匿名对象去初始化
        :_next(nullptr)
        , _prev(nullptr)
        ,_data(x)
    {}
    };

5. 迭代器框架实现

List 的迭代器
迭代器有两种实现方式,具体应根据容器底层数据结构实现:

  1. 原生态指针,比如:vector
  2. 将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下

方法:

  1. 指针可以解引用,迭代器的类中必须重载operator*()
  2. 指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()
  3. 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)
    至于operator–()/operator–(int)释放需要重载,根据具体的结构来抉择,双向链表可以向前 移动,所以需要重载,如果是forward_list就不需要重载–
  4. 迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()

这里typdef的__list_iterator里带了三个参,其中第二和第三个类模版分别用于决定operator*()返回什么样类型的的对象 和 用于operator->()返回当前节点的数据

template<class T>
    class list
    {
        typedef __list_node<T> Node;
    public:
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;
        
        iterator begin(){
            return iterator(_head->_next);
        }
        
        iterator end(){
            return iterator(_head);
        }
        
        const_iterator begin() const{
            return const_iterator(_head->_next);
        }
        
        
        const_iterator end() const {
            return const_iterator(_head);
        }
        
	private:
	   Node* _head;
 };

6. 赋值重载

//解引用
Ref operator*(){
    return _node->_data;
}
    
Ptr operator->(){
    return &_node->_data;
}
    
// ++it
self& operator++(){
    _node = _node->_next;
    return *this;
}
    
// it++
self operator++(int){ //后置++
    self tmp(*this);
    _node = _node->_next;
    return tmp;
}
    
// --it
self& operator--(){
    _node = _node->_prev;
    return *this;
}
    
// it--
self operator--(int){ //后置--
    self tmp(*this);
    _node = _node->_prev;
    return tmp;
}

//比较是否相等
bool operator!=(const self& it){
    return _node != it._node;
}
    
bool operator==(const self& it){
    return _node == it._node;
}

7. 关于List的容量

遍历一遍,直到遇到带头后结束

size_t size(){
    size_t n = 0;
    iterator it = begin();
    while(it != end()){
        ++it;
        ++n;
    }
    return n;
}
        
bool empty(){
    return begin() == end();
}

8. List添加新节点

iterator insert(iterator pos, const T& x){
    Node* cur = pos._node; //当前节点
    Node* prev = cur->_prev;
    
    Node* newnode = new Node(x);
    prev->_next = newnode;
    newnode->_prev = prev;
    
    newnode->_next = cur;
    cur->_prev = newnode;
    
    return iterator(newnode); //反回新插入节点
}

void push_back(const T& x){
	insert(end(), x)
}

void push_front(const T& x){
    insert(begin(), x);
}

9. 删除一个节点

由于list数据结构的特点决定了不能像数组一样实现O(1)访问任意节点,所以标准库里只提供了头删和尾删

iterator erase(iterator pos){
    assert(pos != end());
    
    Node* cur = pos._node;
    Node* pre = cur->_prev;
    Node* next = cur->_next;
    
    delete cur;
    pre->_next = next;
    next->_prev = prev;
    
    return iterator(next);
}

void pop_back(){
    erase(--end());
}

void pop_front(){
    erase(begin());
}

10. 清空链表和析构

这里需要注意的是只有当实例化对象开辟了空间后才析构,否则进入clear函数后会报错

void clear(){
	iterator it = begin();
	while(it != end()){
	it = erase(it);
}
~list(){
    clear();
    delete _head;
    _head = nullptr;
}

二、完整代码

Gitee链接

上一篇:Linux中chown和chmod的区别和用法(忘记了,查了下资料,记录下,)


下一篇:linux常用命令 - find命令之exec