12.3list
The standard library offers a doubly-linked list calledlist:
We use alistfor sequences where we want to insert and delete elements without moving other elements. Insertion and deletion of phone book entries could be common, so alistcould be appropriate for representing a simple phone book. For example:
listphone_book = { {"David Hume",123456}, {"Karl Popper",234567}, {"Bertrand Arthur William Russell",345678} };
When we use a linked list, we tend not to access elements using subscripting the way we commonly do for vectors. Instead, we might search the list looking for an element with a given value. To do this, we take advantage of the fact that alistis a sequence as described in Chapter 13:
int get_number(const string& s) { for (const auto& x : phone_book) if (x.name==s) return x.number; return 0; //use 0 to represent "number not found"}
The search forsstarts at the beginning of the list and proceeds untilsis found or the end ofphone_bookis reached.
Sometimes, we need to identify an element in alist. For example, we may want to delete an element or insert a new element before it. To do that we use aniterator: alistiterator identifies an element of alistand can be used to iterate through alist(hence its name). Every standard-library container provides the functionsbegin()andend(), which return an iterator to the first and to one-past-the-last element, respectively (§13.1). Using iterators explicitly, we can – less elegantly – write theget_number()function like this:
int get_number(const string& s) { for (auto p = phone_book.begin(); p!=phone_book.end(); ++p) if (p->name==s) return p->number; return 0; //use 0 to represent "number not found"}
In fact, this is roughly the way the terser and less error-prone range-forloop is implemented by the compiler. Given an iteratorp,*pis the element to which it refers,++padvancespto refer to the next element, and whenprefers to a class with a memberm, thenp->m相当于(*p).m.
Adding elements to alistand removing elements from alistis easy:
void f(const Entry& ee, list::iterator p, list add ee before the element referred to by pphone_book.erase(q); //remove the element referred to by q}::iterator q) { phone_book.insert(p,ee); //
For alist,insert(p,elem)inserts an element with a copy of the valueelembefore the element pointed to byp. Here,pmay be an iterator pointing one-beyond-the-end of thelist. Conversely,erase(p)removes the element pointed to bypand destroys it.
Theselistexamples could be written identically usingvectorand (surprisingly, unless you understand machine architecture) often perform better with avectorthan with alist. When all we want is a sequence of elements, we have a choice between using avectorand alist. Unless you have a reason not to, use avector. Avectorperforms better for traversal (e.g.,find()andcount()) and for sorting and searching (e.g.,sort()andequal_range(); §13.5, §15.3.3).