欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java 中的vector和list的区别和使用实例详解

程序员文章站 2024-02-24 18:46:10
要了解vector,list,deque。我们先来了解一下stl。 stl是standard template library的简称,中文名是标准模板库。从根本上说,s...

要了解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的区别和使用实例详解,希望对大家有所帮助