Game Development Reference
In-Depth Information
Chapter
15
STL List
The STL
list
template is another linear data collection. The previous chapter briefly mentioned
the difference between
array
,
vector
, and
list
, and this chapter goes into more detail about why
and when you would use these different collections. The main point to remember is that you should
always use the correct tool for the job at hand. Video games rely on extracting the most performance
possible from the target hardware, and access times to data in collections is a major bottleneck with
modern processors. This chapter shows you how to build your own
list
class in an effort to help
you understand the difference between arrays and linked lists.
Understanding
Array
and
List
Memory Layouts
An array is a very efficient method for storing a fixed number of elements. The compiler will pack
each of the elements in your array into a
contiguous
block of memory. You can see this contiguous
memory in action when you work with pointers to arrays and you move between array elements
using pointer arithmetic. As integers are usually 4 bytes in size, you can move from one integer to
the next in an array by adding 4 bytes to the current memory address for the element you have a
pointer to. The same happens when we are working with arrays of any given type: The compiler
can automatically work out the number of bytes required to represent the type and move between
elements efficiently.
This contiguous memory access suits modern processors due to their use of cache memory. A
processor can calculate arithmetic and other instructions at a much faster rate than it can read from
memory. To combat this, processors read from memory in blocks known as cache lines into an
on-die fast memory. It's not uncommon for processors to read in blocks of 64 or 128 bytes. Even if
you need to read only 4 bytes of memory to access an integer, the processor will read a full cache
line. This means that array accesses are very efficient on modern processors because whole chunks
of an array can be read into the processor's cache when you access the first element in the array.
163
