标准库容器如何知道过去结束迭代器之前的内容？-解网

问：

我正在尝试实现我自己的和，并且我一直在使用该方法时遇到麻烦，因为这些容器在内存中不连续。listmapend()

经过一番研究，我最终实现了 as 方法，该方法返回一个拥有 .（end（）以何种方式指向非连续容器中的“one past the end”？这对于我的大部分实现来说已经足够了，因为它验证了当列表为空时（空列表没有节点，因此指向）。end()nullptrlist::begin() == list::end()headnullptr

但是，我已经看到可以调用过去的结束迭代器来指向容器的实际最后一个元素。operator--()

int main() {
  {
    std::map<int, char> m = {{1, 'a'}, {2, 'b'}, {3, 'c'}};
    auto it = m.end();
    --it;
    std::cout << it->first << "\n";  // output: 3
    std::cout << it->second << "\n"; // output: c
  }
  {
    std::list<int> l{ 1, 2, 8};
    auto it = l.end();
    --it;
    std::cout << *it << "\n"; // output: 8
  }
}

这是如何实现的？在 gcc 中实现 of 会更改当前节点以指向前一个节点：operator--()_List_iterator

      _Self&
      operator--() _GLIBCXX_NOEXCEPT
      {
    _M_node = _M_node->_M_prev;
    return *this;
      }

但是，如果节点不在列表中，这怎么可能呢？这个节点是如何存在的？这是否意味着分配了一个额外的节点？你真的可以调用过去的迭代器吗？operator--()

这些是 gcc 的和方法，以防万一：begin()end()std::list

     /**
       *  Returns a read-only (constant) iterator that points to the
       *  first element in the %list.  Iteration is done in ordinary
       *  element order.
       */
      _GLIBCXX_NODISCARD
      const_iterator
      begin() const _GLIBCXX_NOEXCEPT
      { return const_iterator(this->_M_impl._M_node._M_next); }

      /**
       *  Returns a read/write iterator that points one past the last
       *  element in the %list.  Iteration is done in ordinary element
       *  order.
       */
      _GLIBCXX_NODISCARD
      iterator
      end() _GLIBCXX_NOEXCEPT
      { return iterator(&this->_M_impl._M_node); }

C++ 迭代器容器 std c++-standard-library

template<typename T>
struct ListIter {
   ListNodeBase* current;

   // Here however we upcast to the node type to access the data. 
   T& operator*() const
      { return static_cast< ListNode<T>* >(current)->data; }
   T* operator->() const
      { return &static_cast< ListNode<T>* >(current)->data; }

   // just your bog standard list traversal.. 
   // again, this only operates on the 
   ListIter<T>& operator++() {
      current = current->next;
      return *this;
   }

   ListIter<T>& operator--() {
      current = current->prev;
      return *this;
   }
};

不过，诀窍是有一个 ListNodeBase（即列表容器）的节点，其余的节点是 ListNode。

template<typename T> 
struct list : private ListNodeBase {

   typedef ListIter<T> iterator;


   list() 
   {
     // when empty, store pointers to itself 
     this->next = this;
     this->prev = this;
   }

   iterator begin() 
     { return (iterator){ this->next }; }

   iterator end() 
     { return (iterator){ this }; }
};

换句话说，列表容器是哨兵节点（它只是不存储任何数据，因为它使用基本节点类型，而节点是实际节点）。

标准库容器如何知道过去结束迭代器之前的内容？

How do standard library containers know what's before the past-the-end iterator?

评论

评论