在C++中，std::string::push_back()的摊销复杂度是O(1)吗？

Question

在C++中，std::string::push_back()的摊销复杂度是O(1)吗？

c++stringcomplexity-theorypush-back

6

我知道标准规定它是用于向量的，但对于字符串呢？

- Ari

当然可以，但是我现在没有访问标准的权限，所以才会问这个问题。 - Ari

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergey Kalinichenko · Accepted Answer

是的，这是摊销常数时间。请参阅716页此文档上的表格101：

101表格列出了一些序列容器可提供但其他容器不提供的操作。实现应为所有显示在“容器”列中的容器类型提供这些操作，并应以摊销常数时间实现它们。

Operation      | Description          | Container
---------------+----------------------+----------------------------------
a.push_back(t) | Appends a copy of t. | basic_string, deque, list, vector