STL容器之list

​ 1.封装除了对数据的保护、更好地管理数据之外，还有实现了对上层的统一；

​ 2.类模板参数的不同，一方面是为了实例化出来不同的类，另一方面是为了实现类的成员函数的不同；

一、认识list

​ 1.list是一种带头双向循环链表。相较于vector的最大优点就是支持了头插头删，而且时间复杂度是O1；2.list不支持+，因为链表不是一段连续的空间，重载实现得遍历一遍，代价太大，但是却支持了迭代器++，可以用迭代器遍历查找，或者算法find配合查找；3.迭代器循环访问使用!=不是<，是因为空间可能是不连续的；4.insert不存在迭代器失效问题，erase存在。

1.默认成员函数

explicit list (const allocator_type& alloc = allocator_type());
explicit list (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());
template 
list (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());
list (const list& x);
1
2
3
4
5

2.迭代器

iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
1
2
3
4
5
6
7
8

3.空间

bool empty() const;
size_type size() const;
1
2

4.元素访问

reference front();
const_reference front() const;
reference back();
const_reference back() const;
1
2
3
4

5.成员类型

​ InputIterator涉及到父子类关系，一般都可以使用。

​ 迭代器按容器底层结构分为：单向迭代器可以++，双向迭代器可以++ --，随机迭代器可以++ – + -。

​ 单向迭代器forward iterator：forward_list/(哈希)unordered_map/unordered_set

​ 双向迭代器bidirectional iterator：list/map/set

​ 随机迭代器random iterator：vector/string/dequeue/

//与vector类似，除了迭代器类型发生了变化，变成了双向迭代器
1

6.成员修改

void push_front (const value_type& val);
void pop_front();
void push_back (const value_type& val);
void pop_back();
iterator insert (iterator position, const value_type& val);
void insert (iterator position, size_type n, const value_type& val);//配合算法的find（迭代器区间），迭代器区间的设计统一为左闭右开。
template 
void insert (iterator position, InputIterator first, InputIterator last);
iterator erase (iterator position);
iterator erase (iterator first, iterator last);
1
2
3
4
5
6
7
8
9
10

7.其他操作

reserve()//与库里面实现的功能是一样的，较为冗余
sort()//算法库里面的不支持使用的是快排，因为库里面使用的是随机迭代器，而list的迭代器是双向的迭代器不支持。list的sort底层使用的是归并排序
//如果要排序，最好用vector，效率远大于list。
merge()//归并，使用前需要先排序，归并结果才正确
unique()//去重，使用前需要先排序，效率会提高
remove()//find+erase，找到了删除，找不到什么都不做
splice()//将一个链表的节点，转移到另一个链表，全部转移，转移一个节点，区间转移
1
2
3
4
5
6
7

二、模拟实现list

1.命名空间

namespace List
{
    template 
    struct list_node
    {
        list_node(const T &val = T()) : next_(nullptr), prev_(nullptr), val_(val) {}
        list_node *next_;
        list_node *prev_;
        T val_;
    };

    template 
    struct list_iterator
    {
        //迭代器内嵌类型
        typedef list_node node;
		// 迭代器的构造函数
        __list_iterator(node *node) : node_(node) {}
        // 迭代器的成员
        node *node;
    };
    
    template 
    class list
    {
        typedef list_node node;
        
	public:
        typedef __list_iterator iterator;
        typedef __list_iterator const_iterator;
        
    public:
        list() : head_(nullptr)
        {
            head_ = new node;
            head_->next_ = head_;
            head_->prev_ = head_;
            head_->val_ = T();
        }
		~list()
        {
            delete head;
            head
        }
        
    private:
        node *head_;
    };
}
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

2.成员变量

private:
	node *head_;
	size_t size_;
1
2
3

3.普通成员函数

