This chapter is from the book
This chapter is from the book
This chapter is from the book
Iterators
Containers such as lists and maps do not behave like arrays, so you can't use a for loop to go through the elements in them. Likewise, because these containers are not accessible randomly, you cannot use a simple integer index. You can use iterators to refer to elements of a container.
Iterating through a Container
Each container type has a distinct iterator associated with it. For instance, this is how you declare the iterator for list<int>:
;> list<int>::iterator ili;
You have previously seen the operator :: in two forms: as the global scope operator (where it has one operand) and in the constant ios::app. Each container type has a scope that contains a type name (iterator), and the scope operator (::) allows you to access that type name. Again, using typedef can make for easier typing and understanding, as in the following example; remember that ILI is a completely different name from ili in C++:
;> typedef list<int> LI; ;> typedef LI::iterator ILI; ;> LI ls; ls.push_back(1); ls.push(2); ;> ILI ili = ls.begin(); ;> *ili; (int) 1 ;> ++ili; ;> *ili; (int) 2 ;> for(ili = ls.begin(); ili != ls.end(); ++ili) ;1} cout << *ili << endl; 1 2
In this example, the iterator ili is used for accessing the contents of the list ls. First, a list ls is created, and the numbers 1 and 2 are added to it. Then the iterator ili is declared and set to ls.begin(). The expression *ili gives you the first value in ls, and ++ili moves the iterator to the next value. You use the dereference operator (*) to extract the value and the increment operator (++) to move to the next list item. (Note that * is used for both dereferencing and multiplication, in the same way that - is used for both -2.3 and 2-3. The unary and binary forms of the operator are quite different from one another.) The method begin() returns an iterator that points to the beginning of the list, but the method end() returns an iterator that is just beyond the end of the list. Once ++ili has moved the iterator past the end, then ili becomes equal to ls.end(). Therefore, the for loop in the example visits each item in the list. This technique works for any list type, and it is a very common way of iterating over all items in a list. The vector—and in fact, any standard container—can also be traversed by using an iterator, as in the following example:
;> vector<string>::iterator vsi; ;> string tot; ;> for(vsi = vs.begin(); vsi != vs.end(); ++vsi) tot += *vsi;
In a case like this, you would use a plain for loop and use the vector as if it were an array, but being able to iterate over all containers like this allows you to write very general code that can be used with both vectors and lists.
Finding Items
Reinventing the wheel wastes your time and confuses those that follow you. The standard library provides a number of ready-to-use algorithms that do common tasks like searching and sorting. For instance, find() does a simple linear search for a value and returns an iterator that points to that value if it is successful. You specify the data to be searched by a pair of iterators. Assume that you have a list of strings, ls, which contains "john", "mary", and "alice":
;> list<string> iterator ii; ;> ii = find(ls.begin(), ls.end(), "mary"); ;> *ii (string&) `mary' ;> *ii = "jane"; (string&) `jane'
Note that *ii can be assigned a new value, too: It is a valid lvalue (short for left-hand value) and so can appear on the left-hand side of assignments. Because *ii is a reference to the second item in the list, modifying *ii actually changes the list. If find() does not succeed, it returns ls.end().
You might wonder why you can't just pass the list directly to find(). The standard algorithms could do that but they prefer to work with sequences. Consider the following example of finding the second occurrence of 42 in a list of integers li. You use the result of the first find() as the start of the sequence for the second find(). We have to increment the iterator because it will be pointing to 42 after the first find().
;> list<int>::iterator ili; ;> ili = find(li.begin(),li.end(),42); // first position ;> ++ili; // move past the `42' ;> ili = find(ili,li.end(),42); // second position ;> *ili; (int&) 42
find() accepts a sequence and not a container argument for another good reason: find() can work with ordinary arrays, which are not proper containers and have no size information. The following example illustrates this, with the standard algorithm copy(), which copies a sequence to a specified destination:
;> int tbl[] = {6,2,5,1};
;> int cpy[4];
;> copy(tbl,tbl+4,cpy);
;> show_arr(cpy,4);
6 2 5 1
;> int array[20];
;> copy(li.begin(), li.end(), array);
;> *find(tbl,tbl+4,5) = 42;
;> show_arr(tbl,4);
6 2 42 1
Note in this example how you specify the end of an array. copy() is very useful for moving elements from one type of container to another. For example, in this example, you move a list of integers into an array. Again, it is important that the array be big enough for the whole list; otherwise, you could unintentionally damage program memory. Likewise, you can use find(). The call returns a reference to the third element of tbl, which is then changed to 42.
If you have a sorted array-like sequence, then using binary_search() is much faster than find(), as discussed previously. A binary search requires a random access sequence, so it does not work for lists. Maps already have their own find() method, and the generic find() won't work on them.
Erasing and Inserting
Both vectors and lists allow you to erase and insert items, although these operations are faster with lists than with vectors. You specify a position using an iterator, such as the iterator returned by find(). Insertion occurs just before the specified position, as in the following example:
;> list<string> ls;
;> list<string>::iterator ils;
;> ls.push_back("one");
;> ls.insert(ls.end(),"two"); // definition of push_back()!
;> ls.insert(ls.begin(),"zero"); // definition of push_front()!
;> ils = find(ls.begin(),ls.end(),"two");
;> ls.insert(ils, "one-and-a-half");
;> while (ls.size() > 0) {
;1} cout << ls.back() << ` `;
;1} ls.pop_back(); // emptying the list in reverse
;1} }
two one-and-a-half one zero
vectors have methods for inserting and erasing elements, and they all involve moving elements. To erase the second element in a vector (remember that we are counting from zero and begin() refers to the first element), you would use code like this:
;> vi.erase(vi.begin() + 1); ;> vi.erase(vi.end() - 1); // same as pop_back() !