'Dinamic arrays in c++, how to realocate a new array in most efficient way
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.
Solution 1:[1]
I would like to know if there's a better way to create the temp without having to copy everything to the temp one
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.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | eerorika |
