STL vector的实现,删除其中的元素,迭代器如何变化?为什么是两倍扩容?释放空间?
参考答案:
STL(Standard Template Library)是C++标准库的一部分,它为程序员提供了各种常见的数据结构和算法。std::vector
是STL中的一种动态数组实现,它允许在运行时添加和删除元素。
删除元素和迭代器变化
当从std::vector
中删除元素时,迭代器指向的位置可能会受到影响。迭代器是一个指向容器内元素的指针,它提供了一种访问和操作容器元素的方式。在删除元素后,指向被删除元素的迭代器将变得无效,不应再被使用。
对于指向被删除元素之前的元素的迭代器,它们不会受到影响,仍然有效。然而,指向被删除元素之后的元素的迭代器将变得无效,因为它们指向的位置已经不存在了。
为什么是两倍扩容
std::vector
使用动态内存分配来存储元素,当需要添加更多元素时,它会根据需要重新分配内存。为了避免频繁的内存分配和复制操作,std::vector
通常会分配比当前需要的更多的内存。当需要添加更多元素时,它首先检查是否有足够的可用空间。如果没有,它会分配一个新的内存块,其大小通常是当前容量的两倍,然后将现有元素复制到新的内存块中,最后释放旧的内存块。这种策略称为“两倍扩容”。
释放空间
当从std::vector
中删除元素时,它不会立即释放内存。相反,它会保留这些内存以供将来使用。这是为了提高效率,避免频繁的内存分配和释放操作。然而,如果你知道vector
不再需要这些额外的内存,你可以使用std::vector::shrink_to_fit
成员函数来请求释放多余的内存。这个函数会尝试将vector
的容量减少到与当前大小相匹配,从而释放多余的内存。但是请注意,这并不总是可能的,因为释放内存取决于具体的内存分配器实现。