烽火三国路,突袭命运之柱,黄鑫近况
要了解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的区别和使用实例详解，希望对大家有所帮助
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
apollo与springboot集成实现动态刷新配置的教程详解
网友评论