java的vector与list区别

Java  /  管理员 发布于 8年前   400

vector的使用

连续存储结构：vector是可以实现动态增长的对象数组，支持对数组高效率的访问和在数组尾端的删除和插入操作，在中间和头部删除和插入相对不易，需要挪动大量的数据。 （推荐学习：java课程）

它与数组最大的区别就是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可以高效率的对数据元素任意位置进行访问和插入删除等操作。由于涉及对额外指针的维护，所以开销比较大。

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;};

vector 和list的区别

*vector的随机访问效率高，但在插入和删除时（不包括尾部）需要挪动数据，不易操作。

*List的访问要遍历整个链表，它的随机访问效率低。但对数据的插入和删除操作等都比较方便，改变指针的指向即可。

*list是单向的，vector是双向的。

*vector中的迭代器在使用后就失效了，而list的迭代器在使用之后还可以继续使用。

以上就是java的vector与list区别的详细内容，更多请关注其它相关文章！