Author : Mumit Khan
Page : << Previous 5 Next >>
strcpy(buf, "grumpy");
phbook[(char*)buf] = 7621212;
cerr << "==> Grumpy moved again! latest number 7621212" << endl;
print_phbook(cerr, phbook);
cerr << endl;
return 0;
}
And here's the output (might even dump core with some STL implementations):
==> Initial phone book
(grumpy 5551212)
(sleepy 5552121)
(gandhi 5554242)
==> Grumpy moved. The new number is 9995152
(grumpy 5551212)
(sleepy 5552121)
(gandhi 5554242)
( 9995152)
==> Grumpy moved again! latest number 7621212
(grumpy 5551212)
(sleepy 5552121)
(gandhi 5554242)
( 9995152)
(grumpy 7621212)
Hmmm... two grumpy's and a number without a name!
Predicates, Comparators and General Functions
STL containers and algorithms make heavy use of function objects that are either provided by STL (eg., less<T>) or by the user. These function objects typically fall in 3 different categories:
Predicates: boolean function. Especially useful for algorithms that end in _if, such as count_if, find_if, replace_if, etc.
Comparator: boolean function. Useful for ordered containers, such as map<T>, priority_queue<T>, etc.
General functions: functions that operate on objects, but do not necessarily return a value, and if they do, it could be anything.
Predicates: what and how
Jim Jackl-Mochel <JimJM@smtp-gateway2.silverplatter.com> sent me the following note on using the find algorithm:
First off. thank you for maintaining such a useful page on STL. It has
filled the documentation gap for me twice when I could'nt figure out
the Modena manual !
A question that I cannot get a handle on yet is how to search for
element in a list without passing the full element in..
Example: If I have a list or vector of regions which contain a pointer
to a buffer.
vector<Region>
and Region has a method for determining whether or not it contains a
specific pointer in memory.
bool Region::Contains(Byte* Bfr)
What I thought I should be able to do is use
Region = find(List.begin(), List.end(), Byte* BfrToBeSearchedFor);
or something like it.
But STL (in my probably limited understanding) seems to require that I
use
Region = find(List.begin(), List.end(), RegionToBeSearchedFor);
or
Region = find(List.begin(), List.end(), ComparisonFunction);
Neither of which appears to answer my needs.
If you have any suggestions on how this would be tackled please put
them in your Newbie guide. If not I will try posting to comp.lang.c++.
Thank you again.
Jim Jackl-Mochel
The first thing to note is that the appropriate algorithm to use is find_if, not find; now, we also need to supply a predicate (has_buffer shown below) that will do the right thing. The following solution works in this case:
class Region {
public:
// ...
bool Contains(Byte* Bfr) const;
private:
// ...
};
list<Region> regions;
//
// populate regions with all the Region objects containing unique
// Byte* elements, one of which may contain the Byte* you're looking
// for.
//
Byte* BfrToBeSearchedFor = INITIALIZE_BUFFER_POINTER;
//
// find the region which contains the given buffer pointer bufferp;
//
// first, let's define the appropriate comparator fct.
//
struct has_buffer {
Byte* buffer_;
has_buffer(const Byte* buffer) : buffer_(buffer) { }
bool operator()(const Region& region) const {
return region.Contains(buffer_);
}
};
list<Region>::const_iterator it = find_if(regions.begin(),
regions.end(), has_buffer(BfrToBeSearchedFor)
);
if (it == regions.end()) {
// not found
} else {
// found it
const Byte* Bfr = *it;
// ...
}
Notice the use of find_if, which takes a predicate that you can supply to find the element.
Comparators: what and how
Comparators are typically used for sorting/ordering container objects such as the one used by the sort algorithm. More often than not, the STL provided comparators (eg., less<T>, greater<T>, etc), which in turn invoke the < operator, are sufficient; there are cases, however, where you need to supply custom comparators to get the job done. Let's take the following example:
deque<int*> deque1;
//
// populate deque1
//
//
// now sort. (THIS IS INCORRECT)
//
sort(deque1.begin(), dequeu1.end());
In the code sample above, the sort algorithm will use the default less<int*> function object to do the ordering and the result is obviously not the guranteed to be correct. There are two different approaches we can take -- define a set of comparator functions that work on pointers by dereferencing the arguments first (ala ObjectSpace STL<ToolKit>), define a "dereferencing" function object that works on unary and binary functions.
The following example shows how to do a custom pointer comparator.
bool intp_less(const int* i1, const int* i2) {
return *i1 < *i2;
}
sort(deque1.begin(), dequeu1.end(), intp_less);
Or, we can use a bit more structured method:
template <class BinaryFunction>
class binary_dereference : binary_function<
BinaryFunction::first_argument_type,
BinaryFunction::second_argument_type,
BinaryFunction::result_type>
{
public:
binary_dereference(
const BinaryFunction& func = BinaryFunction()
) : func_(func) { }
BinaryFunction::result_type operator() (
BinaryFunction::first_argument_type* const& x,
BinaryFunction::second_argument_type* const& y
) const {
return func_(*x, *y);
}
protected:
BinaryFunction func_;
};
template <class BinaryFunction>
inline binary_dereference<BinaryFunction>
dereference2 (const BinaryFunction& func)
{
return binary_dereference<BinaryFunction>(func);
}
//
// populate deque<int*>
//
deque<int*> deque1;
//
// now we sort ...
//
sort(
deque1.begin(), deque1.end(),
binary_dereference<less<int> > (less<int>())
);
//
// or use the adapter
//
sort(
deque1.begin(), deque1.end(),
dereference2 (less<int> ())
);
To use a set, you could always do the following:
typedef binary_dereference<less<int> > ip_compare;
typedef set<int*, ip_compare> ip_set;
Or, the following is even more structured:
template <class BinaryFunction, class Modifier>
class binary_arg_modifier : binary_function<
Modifier::argument_type,
Modifier::argument_type,
BinaryFunction::result_type>
{
public:
binary_arg_modifier(
const BinaryFunction& func = BinaryFunction(),
const Modifier& modifier = Modifier()
) : func_(func), modifier_(modifier) { }
BinaryFunction::result_type operator() (
const Modifier::argument_type& x,
const Modifier::argument_type& y
) const {
return func_(modifier_(x), modifier_(y));
}
protected:
BinaryFunction func_;
Modifier modifier_;
};
template <class BinaryFunction, class Modifier>
inline binary_arg_modifier<BinaryFunction, Modifier>
arg_modifier2 (const BinaryFunction& func, const Modifier& modifier)
{
return binary_arg_modifier<BinaryFunction, Modifier>(func, modifier);
}
template <class T>
struct dereference : unary_function<T*, T> {
T operator() (const T* x) const { return *x; }
};
//
// populate deque<int*>
//
deque<int*> deque1;
//
// now we sort ...
//
sort(
deque1.begin(), deque1.end(),
binary_arg_modifier< less<int>, dereference<int> > ()
);
//
// or use the adapter
//
sort(
deque1.begin(), deque1.end(),
arg_modifier2 (less<int> (), dereference<int> ())
);
You can of course use for set, map, etc as well.
typedef binary_arg_modifier< less<int>, dereference<int> > ip_compare;
typedef set<int*, ip_compare> ip_set;
ip_set set1;
General Functions: what and how
General functions are useful when you want to operate on each of the objects in a container in sequence, for example using
Page : << Previous 5 Next >>