STL List - Learn C++ for Game Development - page 153

The problem with arrays arises when you do not know exactly how many elements you need at
compile time. Compilers require you to inform them of how many elements will be in your array so
that they can allocate the proper memory for storage. The vector class provides a resizable array,
but this is a little bit of a trick. The vector works by providing more storage than you actually need
when the vector is initialized. If you add more elements than the vector currently has capacity for,
the template requests a new array from the operating system, which is usually double the size of the
current capacity. The vector then copies all of the elements from the old array into the new array.
If you are doing this resizing often, a vector can prove to be a fairly slow container.
A linked list, on the other, hand does not store its elements in a contiguous block of memory.
Instead each element in the list stores a pointer to the next and previous elements in order. This
provides a container that is resizable and can provide for fast inserting and removal of elements
in the list. However, because the list is noncontiguous in memory, the processor cannot use its
cache as effectively when traversing the list. Many C++ courses like to teach the list, as it's a good
introduction to data structures. Unfortunately for game developers, the list is rarely a good choice
for code that you would like to perform as efficiently as possible due to the cache implications. This
chapter shows you how to create your own list and how to use the STL list , but you should always
keep the memory and cache implications in mind.
Building a List Class
Building a linked list is a fairly straightforward process once you understand how to use pointers.
If you need to recap what pointers are and how they work, I suggest that you reread Chapter 4
before continuing. Listing 15-1 shows the ListNode class.
Listing 15-1. ListNode
class ListNode
{
private:
void* m_Data = nullptr;
ListNode* m_Last = nullptr;
ListNode* m_Next = nullptr;
public:
ListNode(void* data)
: m_Data{data}
{
}
void* GetData()
{
return m_Data;
}
void SetLast(ListNode* last)
{
m_Last = last;
}