array<> can’t simply swap pointers internally

Question

For the container array<> introduced to STL with TR1, I have a problem below.

In Page 263 of book "The C++ standard library A Tutorial and Reference":

Note, however, that an array<> can’t simply swap pointers internally. For this reason, swap() has linear complexity and the effect that iterators and references don’t swap containers with their elements.

I wondered why array<> cannot considering its constant overhead for swapping pointers?

Answer 1

You're probably falling for the fallacy of "C[++] arrays are just pointers." No, they are not. In some contexts (mostly function calls), arrays decay to pointers. More formally, an implicit conversion exists from an array to a pointer to its first member.

But they are entirely different things. A pointer is an address - typically 4 or 8 bytes, depending on the HW. An array is a sequence of objects one after the other. sizeof can tell the difference:

int main()
{
  int arr[5];
  int *p = arr;  // decay/implicit conversion happening here
  std::cout << sizeof arr << ':' << sizeof p;
}

This will output 20:4 on a typical 32-bit PC.

So as you can see, swapping pointers is fast, but swapping real arrays is not - you really have to swap individual elements, so that takes time linear in the number of elements. And note that std::array is indeed a wrapper around an array.

---

The confusion is made worse by an ufortunate C and C++ syntax decision - on function parameter types, array syntax can be used, but the "decay" is performed on the type itself. Which means that functions like this:

void foo(int a[]);
void bar(char b[40]);

do not actually take arrays, they take pointers. These function declarations are exactly the same as these:

void foo(int *a);
void bar(char *b);

So much so that you can actually use one as a forward declaration for the other:

#include <iostream>

void foo(int a[40]);

int main()
{
    int x = 42;
    foo(&x);
}

void foo(int *a)
{
    std::cout << a[0] << std::endl;
}

Live example

Answer 2

std::array is a template class that encapsulate a static array, stored inside the object itself, which means that, if you instantiate the class on the stack, the static array will be on the stack. Its size has to be known at compile time. Thus it can't be implemented with pointers (i.e., dynamic memory which has to be allocated in runtime).

Thus, a possible implementation for std::array would be:

template<class _Ty, size_t _Size>
class array {
  //...
  _Ty _Elems[_Size == 0 ? 1 : _Size];
};

As you can see there are no pointers involved but rather concrete arrays.

You can't swap concrete arrays. Thus, it takes linear time to swap element by element the contents of one array with the elements of the other.