Post

C++ STL Container List

Posted
By soong
8 min read
C++ STL Container List

List

  • based on gnu 2.9
  • 双向循环链表

Container

list node

1
2
3
4
5
6
7

template <class T>
struct __list_node {
  typedef void* void_pointer;
  void_pointer next;
  void_pointer prev;
  T data;
};

list

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

/*
    typedef void* void_pointer;
    typedef __list_node<T> list_node;
    typedef simple_alloc<list_node, Alloc> list_node_allocator;     
    typedef T value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef list_node* link_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef __list_iterator<T, T&, T*>             iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;
*/
template <class T, class Alloc = alloc>
class list{
    // 链表的尾节点
    link_type node;
    // iterator
    iterator begin() { return (link_type)((*node).next); }
    const_iterator begin() const { return (link_type)((*node).next); }
    iterator end() { return node; }
    const_iterator end() const { return node; }
    reverse_iterator rbegin() { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const { 
        return const_reverse_iterator(end()); 
    }
    reverse_iterator rend() { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const { 
        return const_reverse_iterator(begin());
    }
    // reference
    reference front() { return *begin(); }
    const_reference front() const { return *begin(); }
    reference back() { return *(--end()); }
    const_reference back() const { return *(--end()); }
    // 容量
    bool empty() const { return node->next == node; }
    size_type size() const {
        size_type result = 0;
        distance(begin(), end(), result);
        return result;
    }
    size_type max_size() const { return size_type(-1); }
    // 插入节点
    iterator insert(iterator position, const T& x) {
        link_type tmp = create_node(x);
        tmp->next = position.node;
        tmp->prev = position.node->prev;
        (link_type(position.node->prev))->next = tmp;
        position.node->prev = tmp;
        return tmp;
    }

    void push_front(const T& x) { insert(begin(), x); }
    void push_back(const T& x) { insert(end(), x); }
    // 删除节点
    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;
        destroy_node(position.node);
        return iterator(next_node);
    }

    void pop_front() { erase(begin()); }
    void pop_back() { 
        iterator tmp = end();
        erase(--tmp);
    }
}

Iterator

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

/*
    typedef __list_iterator<T, T&, T*>             iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;
    typedef __list_iterator<T, Ref, Ptr>           self;

    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef __list_node<T>* link_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
*/
template<class T, class Ref, class Ptr>
struct __list_iterator {
    typedef bidirectional_iterator_tag iterator_category;

    link_type 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*()); }
    // ++i
    self& operator++() { 
        node = (link_type)((*node).next);
        return *this;
    }
    // i++
    // 后++调用前++
    self operator++(int) { 
        self tmp = *this;
        ++*this;
        return tmp;
    }
    // --i
    self& operator--() { 
        node = (link_type)((*node).prev);
        return *this;
    }
    //i--
    self operator--(int) { 
        self tmp = *this;
        --*this;
        return tmp;
    }
};

Algorithm

两个链表是否元素相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

template <class T, class Alloc>
bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y) {
    // x和y的尾节点
    link_type e1 = x.node;
    link_type e2 = y.node;
    // x和y的首节点
    link_type n1 = (link_type) e1->next;
    link_type n2 = (link_type) e2->next;
    for ( ; n1 != e1 && n2 != e2 ; // 判空
            n1 = (link_type) n1->next, n2 = (link_type) n2->next){
        if (n1->data != n2->data) return false;
    }
    // 是否都遍历完
    return n1 == e1 && n2 == e2;
}

删除所有值为value的元素

1
2
3
4
5
6
7
8
9
10
11
12

template <class T, class Alloc>
void list<T, Alloc>::remove(const T& value) {
    iterator first = begin();
    iterator last = end();
    while (first != last) {
        iterator next = first;
        ++next;
        if (*first == value) erase(first);
        // 后移
        first = next;
    }
}

相邻元素去重

1
2
3
4
5
6
7
8
9
10
11
12
13

