如何在STL向量中实现push_back？ [英] how is push_back implemented in STL vector?

问题描述

我在面试中被问过这个问题。

I was asked this question in an interview.

我回答的问题是这样的

1）指向当前位置的索引;

1) an index pointing to the current position;

2）必要时调整大小。

2) resize if neccessary.

任何人都可以进一步阐述吗？

Can anybody elaborate more?

推荐答案

一个STL 向量有一个 size （当前存储的元素数）和 capacity （当前分配的存储空间）。

An STL vector has a size (current number of stored elements) and a capacity (currently allocated storage space).

• 如果 size <容量，a push_back 只是将新元素放在结尾，并将 size c> 之前的，如果 size == capacity ，分配更大的数组（两倍大小是公共的，但这是依赖于实现的afaik），所有当前数据被复制（包括新的元素），并且旧的分配的空间被释放。如果分配失败，这可能会抛出异常。



• If size < capacity, a push_back simply puts the new element at the end and increments the size by 1.
• If size == capacity before the push_back, a new, larger array is allocated (twice the size is common, but this is implementation-dependent afaik), all of the current data is copied over (including the new element), and the old allocated space is freed. This may throw an exception if the allocation fails.

操作的复杂性是摊销 O（1），这意味着在 push_back ，这将导致调整大小，它不会是一个常量时间操作（但一般在很多操作，它是）。

The complexity of the operation is amortized O(1), which means during a push_back that causes a resize, it won't be a constant-time operation (but in general over many operations, it is).

这篇关于如何在STL向量中实现push_back？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！