Author : Mumit Khan
Page : << Previous 6 Next >>
for_each algorithm. Let's say, we have a list of appointments and every day we'd like to print out the ones for that day are. Here's a tentative approach:
class Appointment {
public:
//
// define all the usual members ...
//
bool today(Date const& date) const;
private:
//
// private stuff here.
//
};
typedef list<Appointment> Appointments;
Appointments appt_book;
//
// define a general function
//
void print_todays_appt(Appointment& const appt) {
if (appt.today(date))
print_appt(appt);
}
//
// and here's how it's used.
//
for_each(appt_book.begin(), appt_book.end(), print_todays_appt);
Another common scenario is when you would like to modify each of the container elements within a given range; eg., let's say you would like to negate all the elements of the list. The following code shows how:
//
// define an appropriate algorithm that will modify the element
// in place calling the supplied function object.
//
template <class OutputIterator, class UnaryOperation>
void modify_element(OutputIterator first, OutputIterator last,
UnaryOperation op) {
while (first != last) {
*first = op(*first);
++first;
}
}
list<int> list1;
//
// populate list1 with what-not.
//
modify_element(list1.begin(), list1.end(), negate<int>());
STL iterators
what does iterator::end() return?
For any STL (compliant) container, iterator::end() points to a location one beyond the last item in the container, and hence is an "invalid pointer"; iterator::end() does not point to the last item in the container, rather it points to the location where the next item would go into the container if you were to use push_back.
Why point beyond the end of the container? Why not point at the last item? The reason is quite simple: Remember that STL containers emulate (or try to as faithfully as possible) C pointer semantic and end() returns the equivalent of C 0 pointer.
Consider how else you would do the following if end() instead returned the last item in the container.
MyMap::const_iterator it = my_map.find(key);
if (it == my_map.end())
no_such_key();
else
found_key();
or,
bool empty(const STL_Container& container) {
return container.begin() == container.end();
}
STL_Container::begin() returns the first item in the container if it exists or end() otherwise.
STL_Container::end() returns one-past the end of the container.
Const'ness of iterators
Make sure that iterators follow the const'ness (or lack thereof) of the containers. Most compilers utter absolutely confusing errors messages when you try to use a non-const iterator with a const container. Consider the following:
#include <stl.h>
void foo(const list<int>& list1) {
list<int>::iterator it = list1.begin();
for(; it != list1.end(); ++it) {
;
}
}
and here's the error message from GNU C++ 2.6.3:
g++ -g -I/usr/local/ospace -I/usr/local/ospace/include -c const_iterator.cc -o const_iterator.o
const_iterator.cc: In function `void foo(const class list<int> &)':
const_iterator.cc:5: no matching function for call to `list_iterator<int>::list_iterator<int> (list_const_iterator<int>)'
/usr/local/ospace/ospace/stl/list.h:5: candidates are: list_iterator<int>::list_iterator(const list_iterator<int> &)
/usr/local/ospace/ospace/stl/list.h:79: list_iterator<int>::list_iterator()
/usr/local/ospace/ospace/stl/list.h:131: list_iterator<int>::list_iterator(os_list_node<int> *)
const_iterator.cc:5: in base initialization for class `list_iterator<int>'
const_iterator.cc:6: no conversion from `list_iterator<int>' and `list_const_iterator<int>' to types with default `operator !='
gmake: *** [const_iterator.o] Error 1
Of course the correct way is to use list<int>::const_iterator instead as shown here:
#include <stl.h>
void foo(const list<int>& list1) {
list<int>::const_iterator it = list1.begin();
for(; it != list1.end(); ++it) {
;
}
}
Using iterator tags
On occasion, it is useful to dispatch based on the iterator type (mostly due to efficiency in my experience). Iterators provide a mechanism called iterator_category that allows to overload or specialize based on what kind of iterator it is. Let's take the STL sort algorithm for example; it's is specified to work only containers that provide random-access iterators, which leaves list out of it since list only provides bidirectional iterators. The following variation of sort, hereby dubbed generalized_sort lets you sort any container. Note the use of value_type as well.
//
// slightly modified STL standard sort() algorithm to not exclude
// containers that do not support Random Access Iterators. Uses the
// same interface as HP reference sort(first, last) interface.
//
// This code used with libg++ STL tweaks the infamous "template
// unification failed" problem in all version of, so caveat emptore.
// OS STL<ToolKit> works around this gcc problem.
//
// Mumit Khan <khan@xraylith.wisc.edu>
//
//
#include <stl.h>
template <class RandomAccessIterator, class T>
inline void __generalized_sort (
RandomAccessIterator first,
RandomAccessIterator last,
random_access_iterator_tag,
T*
) {
sort(first, last);
}
//
// highly inefficient, but proves the point.
//
template <class BidirectionalIterator, class T>
inline void __generalized_sort (
BidirectionalIterator first,
BidirectionalIterator last,
bidirectional_iterator_tag,
T*
) {
deque<T> deque1;
copy(first, last, back_inserter(deque1));
sort(deque1.begin(), deque1.end());
copy(deque1.begin(), deque1.end(), first);
}
template <class BidirectionalIterator>
inline void generalized_sort (
BidirectionalIterator first,
BidirectionalIterator last
) {
__generalized_sort(
first, last, iterator_category(first), value_type(first)
);
}
Miscellaneous examples/notes
Copy between lists: right way and wrong way
When using copy, remove_copy, et al algorithms that potentially copy from one sequence to another, make sure the target container is at least as large as the resultant container is likely to get. You have to be extra careful when copying from one list (populated) to another (just defined, so unpopulated).
Consider the following:
list<int> list1;
//
// populate list1 with what-not.
//
list<int> list2;
// DOESN'T WORK.
copy(list1.begin(), list1.end(), list2.begin());
// this works because back_list_iterator invokes push_back() which
// dynamically resizes the list as appropriate. Note that if the
// target were a set, inserter would've been
// the appropriate one.
copy(list1.begin(), list1.end(), back_list_iterator<int> (list2));
Copy between maps
Must use an insert_iterator that uses an auxiliary iterator.
#include <stl.h>
#include <math.h>
#include <iostream.h>
typedef map<int, float, less<int> > MyMap;
void dump_map(ostream& os, const MyMap& map_) {
for(MyMap::const_iterator i = map_.begin(); i != map_.end(); ++i) {
os << "(" << (*i).first << " " << (*i).second << ") ";
}
}
int main(int, char*[]) {
MyMap map1;
for(int i = 1; i < 5; ++i)
map1[i] = sqrt(i);
MyMap map2;
for(i = 10; i < 15; ++i)
map2[i] = sqrt(i);
cerr << "==> Map1" << endl;
dump_map(cerr, map1);
cerr << endl << endl;
cerr << "==> Map2" << endl;
dump_map(cerr, map2);
cerr << endl << endl;
copy(map2.begin(), map2.end(),
insert_iterator<MyMap> (map1, map1.begin())
);
cerr << "==> Map1 += Map2" << endl;
dump_map(cerr, map1);
cerr << endl << endl;
return 0;
}
Adaptors in STL: not1, stack, queue, etc
The adaptors in STL fall in 2 general categories: function adaptors and data type adaptors.
Function adaptors
Study the adaptors, such as not1(). These are wonderful to create new algorithms. bind2nd, bind1st are great.
For example, you can create copy_if from remove_copy_if by negating the predicate that you supply to remove_copy_if().
//
// fill up a list with some numbers.
//
const int list1[] = {18, 3, 21, 3, 24, 3};
const int npoints = sizeof(list1)/sizeof(list1[0]);
cout << endl << "===> Initial list" << endl;
ostream_iterator<int> citer(cout, "\n");
copy(list1, list1 + npoints, citer);
//
// create a new sequence with all elements but 3's from list1. Note
// that we initialize the result container to be as large as the
// original one and use a simple output iterator.
//
cout << endl << "===> Removing all 3's" << endl;
Page : << Previous 6 Next >>