Game Development Reference
In-Depth Information
The
insert
method requires the use of our
pair
template to add values to
myMap
. You can see
that we first construct the
MyPair
object
node
with the key 4 and value Four. After this, I've added
an example of the
emplace
method. You can see how it can be more efficient to use
emplace
compared with
insert
in this example. You can leave out the creation of the
pair
object and a
subsequent copy from the
pair
into the
map
by using
emplace
. The
map
shares a property with
set
:
Both containers sort their values as they are entered. A
map
container will sort the keys into order
as the elements are entered. This is the reason you would use a
map
rather than a
set
. If you have a
complex class that you would like to store objects of in a
map
then the sorting and retrieval of these
objects would be more efficient if you supplied simple data types such as integers as keys. It would
also be possible to store two objects that are identical into a
map
by giving both objects different
keys, as only the keys in a
map
are required to be unique.
Unsurprisingly, a
map
cannot be iterated with exactly the same code as some of the other containers,
as it stores elements as key-value pairs and our loops must take this into account. Listing 16-5
shows an example of how we can loop over all of the elements stored in a
map
.
Listing 16-5. Looping over a
map
for (const auto& node : myMap)
{
cout << "First: " << node.first << " Second: " << node.second << endl;
}
The
for
loop itself is the same and C++ has allowed us to abstract out the
MyPair
type by using the
auto
keyword in its place. You can access the key and value stored in a
pair
using the
first
and
second
variables. The
first
variable stores the key and
second
stores the value.
The
find
method also supplies an iterator to a
map
that represents a
pair
element, as you can see in
Listing 16-6.
Listing 16-6. Using
map::find
MyMap::iterator found = myMap.find(2);
if (found != myMap.end())
{
cout << "Found First: " << found->first << " Second: " << found->second << endl;
}
To find a value in a
map
you can use the
find
method on the
map
itself, not the stand-alone
find
algorithm. The
find
method takes the key you wish to search for as a parameter and if that key does
not exist, the end element of the
map
is returned.
Binary Search Trees
At this point we have covered five different STL containers. In the previous chapter I explained the
difference between the way a list and a vector are implemented.
set
and
map
are also implemented
differently to the linear containers. The
map
and
set
containers are implemented as binary search trees.
A node in a binary search tree stores pointers to two nodes, one to the left and one to the right.
Figure
16-1
shows a visual representation of a tree.
