当前位置:   article > 正文

C++STL之双向链表list_双向列表 operator=

双向列表 operator=

一、list的基本使用以及耗时测试:

#include<list>
#include<cstdlib>//qsort bsearch NULL
#include<ctime>
using namespace std;

const int SIZE = 100000;
int main()
{
	list<int>l;//定义一个链表容器对象l,第二个参数使用默认allocator
	clock_t start = clock();//ms
	for (int i = 0; i < SIZE; ++i)
	{
		l.push_back(rand()%SIZE);
	}
	cout << "插入1000000个元素耗时为: " << (clock() - start) << endl;
	cout << "list.size()" << l.size() << endl;
	cout << "list.front()" << l.front() << endl;
	cout << "list.back()" << l.back() << endl;
	cout << "list.max_size()" << l.max_size() << endl;//最大容量
	
	/*
	//算法都是全局的
	auto it = ::find(l.begin(),l.end(),100);
	if (it != l.end())
	{
		cout << "找到了" << *it << endl;
	}
	else
	{
		cout << "没有找到" << endl;
	}
	*/
	
	
	return 0;
}
执行结果:
插入1000000个元素耗时为: 130
list.size()100000
list.front()41
list.back()1629
list.max_size()357913941
请按任意键继续. . .
  • 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

二、list的特点:

  1. 查找效率低,因为内存是不连续的,需要通过指针挨个遍历,最坏情况O(n);
  2. 前插效率高,O(1);
  3. 由于内存不是连续的,所以删除一个节点不会造成迭代器失效问题;
  4. 增加删除效率高,不需要挪动前后的元素;
  5. 链表是没有operator[]的,因为链表内存不是连续的;
  6. 由于list一般都是用双向链表实现,所以至少有三个指针:前驱、后继、数据域。这样一来,在内存的耗费上开销就相对较大。

三、list部分源码展示:

template <class T, class Allocator = allocator<T> >
class list {
public:
    // 定义types:
    typedef value_type&                                         reference;
    typedef const value_type&                                   const_reference;
    typedef /*implementation-defined*/                          iterator;
    typedef /*implementation-defined*/                          const_iterator; 
    typedef /*implementation-defined*/                          size_type;
    typedef /*implementation-defined*/                          difference_type;
    typedef T                                                   value_type;
    typedef Allocator                                           allocator_type;
    typedef typename allocator_traits<Allocator>::pointer       pointer;
    typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
    typedef std::reverse_iterator<iterator>                     reverse_iterator;
    typedef std::reverse_iterator<const_iterator>               const_reverse_iterator;
 
    // construct/copy/destroy:构造、析构以及内存释放
    explicit list(const Allocator& = Allocator());
    explicit list(size_type n);
    list(size_type n, const T& value,const Allocator& = Allocator());
    template <class InputIterator>
        list(InputIterator first, InputIterator last,const Allocator& = Allocator());
    list(const list<T,Allocator>& x);
    list(list&&);
    list(const list&, const Allocator&);
    list(list&&, const Allocator&);
    list(initializer_list<T>, const Allocator& = Allocator());
    ~list();
    list<T,Allocator>& operator=(const list<T,Allocator>& x);
    list<T,Allocator>& operator=(list<T,Allocator>&& x);
    list& operator=(initializer_list<T>);
    template <class InputIterator>
        void assign(InputIterator first, InputIterator last);
    void assign(size_type n, const T& t);
    void assign(initializer_list<T>);
    allocator_type get_allocator() const noexcept;
 
    // iterators:所有迭代器	
    iterator                begin() noexcept;
    const_iterator          begin() const noexcept;
    iterator                end() noexcept;
    const_iterator          end() const noexcept;
 
    reverse_iterator        rbegin() noexcept;
    const_reverse_iterator  rbegin() const noexcept;
    reverse_iterator        rend() noexcept;
    const_reverse_iterator  rend() const noexcept;
 
    const_iterator          cbegin() const noexcept;
    const_iterator          cend() const noexcept;
    const_reverse_iterator  crbegin() const noexcept;
    const_reverse_iterator  crend() const noexcept;
 
    // capacity:同理相关方法
    size_type size() const noexcept;
    size_type max_size() const noexcept;
    void      resize(size_type sz);
    void      resize(size_type sz, const T& c);
    bool      empty() const noexcept;
 
    // 元素访问
    reference       front();
    const_reference front() const;
    reference       back();
    const_reference back() const;
 
    // modifiers:对list的访问操作等函数如头插、尾插、删除erase
    template <class... Args> void emplace_front(Args&&... args);
    void pop_front();
    template <class... Args> void emplace_back(Args&&... args);
    void push_front(const T& x);
    void push_front(T&& x);
    void push_back(const T& x);
    void push_back(T&& x);
    void pop_back();
 
    template <class... Args> iterator emplace(const_iterator position, Args&&... args);
    iterator insert(const_iterator position, const T& x);
    iterator insert(const_iterator position, T&& x);
    iterator insert(const_iterator position, size_type n, const T& x);
    template <class InputIterator>
        iterator insert (const_iterator position, InputIterator first, 
                         InputIterator last);
    iterator insert(const_iterator position, initializer_list<T>);
 
 
    iterator erase(const_iterator position);
    iterator erase(const_iterator first, const_iterator last);
    void     swap(list<T,Allocator>&);
    void     clear() noexcept;
 
    // list operations:对list的操作,如切片、合并、逆置、排序等操作
    void splice(const_iterator position, list<T,Allocator>& x);
    void splice(const_iterator position, list<T,Allocator>&& x);
    void splice(const_iterator position, list<T,Allocator>& x,
                    const_iterator i);
    void splice(const_iterator position, list<T,Allocator>&& x,
                    const_iterator i);
    void splice(const_iterator position, list<T,Allocator>& x,
                    const_iterator first, const_iterator last);
    void splice(const_iterator position, list<T,Allocator>&& x,
                    const_iterator first, const_iterator last);
 
    void remove(const T& value);
    template <class Predicate> void remove_if(Predicate pred);
 
    void unique();
    template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
 
    void merge(list<T,Allocator>& x);
    void merge(list<T,Allocator>&& x);
    template <class Compare> void merge(list<T,Allocator>& x, Compare comp);
    template <class Compare> void merge(list<T,Allocator>&& x, Compare comp);
 
    void sort();
    template <class Compare> void sort(Compare comp);
 
    void reverse() noexcept;
};
  • 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
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  1. 实际上我们可以看到,list自己实现了sort()方法,而不是标准库的全局sort算法,既然自己实现了sort,那么一般来说使用自己实现的sort效率当然高了;
  2. 提供了链表的合并、切片等成员方法;
  3. 正向迭代器和反向迭代器的关系
    在这里插入图片描述
    四、老版本list中节点定义
//双向环形链表的节点
struct _list_node
{
	typedef void *void_pointer;
	void_pointer prev;
	void_pointer next;
	T data;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

实际上,我们没必要纠结源码每一步是如何实现的,只需要知道容器底层使用的数据结构和对应的特点,以及对效率的影响,我们用到时如何选择效率能最高,这才是我们的目的。

五、注意事项:

我在STL第一讲中提到过,所有的容器和python中表现一样,都遵循“前闭后开” 原则
什么意思?就是最后一个元素得值取不到,为什么取不到:
因为end()指向得是最后一个元素得下一个元素,很明显这个元素不属于容器  [ begin(),end()).
  • 1
  • 2
  • 3

六、list参考链接:
https://en.cppreference.com/w/cpp/container/list
https://en.cppreference.com/w/cpp/header/list

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/761476
推荐阅读
相关标签
  

闽ICP备14008679号