array <>不能简单地在内部交换指针

Question

对于使用TR1引入STL的容器数组<>,我在下面遇到问题.

在"The C++标准库A教程和参考"一书的第263页中:

但请注意,数组<>不能简单地在内部交换指针.因此,swap()具有线性复杂性以及迭代器和引用不会将容器与其元素交换的效果.

我想知道为什么array <>不能考虑交换指针的持续开销？

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;
}

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

正如您所看到的,交换指针的速度很快,但交换实数不是 - 您实际上必须交换单个元素,因此需要时间线性的元素数量.请注意,这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;
}

实例

Answer 2

std :: array是一个封装static数组的模板类,存储在对象本身中,这意味着,如果在堆栈上实例化类,静态数组将在堆栈中.它的大小必须在编译时知道.因此,它不能用指针实现(即,必须在运行时分配的动态存储器).

因此,可能的实现std::array将是:

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

正如您所看到的那样,没有指针,而是具体的数组.

你不能交换具体的数组.因此,需要线性时间来逐个元素地交换一个数组的内容与另一个数组的元素.