要了解vector,list,deque。我們先來了解一下STL。
STL是Standard Template Library的簡稱，中文名是標準模板庫。從根本上說，STL是一些容器和算法的集合。STL可分為容器(containers)、迭代器(iterators)、空間配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函數(functors)六個部分。指針被封裝成迭代器，這里vector，list就是所謂的容器。
我們常常在實現鏈表，棧，隊列或者數組時，都會寫著一些重復或者相似的代碼，還要考慮各種可能出現的問題。而STL的引入，大大提高了代碼的復用性。我們在實現這些代碼時，只要引入頭文件就可以靈活的應用了。
vector的使用
連續存儲結構：vector是可以實現動態增長的對象數組，支持對數組高效率的訪問和在數組尾端的刪除和插入操作，在中間和頭部刪除和插入相對不易，需要挪動大量的數據。它與數組最大的區別就是vector不需程序員自己去考慮容量問題，庫里面本身已經實現了容量的動態增長，而數組需要程序員手動寫入擴容函數進形擴容。
Vector的模擬實現
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的模擬實現
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的區別和使用實例詳解，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對億速云網站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
