数组<>内部不能简单地交换指针

Question

对于STL中引入的容器数组<>，我有以下问题。在书籍《The C++ standard library A Tutorial and Reference》的第263页中提到：

请注意，一个数组<>无法简单地在内部交换指针。因此，swap()具有线性复杂度，并且迭代器和引用不会与其元素一起交换容器。

我想知道为什么数组<>不能考虑指针的常数开销而进行交换？

- Rui Xu

---

可能是因为它没有使用指针来实现。 - 101010

它的设计旨在成为C语言风格数组的零开销替代品。因此，它直接持有数据。没有指向存储在其他地方的数据的指针，因此不能通过简单的指针交换来交换数据。 - juanchopanza

Answer 1

你可能会犯“C++数组就是指针”的谬论，但实际上并不是这样。 在某些情况下（主要是函数调用），数组会衰变成指针。更正式地说，从数组到其第一个成员的指针存在隐式转换。

但它们是完全不同的东西。指针是一个地址——通常是4或8个字节，取决于硬件。而数组是一个接一个的对象序列。sizeof可以区分它们：

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

在典型的32位PC上，这将输出20:4。

所以，正如您所看到的，交换指针很快，但交换实际数组不快——您必须逐个交换元素，因此这需要与元素数量成线性时间。请注意，std::array确实是一个数组包装器。

---

C和C ++语法决策使混淆变得更加糟糕——在函数参数类型上，可以使用数组语法，但“衰减”是在类型本身上执行的。这意味着像这样的函数：

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

并不是实际地取数组，而是取指针。这些函数声明与下面的声明完全相同：

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

如此之多，以至于你实际上可以将其中一个作为另一个的前向声明使用：

#include <iostream>

void foo(int a[40]);

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

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

实时示例

- Angew is no longer proud of SO

Answer 2

std::array是一个模板类，封装了一个静态数组，并将其存储在对象内部，这意味着如果你将该类实例化到栈中，静态数组也将在栈上。 其大小必须在编译时知道，因此不能用指针（即必须在运行时分配的动态内存）来实现。

因此，对于std::array的一个可能的实现是：

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

正如您所看到的，这里没有指针，而是具体的数组。

你不能交换具体的数组。 因此，将一个数组的元素与另一个数组的元素逐个交换需要线性时间。

- 101010

---

您的“可能”的实现中没有指针。这并不说明为什么不能用指针进行“可能”的实现。 - juanchopanza

@juanchopanza 谢谢，已解决。 - 101010

这样更好。将-1换成+1。 - juanchopanza