4 ms·
std::array is not really comparable since its size is fixed at compile time. std::vector or std::list are more similar. The big advantage is creating copies. C
by kr7 10y ago
std::array is not really comparable since its size is fixed at compile time. std::vector or std::list are more similar.
The big advantage is creating copies. Copying a list or vector is O(n) in both time and memory, while this is O(1) in both.
An std::shared_ptr to a const list or vector is O(1) in both for copies. But almost any modifications will be O(n).
For this data structure, almost all operations are O(log(n)).
A summary of their algorithmic complexities:
Copy:
std::vector : O(n) time and memory
std::shared_ptr<const std::vector> : O(1) time and memory
immutable::Array : O(1) time and memory
Append:
std::vector : Amortized O(1)
std::shared_ptr<const std::vector> : O(n)
immutable::Array : O(log(n))
Access at index:
std::vector : O(1)
std::shared_ptr<const std::vector> : O(1)
immutable::Array : O(log(n))
Insert at index:
std::vector : O(n)
std::shared_ptr<const std::vector> : O(n)
immutable::Array : O(log(n))
Replace at index:
std::vector : O(1)
std::shared_ptr<const std::vector> : O(n)
immutable::Array : O(log(n))