[ Pobierz całość w formacie PDF ]

requirements.
1. If comp(x,y) and comp(y,z) are true for objects x, y and z then comp(x,z) is also true.
2. comp(x,x) is false for every object x.
If for any particular objects x and y, both comp(x,y) and comp(y,x) are false then x and y are deemed to be
equal.
This, in fact, is just the behaviour of the strictly-less-than relation (ie
less used above is defined in terms of a
follows.
template
struct less {
What are Function Objects? 40
 C++ Programming HOW-TO
bool operator()(T x, T y) { return x
}
(The actual definition uses references, has appropriate const annotations and inherits from a template class
binary_function.)
This means that if the type T has operator
declaring sets of T. You might still want to use a special purpose comparator if the supplied
appropriate for your purposes. Here is another example. This defines a simple class with a definition of
operator
operators should be given const annotations so that the functions work correctly with the STL.
=
#include
#include
// This class has two data members. The overloaded operator
// such classes on the basis of the member f1.
class myClass {
private:
int f1;
char f2;
public:
myClass(int a, char b) : f1(a), f2(b) {}
int field1() const { return f1; }
char field2() const { return f2; }
bool operator
{ return (f1
};
// This function object compares objects of type myClass on the basis
// of the data member f2.
class comp_myClass {
public:
bool operator()(myClass c1, myClass c2) const
{ return (c1.field2()
};
void main()
{
set s1;
set::iterator i;
set s2;
set::iterator j;
s1.insert(myClass(1,'a'));
s2.insert(myClass(1,'a'));
s1.insert(myClass(1,'b'));
s2.insert(myClass(1,'b'));
s1.insert(myClass(2,'a'));
s2.insert(myClass(2,'a'));
cout
for (i=s1.begin(); i!=s1.end(); i++)
{ cout
}
What are Function Objects? 41
 C++ Programming HOW-TO
cout
cout
for (j=s2.begin(); j!=s2.end(); j++)
{ cout
}
cout
}
The set s1 contains (1,a) and (2,a) as comparison is on the data member f1, so that (1,a) and (1,b) are deemed
the same element. The set s2 contains (1,a) and (1,b) as comparison is on the data member f2, so that (1,a)
and (2,a) are deemed the same element.
A Printing Utility
The way we have printed out the sets in the previous examples is a little awkward so the following header file
containing a simple overloaded version of operator
simple element types.
=
#ifndef _PRINTSET_H
#define _PRINTSET_H
#include
#include
template
ostream& operator
{
set::iterator iter = s.begin();
int sz = s.size();
int cnt = 0;
os
while (cnt
{
os
iter++;
cnt++;
}
if (sz != 0) os
os
return os;
}
#endif
The use here of
uses this to print a comma delimited list of the set elements wrapped in curly braces. It will be used without
comment in the following examples.
A Printing Utility 42
 C++ Programming HOW-TO
How Many Elements?
You can determine if a set is empty or not by using the empty() method. You can find out how many
elements there are in a set by using the size() method. These methods take no arguments, empty() returns true
or false and size() returns an integer.
=
#include
#include
#include printset.h
void main()
{
set s;
cout
cout
cout
s.insert(1);
s.insert(6);
s.insert(7);
s.insert(-7);
s.insert(5);
s.insert(2);
s.insert(1);
s.insert(6);
cout
cout
cout
}
Checking the Equality of Sets.
Two sets may be checked for equality by using ==. This equality test works by testing in order the
corresponding elements of each set for equality using T::operator==.
=
#include
#include
#include printset.h
void main()
{
set s1, s2 ,s3;
for (int i=0; i
{
s1.insert(i);
s2.insert(2*i);
s3.insert(i);
How Many Elements? 43
 C++ Programming HOW-TO
}
cout
cout
cout
cout
cout
}
It is also possible to compare two sets using
lexicographically less than the set s2, otherwise it is false.
Adding and Deleting Elements
The way to add elements to a set is to use the insert method (as we have done above). The way to delete
elements from a set is to use the erase method.
For a set holding elements of type T these methods come in following forms:
" pair insert(T& x). This is the standard insert function. The return value may be
ignored or used to test if the insertion succeeded (that is the element was not already in the set). If the
insertion succeeded the boolean component will be true and the iterator will point at the just inserted
element. If the element is already present the boolean component will be false and the iterator will
point at the element x already present.
" iterator insert(iterator position, T& x). This version of the insert function takes, in addition to the
element to insert, an iterator stating where the insert function should begin to search. The returned
iterator points at the newly inserted element, (or the already present element).
" int erase(T& x). This version of the erase method takes an element to delete and returns 1 if the
element was present (and removes it) or 0 if the element was not present.
" void erase(iterator position). This version takes an iterator pointing at some element in the set and
removes that element.
" void erase(iterator first, iterator last). This verion takes two iterators pointing into the set and
removes all the elements in the range [ first,last ] .
The following example illustrates these various forms.
=
#include
#include
#include printset.h
void main()
{
set s1;
// Insert elements in the standard fashion.
s1.insert(1);
s1.insert(2);
Adding and Deleting Elements 44
 C++ Programming HOW-TO
s1.insert(-2);
// Insert elements at particular positions.
s1.insert(s1.end(), 3);
s1.insert(s1.begin(), -3);
s1.insert((s1.begin()++)++, 0);
cout
// Check to see if an insertion has been successful.
pair x = s1.insert(4);
cout
x = s1.insert(0);
cout
// The iterator returned by insert can be used as the position
// component of the second form of insert.
cout
s1.insert(10);
x=s1.insert(7);
s1.insert(x.first, 8);
cout
// Attempt to remove some elements.
cout
cout
// Locate an element, then remove it. (See below for find.)
cout
set::iterator e = s1.find(7);
cout
s1.erase(e);
cout
// Finally erase everything from the set.
cout
s1.erase(s1.begin(), s1.end());
cout
cout
}
Finding Elements
We mention two member functions that can be used to test if an element is present in a set or not.
" iterator find(T& x). This searches for the element x in the set. If x is found it returns an iterator
pointing at x otherwise it returns end().
" int count(T& x). This returns 1 if it finds x in the set and 0 otherwise. (The count function for
multisets returns the number of copies of the element in the set which may be more than 1. Hence, I
guess, the name of the function.)
Finding Elements 45
 C++ Programming HOW-TO
The use of find has been illustrated above. We could use count to write a simple template based set
membership function. (This should also provide a version that takes a reference to the argument x.)
=
#ifndef _SETMEMBER_H
#define _SETMEMBER_H
#include
template
bool member(T x, set& s)
{
return (s.count(x)==1 ? true : false);
}
#endif
Which might be used as follows.
=
#include
#include
#include printset.h
#include setmember.h
void main()
{
set s;
for (int i= 0; i
cout
cout
cout
}
Set Theoretic Operations [ Pobierz całość w formacie PDF ]