C++|内置数组、STL array、STL vector

2022-11-07  今日头条  小智雅汇


Built-in array: a fixed-size contiguously allocated sequence of N elements of type T; implicitly converts to a T*



A fixed-size contiguously allocated sequence of N elements of type T; like the built-in array, but with most problems solved


A vector is a sequence of elements of a given type. The elements are stored contiguously in memory. A typical implementation of vector will consist of a handle holding pointers to the first element, one-past-the-last element, and one-past-the-last allocated space (§13.1) (or the equivalent information represented as a pointer plus offsets):


In addition, it holds an allocator (here, alloc), from which the vector can acquire memory for its elements. The default allocator uses new and delete to acquire and release memory. Using a slightly advanced implementation technique, we can avoid storing any data for simple allocators in a vector object.


template<typename T>
class Vector {
       allocator<T> alloc;    // standard-library allocator of space for Ts
       T* elem;                     // pointer to first element
       T* space;                   // pointer to first unused (and uninitialized) slot
       T* last;                       // pointer to last slot
       // ...
       int size() const { return space-elem; }            // number of elements
       int capacity() const { return last-elem; }        // number of slots available for elements
       // ...
       void reserve(int newsz);                         // increase capacity() to newsz
       // ...
       void push_back(const T& t);                 // copy t into Vector
       void push_back(T&& t);                         // move t into Vector

STL array, and tuple elements are contiguously allocated; list and map are linked structures.

StL array和tuple元素被连续分配;list和map是链接结构。

An STL array, defined in <array>, is a fixed-size sequence of elements of a given type where the number of elements is specified at compile time. Thus, an array can be allocated with its elements on the stack, in an object, or in static storage. The elements are allocated in the scope where the array is defined. An array is best understood as a built-in array with its size firmly attached, without implicit, potentially surprising conversions to pointer types, and with a few convenience functions provided. There is no overhead (time or space) involved in using an array compared to using a built-in array.

在<array>中定义的STL array是给定类型的元素的固定大小序列,其中元素的数量在编译时指定。因此,可以在堆栈、对象或静态存储中为数组分配元素。元素在定义数组的范围内分配。STL array最好理解为一个内置数组(built-in array),其大小固定,没有隐含的、可能令人惊讶的指针类型转换,并且提供了一些方便的函数。与使用内置数组相比,使用STL array不需要任何开销(时间或空间)。

An array does not follow the “handle to elements” model of STL containers. Instead, an array directly contains its elements. It is nothing more or less than a safer version of a built-in array.

STL array不遵循STL容器的“句柄到元素”模型。相反,数组直接包含其元素。它或多或少是内置array的一个更安全的版本。

This implies that an array can and must be initialized by an initializer list:


array<int,3> a1 = {1,2,3};

The number of elements in the initializer must be equal to or less than the number of elements specified for the array.


The element count is not optional, the element count must be a constant expression, the number of elements must be positive, and the element type must be explicitly stated:


void f(int n)
    array<int> a0 = {1,2,3};                      // error size not specified
    array<string,n> a1 = {"John's", "Queens' "};  // error: size not a constant expression
    array<string,0> a2;                           // error: size must be positive
    array<2> a3 = {"John's", "Queens' "};         // error: element type not stated
    // ...

If you need the element count to be a variable, use vector.


When necessary, an STL array can be explicitly passed to a C-style function that expects a pointer. For example:

必要时,可以将STL array显式传递给需要指针的C样式函数。例如:

void f(int* p, int sz);         // C-style interface
void g()
        array<int,10> a;
         f(a,a.size());             // error: no conversion
         f(a.data(),a.size());      // C-style use
         auto p = find(a,777);      // C++/STL-style use (a range is passed)
         // ...

Why would we use an STL array when vector is so much more flexible? An array is less flexible so it is simpler. Occasionally, there is a significant performance advantage to be had by directly accessing elements allocated on the stack rather than allocating elements on the free store, accessing them indirectly through the vector (a handle), and then deallocating them. On the other hand, the stack is a limited resource (especially on some embedded systems), and stack overflow is nasty. Also, there are Application areas, such as safety-critical real-time control, where free store allocation is banned. For example, use of delete may lead to fragmentation or memory exhaustion.

当STL vector如此灵活时,我们为什么要使用STL array?STL array不太灵活,因此更简单。有时,直接访问堆栈上分配的元素,而不是在空闲存储(堆)上分配元素,通过vector(句柄)间接访问它们,然后释放它们,会带来显著的性能优势。另一方面,堆栈是一种有限的资源(尤其是在一些嵌入式系统上),并且堆栈溢出非常严重。此外,还有一些应用领域,如安全关键型实时控制,禁止空闲存储(堆)分配。例如,使用delete可能会导致碎片化或内存耗尽。

Why would we use an STL array when we could use a built-in array? An array knows its size, so it is easy to use with standard-library algorithms, and it can be copied using =. For example:

当我们可以使用内置数组时,为什么要使用STL array?STL array知道它的大小,因此它很容易与标准库算法一起使用,并且可以使用操作符“=”复制它。例如:

array<int,3> a1 = {1, 2, 3 };
auto a2 = a1;     // copy
a2[1] = 5;
a1 = a2;              // assign

However, the main reason to prefer STL array is that it saves me from surprising and nasty conversions to pointers. Consider an example involving a class hierarchy:


void h()
    Circle a1[10];
    array<Circle,10> a2;
    // ...
    Shape* p1 = a1;       // OK: disaster waiting to happen
    Shape* p2 = a2;       // error: no conversion of array<Circle,10> to Shape* (Good!)
    p1[3].draw();         // disaster

The “disaster” comment assumes that sizeof(Shape)<sizeof(Circle), so subscripting a Circle[] through a Shape* gives a wrong offset. All standard containers provide this advantage over built-in arrays.

“disaster”注释假定sizeof(Shape)<size of(Circle),因此通过Shape*下标Circle[]给出了错误的偏移量。与内置数组相比,所有标准容器都提供了这一优势。


Bjarne Stroustrup, A Tour of C++ Third Edition


更多资讯 >>>