Using array with Standard-Library Algorithms
An array is less flexible than a vector because it is simpler, and it can offer a real performance advantage by accessing stack-allocated elements directly rather than through a handle to the free store.
Why Keep a Simpler Container
When a programmer first meets array alongside vector, a natural question follows. If vector is so much more flexible, why would anyone bother with an array at all? And when the language already provides built-in arrays, why add another option? These questions are reasonable, and the answers reveal a set of trade-offs rather than a single winner.
What do you think happens?
Before reading on: if vector can grow, shrink, and adapt, what would be a good reason to choose the less flexible array?
Reveal answer
Because array is less flexible, and that simplicity can give it a real performance advantage.
The source states that an array is less flexible than a vector because it is simpler, and that it can offer a real performance advantage by accessing stack-allocated elements directly rather than through a handle to the free store. The rest of this article traces how that advantage arises and where it stops being worth having.
The key idea is that simplicity is not only a matter of tidiness. It changes how the elements are reached in memory, and that change can matter for speed. To follow the argument, we will trace what the program does to reach an element in each case.
Where the Speed Advantage Comes From
A vector keeps its elements on the free store, which is the memory pool used for dynamic allocation. The program does not hold the elements directly. It reaches them indirectly, through the vector acting as a handle. An array can instead place its elements directly on the stack, so the elements are reached without going through that handle.
Read the diagram from top to bottom. In the array branch, the elements sit directly in the array's storage on the stack, so reaching an element is a direct access. In the vector branch, the vector object is only a handle. The elements live on the free store, and the program must go through the handle to reach them. That extra indirection is the step the array avoids, and it is the source of the performance advantage the source describes.
Size Knowledge and Copying
The source compares array with the built-in array that the language provides directly, and gives three reasons an array is preferred. First, an array knows its size. That property makes it straightforward to use with standard-library algorithms, which need to know where a sequence ends. Second, an array can be copied using assignment or initialization. Third, and the source calls this its main reason, an array saves the programmer from surprising and nasty conversions to pointers.
- An array knows its size, so algorithms can determine where the sequence ends.
- An array can be copied with assignment or initialization.
- An array avoids surprising conversions to pointers, which the source names as its main advantage over a built-in array.
Losing Size Through Decay
A built-in array does not carry its size along with it the way an array object does. The information about how many elements exist must be tracked separately, and that is a common source of errors. The more serious issue arises when a built-in array is used in an ordinary expression. It can decay to a pointer to its first element. Once that happens, the information the program was relying on is no longer attached to the value it is working with.
Decay is the conversion in which a built-in array's name is treated as a pointer to its first element. For most purposes this conversion is harmless, and it is how built-in arrays are passed around in older C-style code. The trouble begins when the pointer's type is not the same as the type of the elements actually stored. The before and after states in the diagram show the change. Before decay the array knows its size. After decay only a pointer to the first element remains.
Tracing a Shape and Circle Mismatch
The source gives a short scenario in a comment. It assumes that the size of Shape is less than the size of Circle, and then subscripts an array of Circles through a pointer to Shape. The example below uses the same relationship between a base type and a derived type. It is an illustration written for this article, not a quotation from the source.
Subscripting an Array of Circles Through a Shape Pointer
An array holds three Circle elements. The array decays to a pointer whose type is Shape, and Shape is assumed to be smaller than Circle. What goes wrong when the program subscripts that pointer?
- 1Start with the real elements
The array holds three Circle elements placed one after another. Each element occupies the full size of a Circle.
- 2Decay removes the size
The array decays to a pointer to its first element. The pointer's type is Shape, and the array's size is no longer attached to it.
- 3Compute the step
Subscripting through the Shape pointer advances by the size of Shape, which is smaller than the size of one Circle.
- 4Observe the landing point
The computed position falls partway through the first Circle rather than at the start of the second one. The program reads or writes the wrong part of the wrong element.
- 5Name the root cause
The pointer's type does not match the type of the elements actually stored, and the size that could have caught the error is gone.
The subscript silently lands inside the wrong element. No size check exists to flag it, which is why the source treats this as a serious hazard.
Mistakes Beginners Make
Common mistake Assuming array is simply a weaker vector with no reason to exist
Why it failsThe source presents the lower flexibility as the point. Simplicity changes how elements are reached in memory, and that can matter for speed.
Do this insteadTreat the reduced flexibility as a deliberate trade for simplicity and a possible performance advantage.
Common mistake Believing a built-in array always keeps track of how many elements it has
Why it failsA built-in array does not carry its size with it. The count must be tracked separately, which the source identifies as a common source of errors.
Do this insteadUse array when the size should travel with the sequence, or track the count deliberately if you use a built-in array.
Common mistake Thinking decay to a pointer is always harmless
Why it failsDecay is harmless for most purposes, but once the pointer's type differs from the stored element type, offsets can land in the wrong element.
Do this insteadKeep the pointer's type matched to the stored element type, and avoid passing a bare pointer around when the size is needed.
Common mistake Choosing array for speed without considering the stack
Why it failsElements of an array sit on the stack, which is a limited resource. Large arrays can risk stack overflow.
Do this insteadWeigh the speed advantage against the stack's limited space before choosing array for large data.
Choosing Among Array, Vector, and Built-in Array
The three options differ in how they handle size, memory location, flexibility, and performance. The comparison below summarizes what the source supports. Where the source is silent on a detail, the table does not add one.
| Option | Knows its size | Where elements live | Flexibility | Performance note |
|---|---|---|---|---|
| vector | Yes, as a container | On the free store, reached through a handle | High | Extra indirection through the handle |
| array | Yes | Directly on the stack | Low, by design | Direct access; stack size is limited |
| built-in array | No, tracked separately | Directly in its own storage | Low | Can decay to a pointer and lose size information |
Trade-offs among the three options, as described in the source
A reasonable rule follows from the table. Choose vector when the collection must grow or change shape, because its flexibility is the reason to use it. Choose array when the sequence has a fixed size, the speed of direct access matters, and the stack can comfortably hold the elements. Prefer array over a built-in array when the sequence will be passed around, copied, or used with standard-library algorithms, because array keeps its size and avoids the surprising pointer conversions. Keep a built-in array for code that must follow older C-style conventions, and then take care to track its size yourself.
Checking Your Understanding
A function receives a built-in array of Circle elements as a bare pointer whose type is Shape, and Shape is smaller than Circle. Explain in your own words why a subscript through that pointer can land inside the wrong element, and say what information was lost during decay.
Hints
- Think about what size the pointer uses for each step.
- Ask whether the pointer still carries the number of elements.
- Compare the step size with the size of one real Circle.
Name the choice you would make for a fixed-size list of sensor readings that a library function must process with standard-library algorithms, and justify it using size knowledge and the stack trade-off.
Hints
- Consider whether the sequence needs to know where it ends.
- Consider how large the list is and whether it fits comfortably on the stack.
Key Takeaways
- An array is less flexible than a vector because it is simpler, and that simplicity can give it a real performance advantage by letting the program reach stack-allocated elements directly rather than through a handle to the free store.
- The stack is limited, so the speed of an array must be weighed against the risk of stack overflow.
- A built-in array can decay to a pointer to its first element, and then it loses its size. Subscripting through a pointer of a mismatched type can compute the wrong offset and land inside the wrong element.
- An array knows its size, can be copied by assignment or initialization, and avoids surprising pointer conversions, which makes it well suited to standard-library algorithms.
- Choose vector when the collection must change shape, array for fixed-size sequences that benefit from direct access and size knowledge, and a built-in array only when older conventions require it.