首页 文章

std :: vector :: end()迭代器如何在内存中工作?

提问于
浏览
0

今天,我试图从大小为M的向量中提取N个元素的子集,其中N <M . 我意识到我不需要创建新的副本,只需要修改原始文件,而且,可以简单地前N个元素 .

在进行了一些简短的搜索之后,有很多答案,最有吸引力的是resize(),它似乎将向量截断到长度,并且整齐地处理了擦除其他元素的内存问题 .

然而,在我遇到vector.resize()之前,我试图将vector.end()指向第N个第一个位置 . 我知道这不起作用,但我想不管怎样尝试 . 这将使其他元素超过第N个位置“搁浅”,我相信(如果我错了,请纠正我)这将是内存泄漏的一个例子 .

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

这引出了我的疑问, what is the underlying mechanic of vector.end()? 它在记忆中的位置在哪里?可以看到递增指向向量中最后一个元素的迭代器,例如auto iter =&vector.back(),iter,但在内存中,这是怎么回事?

我可以相信,在任何时候,vector.begin()之后应该是第一个元素,但是在resize上,看起来vector.end()可以位于除了向量中的最后一个元素之外的其他位置 .

出于某种原因,我似乎无法找到答案,但这听起来像一个非常基础的计算机科学课程将包含这些信息 . 我想它是特定的,因为可能有许多不同的矢量/列表的实现......

对于关于一个简单问题的长篇帖子感到抱歉!

3 回答

  • 0

    你问过“vector.end()的基本机制” . 那么这是一个易于理解的过度简化的矢量(一个片段):

    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 for std::vector<T>


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

    我试图将vector.end()指向第N 1位置 .

    这是不可能的 . 结束迭代器不是直接存储在类中的东西 . 正如您所看到的,它是缓冲区的乞讨加上容器的大小(元素数量)的计算 . 而且你无法直接操纵它 . 类的内部工作方式确保 end() 将返回一个迭代器,该迭代器指向缓冲区中最后一个元素的1 . 你无法改变这一点 . 您可以做的是从容器中插入/删除元素, end() 将反映这些新的更改,但您无法直接操作它 .

    我相信(如果我错了,请纠正我)这将是内存泄漏的一个例子 .

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

  • 2

    任何连续容器(如矢量或数组)的"end"始终是容器最后一个元素之外的一个元素 .

    因此对于X元素的数组(或向量),“end”是索引X(请记住,因为索引从零开始,所以最后一个索引是X - 1) .

    这在例如很好地说明 . this vector::end reference .

    如果缩小向量,最后一个索引当然也会改变,这意味着"end"也会改变 . 如果end-iterator没有改变,那么它意味着你在收缩向量之前保存它,这将改变大小并使所有迭代器无效,超出向量中的最后一个元素,包括结束迭代器 .

    如果通过添加新元素或删除元素来更改向量的大小,则必须重新获取结束迭代器 . 您拥有的现有迭代器对象不会自动更新 .

  • 1

    通常,结尾不存储在vector的实现中 . 矢量存储:

    • 指向第一个元素的指针 . 如果你调用begin(),这就是你得到的 .

    • 已管理的内存块的大小 . 如果调用capacity(),则会返回可以容纳此分配内存的元素数 .

    • 正在使用的元素数 . 这些元素已经构建并位于存储块的第一部分中 . 内存的其余部分未使用,但可用于新内存元素 . 如果整个容量被填满,为了添加更多元素,向量将分配更大的内存块并将所有元素复制到其中,并释放原始块 .

    当你调用end()时,这会返回begin()size() . 所以是的,end()是一个指向超出最后一个元素的指针 .

    所以end()不是你可以移动的东西 . 您只能通过添加或删除元素来更改它 .

    如果你想提取一些元素'N',你可以通过读取从begin()到begin()'N'的元素来实现 .

    for( var it = vec.begin(); it != begin() + n; ++it )
    {
        // do something with the element (*it) here.
    }
    

    许多stl算法将一对迭代器用于您想要使用的一系列元素的开头和结尾 . 在您的情况下,您可以使用vec.begin()和vec.begin()n作为您感兴趣的范围的开头和结尾 .

    如果你想在n之后丢弃元素,你可以做vec.resize(n) . 然后向量将破坏您不需要的元素 . 它可能不会改变矢量管理的内存块的大小,如果再次添加更多元素,矢量可能会保留内存 . 这是您正在使用的矢量类的实现细节 .

相关问题