Containers and Lists

Section 21.1 Containers and Lists

The C++ Standard Library provides a variety of different containers that are optimized for doing different things with a collection of data.

🔗

The vector is one such container that is optimized for storing ordered collections of data where elements are accessed by their position. But it has an interesting limitation: it is only efficient at adding and removing items at the end of the collection. You can call


    .push_back()

to add an item to the end of a vector or .pop_back() to remove the last item efficiently. But adding or removing items at the front of the vector (using


    .insert()

or .erase()) is inefficient.

🔗

Figure 21.1.1. A vector stores a block of contiguous memory. Extra space is reserved at the end which makes adding new items at the end efficient. However, there is no easy way to add items at the start.
🔗

Insight 21.1.1.

The capabilities provided by the vector class are good (but not perfect) hints about what it can do well and what it cannot do efficiently. It does not provide .push_front() or


      .pop_front()

because those operations are inefficient with vectors.

🔗

So what should you do if you want to be able to add values to one end of a list and remove them from the other end? Say messages arrive into a system and you want to process them in the order they arrive. You would add new messages to the back of a list as they arrive, and remove messages from the front of the list as you process them. To do this job efficiently, we would need to look for a container that supports fast insertion and removal at both ends.

🔗

Note 21.1.2.

Processing items in this way is referred to first-in, first-out (FIFO) because the first item added is the first one to be removed.

🔗

A list is a container that is optimized for efficient insertion and removal at either end of the sequence (among other things). A list provides .push_back() to add an item to the back and .push_front() to add an item to the front. It also provides .pop_front() to remove an item from the front and .pop_back() to remove an item from the back. You can use .front() to look at the item at the front of the list without removing it, and .back() to look at the item at the back of the list without removing it.

🔗

Figure 21.1.2. A list stores elements in a linked structure allowing efficient insertion and removal at both ends.
🔗

We declare a list just like a vector by specifying the type of the items it will hold:

🔗

list<int> intList;
list<Person> registrationLine;

This sample program demonstrates using a list to add and remove items at either end, and shows FIFO behavior using .push_back() and .pop_front():

🔗

Listing 21.1.3.

🔗

Note that the <list> library must be included to use the list class.

🔗

Checkpoint 21.1.1.

Hint.

Each answer must start with the name of the list variable.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next