Details of the differences between vector and list in Java

Know vector,list,deque. So let's start with STL.

STL is short for Standard Template Library, and its Chinese name is the standard template library. Essentially, STL is a collection of 1 containers and algorithms. STL can be divided into six parts: container (containers), iterator (iterators), spatial configurator (allocator), adapter (adapters), algorithm (algorithms) and copy function (functors). Pointers are encapsulated as iterators, where vector and list are so-called containers.

Often when we implement linked lists, stacks, queues, or arrays, we write duplicate or similar code, and we consider various possible problems. The introduction of STL greatly improves the reusability of the code. When we implement this code, we can apply it flexibly by introducing header files.

The use of vector

Continuous storage structure: vector is an object array that can realize dynamic growth. It supports efficient access to the array and delete and insert operations at the end of the array. It is relatively difficult to delete and insert in the middle and the head, requiring a large amount of data to be moved. The biggest difference between vector and arrays is that vector does not need the programmer to think about capacity. The library itself has realized the dynamic growth of capacity, while the array needs the programmer to manually write the expansion function to expand the capacity.

Simulation implementation of 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())// with Resize When expanding, you need to initialize space, and you can reduce capacity 
  {
    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)// Instead of initializing space, add capacity directly 
  {
    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; // Pointing to the first 1 The node of the element 
  Iterator _finish; // Pointing to the last 1 Below the node where the element is located 1 A node 
  Iterator _endOfStorage; // The end node of the available memory space 
};

The use of list

Discontinuous storage structure: list is a double linked list structure that supports two-way traversal of the list. Each node contains three pieces of information: the element itself, the node pointing to the previous element (prev), and the node pointing to the next element (next). Therefore, list can efficiently access, insert and delete data elements at any location. This is expensive because it involves maintenance of additional Pointers.

Differences between vector and list

*vector has high efficiency of random access, but it is difficult to operate because it needs to move data when inserting and deleting (excluding the tail).

*List access to traverse the entire linked list, its random access efficiency is low. But to the data insert and delete operation are more convenient, change the pointer to point to can.

*list is one-way and vector is two-way.

* The iterators in vector fail after use, while the iterators in list continue to be used after use.

Simulation implementation of 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;
};

conclusion