std :: vector向下调整大小

Question

C++标准似乎让有关能力的副作用通过或者没有声明 resize(n),与n < size(),或clear().

它确实作出了关于摊销成本push_back和pop_back- O(1)的声明

我可以设想一种实现通常的容量变化和CLRS算法(例如,放大时加倍,减少时减半size to < capacity()/4).(Cormen Lieserson Rivest Stein)

有没有人参考任何实施限制？

Answer 1

resize()较小尺寸的呼叫对a的容量没有影响vector.它不会释放内存.

用于从释放内存的标准成语vector是swap()它具有空临时vector:std::vector<T>().swap(vec);.如果要向下调整大小,则需要从原始向量复制到新的本地临时向量,然后将生成的向量与原始向量交换.

更新: C++ 11 shrink_to_fit()为此添加了一个成员函数,它是一个非约束请求,以减少capacity()为size().

Answer 2

实际上,该标准确实指明了应该发生的事情:

这是从vector,但主题是所有容器相同的(list,deque,等...)

23.2.4.2向量容量[lib.vector.capacity]

void resize(size_type sz, T c = T());

6)效果:

if (sz > size())
    insert(end(), sz-size(), c);
else if (sz < size())
    erase(begin()+sz, end());
else
    ; //do nothing

也就是说:如果指定的大小resize小于元素的数量,那么这些元素将从容器中删除.关于capacity(),这取决于erase()它做了什么.

我无法在标准中找到它,但我很确定clear()定义为:

void clear()
{
    erase(begin(), end());
}

因此,影响clear()了上capacity()还绑在效果erase()上有.根据标准:

23.2.4.3向量修饰符[lib.vector.modifiers]

iterator erase(iterator position);
iterator erase(iterator first, iterator last);

4)复杂性:T的析构函数被称为等于被删除元素数量的次数....

这意味着元素将被破坏,但内存将保持不变.erase()因此对容量没有影响resize(),clear()也没有影响.

Answer 3

容量永远不会减少.我不确定标准是否明确说明了这一点,但暗示:迭代器和对vector元素的引用不能被resize(n)if 无效n < capacity().