Storing Objects in a list

Problem

You need to store items in a sequence, but your requirements don't match up well with a vector. Specifically, you need to be able to efficiently add and remove items in the middle of the sequence, not just at the end.

Solution

Use a list, declared in , to hold your data. lists offer better performance and more flexibility when modifying the sequence at someplace other than the beginning or the end. Example 6-5 shows you how to use a list, and shows off some of its unique operations.

Example 6-5. Using a list

#include #include #include #include using namespace std; // A simple functor for printing template struct printer { void operator( )(const T& s) { cout << s << ' '; } }; bool inline even(int n) { return(n % 2 == 0); } printer strPrinter; printer intPrinter; int main( ) { list lstOne; list lstTwo; lstOne.push_back("Red"); lstOne.push_back("Green"); lstOne.push_back("Blue"); lstTwo.push_front("Orange"); lstTwo.push_front("Yellow"); lstTwo.push_front("Fuschia"); for_each(lstOne.begin( ), // Print each element in the list lstOne.end( ), // with a custom functor, print strPrinter); lstOne.sort( ); // list has a member for sorting lstTwo.sort( ); lstOne.merge(lstTwo); // Merge the two lists and print for_each(lstOne.begin( ), // the results (the lists must be lstOne.end( ), // sorted before merging) strPrinter); list intLst; intLst.push_back(0); intLst.push_back(1); intLst.push_back(2); intLst.push_back(3); intLst.push_back(4); // Remove all values greater than 2 intLst.remove_if(bind2nd(greater( ), 2)); for_each(intLst.begin( ), intLst.end( ), intPrinter); // Or, remove all even values intLst.remove_if(even); }

Discussion

A list is a sequence provides constant complexity for inserting or deleting elements at any position, but it requires linear complexity to find elements. lists are usually implemented as a doubly linked list, which means that each element is stored in a node that has a pointer to its previous and next elements in the sequence. It meets all the requirements of a standard sequence container, plus provides a few unique member functions.

Declaring a list is straightforward, just give it the type of the elements you're going to store in it, and, optionally, specify a memory allocation class:

list > // The memory allocator // to use

The Value template parameter is the type of the elements that will be stored in the list. It must be a type that supports copy construction and assignment. Allocator is the memory allocation class to use; the standard allocator is the default (and will be sufficient for most of your needs).

Following is a typical list declaration (from Example 6-5):

list lstOne;

After you've declared your list, put some things in it with push_front or push_back, like this:

lstOne.push_back("Red"); // Add these to the end of the list lstOne.push_back("Green"); lstOne.push_back("Blue"); lstTwo.push_front("Orange"); // Add these to the beginning lstTwo.push_front("Yellow"); lstTwo.push_front("Fuschia");

Pushing elements on a list takes constant time, but not amortized constant time as with a vector. A list implementation does not need to occasionally resize its buffer, so you won't have the intermittent performance penalty you would with a vector. The list will just have to update a handful of pointers, and not much else.

Use pop_front or pop_back (no arguments) to remove elements from the beginning or end of the list. Despite their name, the "pop" member functions don't return the popped element, as you might expect à la typical stack semantics; to get a reference to the element at the beginning or end of a sequence, use back or front.

Typically, a list looks like what is displayed in Figure 6-2. Each node has (at least) three parts: the object it contains, a pointer to the previous node, and a pointer to the next node. For the rest of this recipe, I will refer to the next and previous pointers as next_ and prev_.

Figure 6-2. A doubly linked list

Once you see how a list is implemented, it's probably obvious why some of the operations have different complexity than a vector. Adding an element anywhere in the list requires only that the preceding and following items have their next_ and prev_ pointers adjusted. One nice thing about lists is that only iterators pointing to the affected object(s) are invalidated when you insert or erase elements. Iterators to other elements are unaffected.

The insertion and deletion methods are insert and erase. insert takes an iterator as its first argument, and either an object of type T, a number and then an object of type T, or an ending iterator as its second argument. The iterator points to the item that is to have the insert performed immediately preceding it. Each of the insert overloads is used like this:

list strLst; list::iterator p; // ... string s = "Scion"; p = find(strLst.begin( ), strLst.end( ), // std::find from "Toyota"); strLst.insert(p, s); // Insert s right before p strLst.insert(p, 16, s); // Insert 16 copies of s right before p strLst.insert(p, myOtherStrLst.begin( ), // Insert everything in myOtherStrLst.end( )); // myOtherStrLst before p

Erasing elements is similar:

p = find(strLst.begin( ), strLst.end( ), // std::find from "Toyota"); strLst1.erase(p); // Erase this element strLst2.erase(p, strLst.end( )); // Erase p to the end strLst3.clear( ); // Erase all elements

In addition to the standard container member functions, list provides a few interesting ones. The first is splice .

splice does what it sounds like: it splices two lists together. Here's how I could have spliced lstTwo into lstOne in Example 6-5:

list::iterator p = // Find somewhere to insert the other std::find(lstOne.begin( ), // list lstOne.end( ), "Green"); lstOne.splice(p, lstTwo); // Insert lstTwo right before "Green"

p is an iterator that refers to an element in lstOne. lstTwo is inserted into lstOne immediately preceding p. As with an insertion, all that really needs to be done here is to change the next_ and prev_ pointers on the affected nodes, so this operation takes constant time. lstTwo is empty after you splice it into lstOne, which is why it is not a const parameter. You can also insert a single element from lstTwo into lstOne, or a range of items from lstTwo. In both cases, the items that are spliced in are removed from the originating list.

If your lists are sorted (list has its own sort member function; std::sort won't work with a list), and you want to merge them together and preserve their sorted order, use merge instead of splice. merge will combine the two lists into one, and if two elements are equivalent, the one from lstOne comes first in the final list. As with splice, the argument list is empty afterward.

list also has some cool aggregate operations for removing things. Imagine that you want to erase all occurrences of an element. All you have to do is call remove with an argument that, when compared to each item in the list, will give (*p == item) != false, where p is a list iterator. Call remove like this:

strLst.remove("Harry");

This will remove all elements from strLst where el == "Harry". If you want to remove elements that satisfy some other predicate, such as being larger than some value, use remove_if instead:

bool inline even(int n) { return(n % 2 == 0); } list intLst; // Fill up intLst... intLst.remove_if(even); // Removes all elements where even(*p) // is != false

If your predicates are more complicated, consider using some of the functors in . For example, if you want to remove elements that are greater than some value, you can use greater (from ) and bind2nd combined with remove_if:

intLst.remove_if(std::bind2nd(std::greater( ), 2));

This will remove all values greater than 2 from intLst. The syntax is a little esoteric, but what's happening is straightforward. bind2nd takes two arguments, a function object (call it f) and a value (v), and returns a function object that takes a single argument (arg) and invokes f(arg, v). bind2nd is a slick way to do just this sort of thing without having to write a bunch of little functions.

A list is a good alternative to vector when you need a standard sequence container. list's different internal representation permits it to provide different complexities for many of the standard sequence operations and a few interesting operations of its own.

See Also

Recipe 6.1