La différence entre le vecteur et la liste

● Le vecteur a une efficacité d'accès aléatoire élevée, mais il doit être déplacé lors de l'insertion et de la suppression (à l'exclusion la queue) Les données sont difficiles à manipuler.

● L'accès à la liste nécessite de parcourir l'intégralité de la liste cha?née et son efficacité d'accès aléatoire est faible. Cependant, il est plus pratique d'insérer et de supprimer des données, il suffit de changer le pointage du pointeur.

● La liste est unidirectionnelle, le vecteur est bidirectionnel.

● L'itérateur du vecteur devient invalide après utilisation, tandis que l'itérateur de la liste peut continuer à être utilisé après utilisation.

Utilisation du vecteur

Structure de stockage continue?: le vecteur est un tableau d'objets qui peut atteindre une croissance dynamique, prenant en charge un accès efficace au tableau ainsi que la suppression et l'insertion à la fin de L'opération du tableau, la suppression et l'insertion au milieu et en tête sont relativement difficiles et nécessitent le déplacement d'une grande quantité de données. La plus grande différence entre elle et un tableau est que le vecteur n'oblige pas les programmeurs à prendre en compte eux-mêmes les problèmes de capacité. La bibliothèque elle-même a réalisé une croissance dynamique de la capacité, tandis que les tableaux obligent les programmeurs à écrire manuellement des fonctions d'extension pour l'expansion.

Implémentation de simulation de 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擴(kuò)容時(shí)需要初始化空間，并且可以縮小容量
  {
    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; //指向第一個(gè)元素所在節(jié)點(diǎn)
  Iterator _finish; //指向最后一個(gè)元素所在節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
  Iterator _endOfStorage; //可用內(nèi)存空間的末尾節(jié)點(diǎn)
};

Utilisation de liste

Structure de stockage non continue?: la liste est une structure de liste doublement liée qui prend en charge le parcours bidirectionnel de la liste cha?née. Chaque n?ud comprend trois informations?: l'élément lui-même, le n?ud pointant vers l'élément précédent (prev) et le n?ud pointant vers l'élément suivant (next). Par conséquent, la liste peut accéder, insérer et supprimer efficacement des éléments de données à n’importe quel endroit. Puisqu’il implique la maintenance de pointeurs supplémentaires, le surco?t est relativement élevé.

Implémentation de simulation de 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;
};

Apprentissage recommandé?: Tutoriel vidéo Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!