CODEWITHSUNDEEP
c++arrays
Martin Drozdik
Martin Drozdik

Reputation: 13313

What is the cost of swapping two std::array<T, 100> objects?

I imagine the internals of a std::vector to be a pair of pointers pointing to the beginning and the end of the occupied memory and an integer specifying the length of the memory array that belongs to the vector. Therefore swapping two vectors of the same size should cost only 3 swaps of built in types.

However I almost never use std::array and therefore I do not know how to imagine its internals. Intuitively, since the compiler already knows the size of the array there is no need to store the end of the array or the size of preallocated memory so its internals should be just 1 pointer. Therefore the cost should be just 1 built in type swap.

Instead the documentation says that the cost is linear in the number of elements. Why is this so?

Upvotes: 1

Views: 1075

Answers (2)

Shoe
Shoe

Reputation: 76280

Therefore the cost should be just 1 built in type swap. Instead the documentation says that the cost is linear in the number of elements. Why is this so?

Because the complexity for a C-style array is linear and std::array is just a wrapper to a C-style array. Intuitively this is obvious: you have to swap every element of the array with each other.

I imagine the internals of a std::vector to be a pair of pointers pointing to the beginning and the end of the occupied memory and an integer specifying the length of the memory array that belongs to the vector.

Well, maybe. Some implementations just store a pointer to a dynamically allocated array, an std::size_t member and an integral value for the capacity (there's no need to store the pointer to the end of the array as it can be easily retrieved via begin + size), with the cost of pointer arithmetics when calling push_back or end. Other implementations store two pointers to the begin and end (like you said) with the cost of end - begin when calling size.

Intuitively, since the compiler already knows the size of the array there is no need to store the end of the array or the size of preallocated memory so its internals should be just 1 pointer.

No, the std::array class is just "an aggregate type with the same semantics as a struct holding a C-style array T[N] as its only non-static data member".

Upvotes: 1

user395760
user395760

Reputation:

Because an array is not a pointer. It's literally n inline values. A std::array doesn't allocate space elsewhere for N objects, it is the space for N objects, as if it has members value1, value2, value3, ... only with a guarantee of no padding (which allows indexing). You're thinking of the as-of-yet-hypothetical std::dynarray. These two objects:

std::array<T, 100> a;
std::dynarray<T> b;

looks like this in memory:

a: +-+-+-+-+-+
   |T|T|T|...|
   +-+-+-+-+-+

b: ptr ----------> +-+-+-+-+-+
                   |T|T|T|...|
                   +-+-+-+-+-+

Upvotes: 6

Related Questions