Game Development Reference
In-Depth Information
The
OurList
function creates three nodes to add to our list, each storing an
unsigned int
to illustrate
the result when we loop over the list. What you can see is that the
m_Next
pointer of
first
is set to
point to the
ListNode second
. In turn
second
points back to
first
and forward to
third
and
third
points back to
second
.
The
for
loop in the function then traverses the list and prints the value stored by each. It does this
by faking an iterator to the list. In fact, all we do is get a pointer to
first
, then have the
iter
pointer
be updated to
iter->GetNext()
each time the loop iterates. Eventually we get to third's
m_Next
pointer, which will be set to
nullptr
, and the loop ends. At this point you could delve deeper into
implementing your own lists; however, I would recommend sticking to the STL
list
template. All of
the features you might like in a list have already been implemented and the STL
list
is compatible
with all of the iterator types and algorithms that also support other STL containers.
The STL List Template
You will not be surprised to hear that STL's
list
syntax is very similar to that of
vector
. You can see
this in Listing 15-3.
Listing 15-3. STL
list
using namespace std;
using MyList = list<int>;
MyList myList = { 0, 1, 2 };
myList.push_back(3);
myList.push_back(4);
MyList::const_iterator iter = myList.cbegin();
++iter;
Iter = myList.insert(iter, 5);
myList.erase(iter);
There is only a single difference between this code when using a
list
compared to using a
vector
:
list
iterators cannot be modified using the
+
and
-
operators. Instead we get the iterator and then
use the
++
or
--
operators to move to the position in the list where we would like to insert or erase
elements. The iterator we have also remains pointing to the same element after we insert into
myList
. To be able to remove the correct element we had to catch the new iterator returned by the
insert
method.
The last major difference in usage between
list
and
vector
is that the
[]
operator is not supported
by
list
. This makes sense if you think back to the way that these containers store their elements in
memory. Generally
vector
is implemented using arrays internally, which means that it's easy to use
the
[]
operator and pointer arithmetic to offset into the
array
to get the proper element for a given
index. This operation doesn't make any sense for a
list
where the underlying implementation does
not store elements contiguously in memory.
STL's list implementation supports all of the same iterator types and the
find
algorithm that we
looked at in Chapter 14. The
sort
function is a little different and is implemented as a method rather
than a stand-alone function. Listing 15-4 shows the
list::sort
method in action.