void push_back(const T &val)
{
    insert(end(), val);
}
void push_front(const T &val)
{
    insert(begin(), val);
}
void pop_back()
{
    erase(--end());
}
void pop_front()
{
    erase(begin());
}
iterator insert(iterator pos, const T &val)
{
    // 对于带头双向循环链表不需要检查pos的合法性。
    // 1.将迭代器转换为节点指针，便于访问数据
    node *cur = pos.node_;
    // 2.创建新节点
    node *newnode = new node(val);
    // 3.建立连接
    node *prev = cur->prev_;
    prev->next_ = newnode;
    newnode->prev_ = prev;
    newnode->next_ = cur;
    cur->prev_ = newnode;
    size_++;
    return newnode;
}
iterator erase(iterator pos)
{
    assert(pos != end()); // 不能删除哨兵位头节点
    node *cur = pos.node_;
    node *prev = cur->prev_;
    node *next = cur->next_;
    prev->next_ = next;
    next->prev_ = prev;
    delete cur;
    cur = nullptr;
    size_--;
    return next;
}
size_t size()
{
    // 每次都要遍历，时间复杂度是On
    //  size_t sz = 0;
    //  iterator it = begin();
    //  while (it != end())
    //  {
    //      ++sz;
    //      ++it;
    //  }
    //  return sz;
    return size_;
}
void clear()
{
    iterator it = begin();
    while (it != end())
    {
        it = erase(it);
    }
}
void empty_init()
{
    head_ = new node;
    head_->next_ = head_;
    head_->prev_ = head_;
}
void swap(list <)
{
    std::swap(head_, lt.head_);
    std::swap(size_, lt.size_);
}
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

4.迭代器类的定义

//1.不写拷贝构造，内置类型浅拷贝已经满足，析构函数对内置类型不做处理，这样使得迭代器类满足只访问和修改，不参与节点的创建和销毁
//2.vector与string使用指针做迭代器，是因为它们的底层结构使用指针天然支持迭代器，比如 ++、！=、*等，都是直接就满足要求的，而list需要自己设计，来符合这种上层统一的像指针一样访问数据的方法。
template 
struct __list_iterator
{
   		// 迭代器的内嵌类型
        typedef list_node node;
        typedef __list_iterator self;

        // 迭代器的构造函数
        __list_iterator(node *node) : node_(node) {}

        // 迭代器的普通成员函数
        Ref operator*()
        {
            return node_->val_;
        }
        // 如果value是一个自定义对象，而想要访问的是对象的成员，但是直接解引用就是对象本身，而不是对象的成员，还需要对象.成员的操作来访问
        // 使用箭头就可以直接访问到成员
        // iterator->返回的是val的地址，iterator->成员转化成了地址成员，应该是地址->成员，所以猜测编译器进行了特殊处理，将iterator->成员识别
        // 成了iterator->->成员，即为了增强可读性，做了优化
        Ptr operator->()
        {
            return &(node_->val_);
        }
        self &operator++()
        {
            node_ = node_->next_;
            return *this;
        }
        self operator++(int)
        {
            self tmp(node_);
            node_ = node_->next_;
            return tmp;
        }
        self &operator--()
        {
            node_ = node_->prev_;
            return *this;
        }
        self operator--(int)
        {
            self tmp(node_);
            node_ = node_->prev_;
            return tmp;
        }
        bool operator!=(const self &it) const
        {
            return node_ != it.node_;
        }
        bool operator==(const self &it) const
        {
            return node_ == it.node_;
        }

        // 迭代器的成员
        node *node_;
};
//const迭代器的设计
//1.首先const迭代器本身要允许++，即允许自身改变，而typedef const __list_iterator iterator;
//则是对象本身不允许修改。2.只要改变*运算符重载，返回值const修饰，不允许修改即可。3.直接设计const迭代器类，过于冗余，可以增加模板参数来实现对返回值和参数的修改。
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

5.迭代器

iterator begin()
{
    return head_->next_; // 隐式类型转换加拷贝构造，优化为构造
}
iterator end()
{
    return head_;
}
const_iterator begin() const
{
    return head_->next_; 
}
const_iterator end() const
{
    return head_;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6.默认成员函数

// 默认成员函数
list() : head_(nullptr), size_(0)
{
    empty_init();
}
// list(const list <) : head_(nullptr), size_(0)
list(const list <) : head_(nullptr), size_(0)
{
    // 初始化哨兵位头节点
    empty_init();
    // 遍历拷贝
    for (auto &e : lt)
    {
        push_back(e);
        // list内部存放的是一个头节点，可以通过头节点找到并访问普通节点中所存放的值。而vector内部一大块空间，所以可以实现赋值。
    }
}
// list &operator=(list lt)//在类内，语法上支持直接用类名替换类型，成员函数也支持
list &operator=(list lt)
{
    swap(lt);
    return *this;
}
~list()
{
    clear();
    delete head_;
    head_ = nullptr;
}
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

7.内嵌类型

private：
	typedef list_node node;
public:
	typedef __list_iterator iterator;
    typedef __list_iterator const_iterator;
1
2
3
4
5