c++ 中的动态数组，如何以最有效的方式重新分配新数组
我正在做一个 STL 容器（std::vector），我意识到当容量达到最大时，它的复杂度不再是 O(1)，而是 O(n)，因为我们需要创建一个新数组并删除旧数组。我想知道是否有更好的方法来创建临时文件，而不必将所有内容复制到临时文件，删除真实文件并将真实文件指向临时文件。 我可以举一个代码示例：
realloc_arr(int newCapacity)
{
if (newCapacity <= _oldCapacity)
return;
T *temp = _alloc.allocate(newCapacity);
for (int i = 0; i < _oldCapacity; i++)
temp->construct(temp + i, _arr[i]);
_alloc.dealocate(_arr, _oldCapacity);
_arr = temp;
_oldCapacity = newCapacity;
};
我正在尝试理解分配器语义和语法，我想知道我是否使用得很好。
I'm doing a STL container (std::vector) and I realized that when capacity is maxed out, it no more O(1) complexity, but O(n) since we need create a new array and delete the old one. I would like to know if there's a better way to create the temp without having to copy everything to the temp one, deleting the real and pointing the real to the temp one.
I can give a example of the code:
realloc_arr(int newCapacity)
{
if (newCapacity <= _oldCapacity)
return;
T *temp = _alloc.allocate(newCapacity);
for (int i = 0; i < _oldCapacity; i++)
temp->construct(temp + i, _arr[i]);
_alloc.dealocate(_arr, _oldCapacity);
_arr = temp;
_oldCapacity = newCapacity;
};
I am trying to understand the allocator semantic and syntax and I would like to know if I am using it well.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果满足某些要求，那么有一种更好的方法。
如果元素的移动构造函数没有抛出异常，那么您可以移动它们，而不是复制元素。
对于动态数组，不存在渐进更快的重新分配方法。 O(n) 是最优的。
If certain requirements are met, then there is a better way.
If the move constructor of the element doesn't throw, then instead of copying the elements, you can move them.
No asymptotically faster reallocation method exists for dynamic arrays. O(n) is optimal.