要了解vector,list,deque。我们先来了解一下STL。
STL是Standard Template Library的简称，中文名是标准模板库。从根本上说，STL是一些容器和算法的集合。STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。指针被封装成迭代器，这里vector，list就是所谓的容器。
我们常常在实现链表，栈，队列或者数组时，都会写着一些重复或者相似的代码，还要考虑各种可能出现的问题。而STL的引入，大大提高了代码的复用性。我们在实现这些代码时，只要引入头文件就可以灵活的应用了。
vector的使用
连续存储结构：vector是可以实现动态增长的对象数组，支持对数组高效率的访问和在数组尾端的删除和插入操作，在中间和头部删除和插入相对不易，需要挪动大量的数据。它与数组最大的区别就是vector不需程序员自己去考虑容量问题，库里面本身已经实现了容量的动态增长，而数组需要程序员手动写入扩容函数进形扩容。
Vector的模拟实现
|
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
|
template <class T>class Vector{public: typedef T* Iterator; typedef const T* Iterator; Vector() :_start(NULL) ,_finish(NULL) ,_endOfStorage(NULL) {} void template<class T> PushBack(const T& x) { Iterator end = End(); Insert(end, x); } void Insert(Iterator& pos, const T& x) { size_t n = pos - _start; if (_finish == _endOfStorage) { size_t len = Capacity() == 0 ? 3 : Capacity()*2; Expand(len); } pos = _start+n; for (Iterator end = End(); end != pos; --end) { *end = *(end-1); } *pos = x; ++_finish; } Iterator End() { return _finish; } Iterator Begin() { return _start; } void Resize(size_t n, const T& val = T())//用Resize扩容时需要初始化空间，并且可以缩小容量 { if (n < Size()) { _finish = _start+n; } else { Reserve(n); size_t len = n-Size(); for (size_t i = 0; i < len; ++i) { PushBack(val); } } } void Reserve(size_t n)//不用初始化空间，直接增容 { Expand(n); } inline size_t Size() { return _finish-_start; } inline size_t Capacity() { return _endOfStorage-_start; } void Expand(size_t n) { const size_t size = Size(); const size_t capacity = Capacity(); if (n > capacity) { T* tmp = new T[n]; for (size_t i = 0; i < size; ++i) { tmp[i] = _start[i]; } delete[] _start; _start = tmp; _finish = _start+size; _endOfStorage = _start+n; } } T& operator[](size_t pos) { assert(pos < Size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < Size()); return _start[pos]; }protected: Iterator _start; //指向第一个元素所在节点 Iterator _finish; //指向最后一个元素所在节点的下一个节点 Iterator _endOfStorage; //可用内存空间的末尾节点}; |
list的使用
非连续存储结构：list是一个双链表结构，支持对链表的双向遍历。每个节点包括三个信息：元素本身，指向前一个元素的节点（prev）和指向下一个元素的节点（next）。因此list可以高效率的对数据元素任意位置进行访问和插入删除等操作。由于涉及对额外指针的维护，所以开销比较大。
vector 和list的区别
*vector的随机访问效率高，但在插入和删除时（不包括尾部）需要挪动数据，不易操作。
*List的访问要遍历整个链表，它的随机访问效率低。但对数据的插入和删除操作等都比较方便，改变指针的指向即可。
*list是单向的，vector是双向的。
*vector中的迭代器在使用后就失效了，而list的迭代器在使用之后还可以继续使用。
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
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
|
template<class T>class List{ typedef __ListNode<T> Node;public: typedef __ListIterator<T, T&, T*> Iterator; typedef __ListIterator<T, const T&, const T*> ConstIterator; Iterator Begin() { return _head->_next; } Iterator End() { return _head; } ConstIterator Begin() const { return _head->_next; } ConstIterator End() const { return _head; } List() { _head = new Node(T()); _head->_next = _head; _head->_prev = _head; } // l2(l1) List(const List& l) { _head = new Node(T()); _head->_next = _head; _head->_prev = _head; ConstIterator it = l.Begin(); while (it != l.End()) { PushBack(*it); ++it; } } ~List() { Clear(); delete _head; _head = NULL; } void Clear() { Iterator it = Begin(); while (it != End()) { Node* del = it._node; ++it; delete del; } _head->_next = _head; _head->_prev = _head; } void PushBack(const T& x) { Insert(End(), x); } void PushFront(const T& x) { Insert(Begin(), x); } void PopBack() { Erase(--End()); } void PopFront() { Erase(Begin()); } void Insert(Iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* tmp = new Node(x); prev->_next = tmp; tmp->_prev = prev; tmp->_next = cur; cur->_prev = prev; } Iterator Erase(Iterator& pos) { assert(pos != End()); Node* prev = (pos._node)->_prev; Node* next = (pos._node)->_next; prev->_next = next; next->_prev = prev; delete pos._node; pos._node = prev; return Iterator(next); }protected: Node* _head;}; |
总结
以上所述是小编给大家介绍的Java 中的vector和list的区别和使用实例详解，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对服务器之家网站的支持！
原文链接：http://blog.csdn.net/wyn126/article/details/77823661