template <class T, class Alloc>
void list<T, Alloc>::unique() {
    iterator first = begin();
    iterator last = end();
    // 为空
    if (first == last) return;
    iterator next = first;
    while (++next != last) {
        if (*first == *next) erase(next);
        else first = next;
        next = first;
    }
}

将链表x按序合并到链表this

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/* 
transfer(position, first, last) {}
执行完后变成 position.prev->first->...->last->position->position->last
*/
template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x) {
    iterator first1 = begin();
    iterator last1 = end();
    iterator first2 = x.begin();
    iterator last2 = x.end();
    while (first1 != last1 && first2 != last2){
        if (*first2 < *first1) {
            iterator next = first2;
            transfer(first1, first2, ++next);
            first2 = next;
        }
        else ++first1;
    }
    if (first2 != last2) transfer(last1, first2, last2);
}

翻转链表

1
2
3
4
5
6
7
8
9
10
11
12

template <class T, class Alloc>
void list<T, Alloc>::reverse() {
    if (node->next == node || link_type(node->next)->next == node)  return;
    iterator first = begin();
    ++first;
    while (first != end()) {
        iterator old = first;
        ++first;
        // 相当于头插
        transfer(begin(), old, first);
    }
}

链表排序

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

// 归并排序 
// O(nlogn)
/*
this::splice(position, list, i)
将list链表中的i元素插入到this链表的position位置
*/
template <class T, class Alloc>
void list<T, Alloc>::sort() {
    if (node->next == node || link_type(node->next)->next == node) return;
    list<T, Alloc> carry;
    list<T, Alloc> counter[64];
    int fill = 0;
    while (!empty()) {
        carry.splice(carry.begin(), *this, begin());
        int i = 0;
        // 第i个counter最多放2^i个元素
        // 放满后移到下一个位置
        while(i < fill && !counter[i].empty()) {
            counter[i].merge(carry);
            // carry.swap(counter[i++]);
            carry.swap(counter[i]); i++;
        }
        // 遇到空counter, 将carry放到空的位置上, carry置空
        carry.swap(counter[i]);     
        // fill+1, 此时前fill个counter为空, 再从第0个counter开始放   
        if (i == fill) ++fill;
    } 
    // 归并所有counter
    for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]);
    swap(counter[fill-1]);
}

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

/*
算法流程模拟
*/
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>

void printList(const std::list<int>& lst) {
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

void printCounters(const std::vector<std::list<int>>& counters, int fill) {
    for (int i = 0; i < fill; ++i) {
        std::cout << "counter[" << i << "]: ";
        for (auto it = counters[i].begin(); it != counters[i].end(); ++it) {
            std::cout << *it << " ";
        }
        std::cout << std::endl;
    }
}

void sortList(std::list<int>& lst) {
    std::list<int> carry;
    std::vector<std::list<int>> counter(64); // 64 empty lists
    int fill = 0;

    std::cout << "Initial list: ";
    printList(lst);
    std::cout << std::endl;

    while (!lst.empty()) {
        // Move the first element of lst to carry
        carry.splice(carry.begin(), lst, lst.begin());
        std::cout << "Moved to carry: ";
        printList(carry);
        std::cout << "Remaining list: ";
        printList(lst);
        std::cout << std::endl;

        // Each counter[i] can hold up to fill elements, put carry into the first empty counter[i]
        int i = 0;
        while (i < fill && !counter[i].empty()) {
            counter[i].merge(carry);
            carry.swap(counter[i]);
            ++i;
        }
        carry.swap(counter[i]); // Ensure carry is empty after swapping
        if (i == fill) ++fill;

        std::cout << "After merge and swap: " << std::endl;
        printCounters(counter, fill);
        std::cout << std::endl;
    }

    // Merging all counters
    for (int i = 1; i < fill; ++i) {
        counter[0].merge(counter[i]);
    }
    carry.swap(counter[0]);

    std::cout << "Final sorted list: ";
    printList(carry);
}

int main() {
    std::list<int> lst = {16,15,14,13,12,11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    sortList(lst);
    return 0;
}
C++, STL
STL
This post is licensed under CC BY 4.0 by the author.