c++ - std::vector::end() 迭代器如何在内存中工作？

Question

今天，我试图从一个大小为 M 的 vector 中提取 N 个元素的子集，其中 N < M。我意识到我不需要创建一个新拷贝，只需要修改原始拷贝，而且，可以只取前 N 个元素。

在做了一些简短的搜索之后，有很多答案，最吸引人的是 resize() ，它似乎将 vector 截断到一定长度，并巧妙地处理了删除其他元素的内存问题。

但是，在遇到 vector.resize() 之前，我试图将 vector.end() 指向第 N+1 个位置。我知道这行不通，但无论如何我都想尝试一下。这将使超过第 N 个位置的其他元素“搁浅”，我相信(如果我错了请纠正我)这将是内存泄漏的一个例子。

在 http://www.cplusplus.com/reference/vector/vector/resize/ 上查看迭代器的有效性,我们看到如果它缩小，vector.end() 保持不变。如果它扩展，vector.end() 将移动(尽管与我们的情况无关)。

这让我产生疑问，vector.end() 的底层机制是什么？它在内存中的什么位置？可以发现递增一个指向vector中最后一个元素的迭代器，eg auto iter = &vector.back(), iter++，但是在内存中，是这样吗？

我相信在任何时候，vector.begin() 之后的内容都应该是第一个元素，但在调整大小时，vector.end() 似乎可以位于 vector 中最后一个元素之外的其他位置。

出于某种原因，我似乎找不到答案，但听起来非常基础的计算机科学类(class)会包含这些信息。我想它是特定于 STL 的，因为可能有许多不同的 vector/列表实现......

很抱歉关于一个简单问题的长篇博文!

Answer 1

您询问了“vector.end() 的底层机制”。好吧，这里是(一小段)一个易于理解的过度简化的 vector :

template <class T>
class Simplified_vector
{
public:
    using interator = T*;
    using const_interator = const T*;

private:
   T* buffer_;
   std::size_t size_;
   std::size_t capacity_;

public:

   auto push_back(const T& val) -> void
   {
       if (size_ + 1 > capacity_)
       {
           // buffer increase logic
           //
           // this usually means allocation a new larger buffer
           // followed by coping/moving elements from the old to the new buffer
           // deleting the old buffer
           // and make `buffer_` point to the new buffer
           // (along with modifying `capacity_` to reflect the new buffer size)
           //
           // strong exception guarantee makes things a bit more complicated,
           // but this is the gist of it
       }

       buffer_[size_] = val;
       ++size_;
   }

   auto begin() const -> const_iterator
   {
       return buffer_;
   }

   auto begin() -> iterator
   {
       return buffer_;
   }

   auto end() const -> const_iterator
   {
       return buffer_ + size_;
   }

   auto end() -> iterator
   {
       return  buffer_ + size_;
   }
};

另请参阅此问题 Can std::vector<T>::iterator simply be T*?为什么T*是一个完全有效的 iterator对于 std::vector<T>

---

现在考虑到这个实现，让我们回答一些您的误解问题:

I was trying to point the vector.end() to the N+1'th position.

这是不可能的。结束迭代器不是直接存储在类中的东西。如您所见，它是对缓冲区请求加上容器大小(元素数量)的计算。而且你不能直接操纵它。类(class)的内部运作确保end()将返回指向缓冲区中最后一个元素之后的 1 的迭代器。你不能改变这个。您可以做的是从容器和 end() 中插入/删除元素。将反射(reflect)这些新变化，但您不能直接操纵它。

and I believe (correct me if i'm wrong) this would be an example of a memory leak.

你错了。即使你以某种方式制作 end指向应该指向的其他东西，那不会是内存泄漏。如果您丢失了对动态分配的内部缓冲区的任何引用，就会发生内存泄漏。