java中的接口是类吗
284
2023-04-10
Java 中的vector和list的区别和使用实例详解
要了解vector,list,deque。我们先来了解一下STL。
STL是Standard Template Library的简称,中文名是标准模板库。从根本上说,STL是一些容器和算法的集合。STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。指针被封装成迭代器,这里vector,list就是所谓的容器。
我们常常在实现链表,栈,队列或者数组时,都会写着一些重复或者相似的代码,还要考虑各种可能出现的问题。而STL的引入,大大提高了代码的复用性。我们在实现这些代码时,只要引入头文件就可以灵活的应用了。
vector的使用
连续存储结构:vector是可以实现动态增长的对象数组,支持对数组高效率的访问和在数组尾端http://的删除和插入操作,在中间和头部删除和插入相对不易,需要挪动大量的数据。它与数组最大的区别就是vector不需程序员自己去考虑容量问题,库里面本身已经实现了容量的动态增长,而数组需要程序员手动写入扩容函数进形扩容。
Vector的模拟实现
template
class Vector
{
public:
typedef T* Iterator;
typedef const T* Iterator;
Vector()
:_start(NULL)
,_finish(NULL)
,_endOfStorage(NULL)
{}
void template
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 List
{
typedef __ListNode
public:
typedef __ListIterator
typedef __ListIterator
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的区别和使用实例详解,希望对大家有所帮助,如果大家有任何疑问请给我留言,会及时回复大家的。在此也非常感谢大家对我们网站的支持!
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~