(M)  s i s t e m a   o p e r a c i o n a l   m a g n u x   l i n u x ~/ · documentação · suporte · sobre

  Next Previous Contents

22. STL References

Please visit the following sites for STL -

STL Tutorial:

Ready-made Components for use with the STL

Main STL sites -

22.1 Overview of the STL

The STL offers the programmer a number of useful data structures and algorithms. It is made up the following components.

  • Containers. There are two types:
    • Sequential. This group comprises the vector, list and dequeue types.
    • Sorted Associative. This group comprises the set, map, multiset and multimap types.

  • Iterators. These are pointer like objects that allow the user to step through the contents of a container.

  • Generic Algorithms. The STL provides a wide range of efficently implemented standard algorithms (for example find, sort and merge) that work with the container types. (Some of the containers have special purpose implementations of these algorithms as member functions.)

  • Function Objects. A function object is an instance of a class that provides a definition of operator(). This means that you can use such an object like a function.

  • Adaptors. The STL provides
    • Container adaptors that allow the user to use, say, a vector as the basis of a stack.
    • Function adaptors that allow the user to construct new function objects from existing function objects.

  • Allocators. Every STL container class uses an Allocator class to hold information about the memory model the program is using. I shall totally ignore this aspect of the STL.

I will be considering the use of the vector, list, set and map containers. To make use of these containers you have to be able to use iterators so I shall have something to say about STL iterators. Using the set and map containers can mean having to supply a simple function object to the instantiation so I shall also have something to say about function objects. I will only briefly mention the algorithms supplied by the STL. I will not mention adaptors at all.

I have taken liberties with some of the types of function arguments -- for example most of the integer arguments referred to in what follows actually have type size_type which is typedef'ed to an appropriate basic type depending on the allocation model being used. If you want to see the true signatures of the various functions discussed have a look at the Working Paper or the header files.

There are a number of utility classes supplied with the STL. The only one of importance to us is the pair class. This has the following definition:


template<class T1, class T2>
class pair {
public:
T1 first;
T2 second;
pair(const T1& a, const T2& b) : first(a), second(b) {}

};

and there is a convenient function make_pair with signature:


pair<T1,T2> make_pair(const T1& f, const T2&,s)

as well as implementations of operator== and operator < . There is nothing complicated about this template class and you should be able to use it without further guidance. To use it #include the header file pair.h. It crops up in a number of places but particularly when using the set and map classes.

22.2 Header Files

To use the various bits of the STL you have to #include the appropriate header files. These may differ slightly from compiler to compiler but for g++ the ones of interest are:

  • vector.h for the vector type.
  • list.h for the list type.
  • set.h for the set type.
  • map.h for the map type.
  • algo.h for access to the generic algorithms.

If you don't want to remember which is which you could just use stl.h which includes all the above (and all the other header files of the STL as well).

22.3 The Container Classes Interface

The container classes have many member functions that have the same names. These functions provide the same (or very similar) services for each of the classes (though, of course, the implementations will be different). The following table lists the functions that we shall consider in more detail. A star opposite a function name indicates that the container type heading the column provides a member function of that name.


Operation
Purpose Vector List Set Map
== comparison * ***
< comparison * * * *
begin iterator * * * *
end iterator * * * *
size no. of elements * * * *
empty is container empty * * * *
front first element * *
back last element * *
[ ] element access/modification * *
insert insert element(s) * * * *
push_back insert new last element * *
push_front insert new first element *
erase remove element(s) * * * *
pop_back remove last element * *
pop_front remove last element *
Container Class Interface

If the following discussion leaves something unclear (and it will) you can always write a small test program to investigate how some function or feature behaves.

22.4 Vectors

A vector is an array like container that improves on the C++ array types. In particular it is not neccessary to know how big you want the vector to be when you declare it, you can add new elements to the end of a vector using the push_back function. (In fact the insert function allows you insert new elements at any position of the vector, but this is a very inefficent operation -- if you need to do this often consider using a list instead).

Constructing Vectors

vector is a class template so that when declaring a vector object you have to state the type of the objects the vector is to contain. For example the following code fragment


vector<int> v1;
vector<string> v2;
vector<FiniteAutomaton> v3;

declares that v1 is a vector that holds integers, v2 a vector that holds strings and v3 holds objects of type FiniteAutomaton (presumably an user defined class type). These declarations do not say anything about how large the vectors are to be (implementations will use a default starting size) and you can grow them to as large as you require.

You can give an inital size to a vector by using a declaration like


vector<char> v4(26);

which says that v4 is to be vector of characters that initially has room for 26 characters. There is also a way to initailise a vector's elements. The declaration


vector<float> v5(100,1.0);

says that v5 is a vector of 100 floating point numbers each of which has been initialised to 1.0.

Checking Up on Your Vector

Once you have created a vector you can find out the current number of elements it contains by using the size function. This function takes no arguments and returns an integer (strictly a value of type size_type, but this gets converted to an integer) which says how many elements there are in the vector. What will be printed out by the following small program?


<vector-size.cc>=
#include <iostream.h>
#include <vector.h>

void main()
{
  vector<int> v1;
  vector<int> v2(10);
  vector<int> v3(10,7);

  cout << "v1.size() returns " << v1.size() << endl;
  cout << "v2.size() returns " << v2.size() << endl;
  cout << "v3.size() returns " << v3.size() << endl;
}

To check on wether your vector is empty or not you can use the empty function. This takes no arguments and returns a boolean value, true if the vector is empty, false if it is not empty. What will be printed out by the following small program (true prints as 1 and false prints as 0)?


<vector-empty.cc>=
#include <iostream.h>
#include <vector.h>

void main()
{
  vector<int> v1;
  vector<int> v2(10);
  vector<int> v3(10,7);

  cout << "v1.empty() has value " << v1.empty() << endl;
  cout << "v2.empty() has value " << v2.empty() << endl;
  cout << "v3.empty() has value " << v3.empty() << endl;
}

Accessing Elements of a Vector

You can access a vector's elements using operator[]. Thus, if you wanted to print out all the elements in a vector you could use code like


vector<int> v;
// ...
for (int i=0; i<v.size(); i++)
     cout << v[i];

(which is very similar to what you might write for a builtin array).

You can also use operator[] to set the values of the elements of a vector.


vector<int> v;
// ...
for (int i=0; i<v.size(); i++)
      v[i] = 2*i;

The function front gives access to the first element of the vector.


vector<char> v(10,'a');
// ...
char ch = v.front();

You can also change the first element using front.


vector<char> v(10,'a');
// ...
v.front() = 'b';

The function back works the same as front but for the last element of the vector.


vector<char> v(10,'z');
// ...
char last = v.back();
v.back() = 'a';

Here is a simple example of the use of [].


<vector-access.cc>=
#include <vector.h>
#include <iostream.h>

void main()
{
  vector<int> v1(5);
  int x;
  cout << "Enter 5 integers (seperated by spaces):" << endl;
  for (int i=0; i<5; i++)
    cin >> v1[i];
  cout << "You entered:" << endl;
  for (int i=0; i<5; i++)
    cout << v1[i] << ' ';
  cout << endl;
}

Inserting and Erasing Vector Elements

Along with operator[] as described above there are a number of other ways to change or access the elements in a vector.

  • push_back will add a new element to the end of a vector.
  • pop_back will remove the last element of a vector.
  • insert will insert one or more new elements, at a designated position, in the vector.
  • erase will remove one or more elements from a vector between designated positions.

Note that insert and erase are expensive operations on vectors. If you use them a lot then you should consider using the list data structure for which they are more efficient.


<vector-mod.cc>=
#include <iostream.h>
#include <vector.h>

void main()
{
  vector<int> v;

  for (int i=0; i<10; i++) v.push_back(i);
  cout << "Vector initialised to:" << endl;
  for (int i=0; i<10; i++) cout << v[i] << ' ' ;
  cout << endl;

  for (int i=0; i<3; i++) v.pop_back();
  cout << "Vector length now: " << v.size() << endl;
  cout << "It contains:" << endl;
  for (int i=0; i<v.size(); i++) cout << v[i] << ' ';
  cout << endl;

  int a1[5];
  for (int i=0; i<5; i++) a1[i] = 100;

  v.insert(& v[3], & a1[0],& a1[3]);
  cout << "Vector now contains:" << endl;
  for (int i=0; i<v.size(); i++) cout << v[i] << ' ';
  cout << endl;

  v.erase(& v[4],& v[7]);
  cout << "Vector now contains:" << endl;
  for (int i=0; i<v.size(); i++) cout << v[i] << ' ';
  cout << endl;
}

In the above a vector v has been declared then initialised using push_back. Then some elements have been trimmed off it's end using pop_back. Next an ordinary integer array has been created and then some of its elements inserted into v using insert. Finally erase has been used to remove elements from v. The functions used above take arguments as follows.

  • push_back takes a single argument of the type of the elements held in the vector.
  • pop_back takes no arguments. It is a mistake to use pop_back on an empty vector.
  • insert has three forms:
    • insert(pos, T& x) which will insert the single element x at position pos in the vector.
    • insert(pos, start, end) which inserts a sequence of elements from some other container at position pos in the vector. The
    • sequence of elements is identified as starting at the start element and continuing to, but not including, the end element.
    • insert(pos, int rep, T& x) inserts rep copies of x at position pos in the vector.
As indicated in the code above the position pos should be the address of the element to insert at, whilst the start and end arguments are likewise also addresses. (The true story is that they are iterators -- see next subsection and following section).
  • erase has two forms (pos, start and end have the same types as for the insert function):
    • erase(pos) which will remove the element at position pos in the vector.
    • insert(start,end) which will remove elements starting at postion start upto, but not including, the element at position end.

Vector Iterators

The simple way to step through the elements of a vector v is as we have done above:


for (int i=0; i<v.size(); i++) { ... v[i] ... }

Another way is to use iterators. An iterator can be thought of as a pointer into the container, incrementing the iterator allows you to step through the container. For container types other than vectors iterators are the only way to step through the container.

For a vector containing elements of type T:


vector<T> v;

an iterator is declared as follows:


vector<T>::iterator i;

Such iterators are constructed and returned by the functions begin() and end(). You can compare two iterators (of the same type) using == and !=, increment using ++ and dereference using *. [In fact vector iterators allow more operations on them - see next section for more information].

Here is an illustration of how to use iterators with vectors.


<vector-iterator.cc>=
#include <iostream.h>
#include <vector.h>

void main()
{
  vector<int> v(10);
 first is ``less'' than the second

  int j = 1;

  vector<int>::iterator i;

  // Fill the vector v with integers 1 to 10.
  i = v.begin();
  while (i != v.end())
  {
    *i = j;
    j++;
    i++;
  }

  // Square each element of v.
  for (i=v.begin(); i!=v.end(); i++) *i = (*i) * (*i);

  // Print out the vector v.
  cout << "The vector v contains: ";
  for (i=v.begin(); i!=v.end(); i++) cout << *i << ' ';
  cout << endl;

}

Note how *i can be used on the left-hand side of an assignment statement so as to update the element pointed at by i, and on the right-hand side to access the current value.

Comparing Vectors

You can compare two vectors using == and <. == will return true only if both vectors have the same number of elements and all elements are equal. The < functions performs a lexicographic comparison of the two vectors. This works by comparing the vectors element by element. Suppose we are comparing v1 and v2 (that is v1 < v2?). Set i=0. If v1[i] < v2[i] then return true, if v1[i] > v2[i] then return false, otherwise increment i (that is move on to the next element). If the end of v1 is reached before v2 return true, otherwise return false. Lexicographic order is also known as dictionary order. Some examples:


(1,2,3,4) < (5,6,7,8,9,10) is false.
(1,2,3) < (1,2,3,4) is true
(1,2,3,4) < (1,2,3) is false
(0,1,2,3) < (1,2,3) is true

The following code illustrates the third example above.


<vector-comp.cc>=
#include <vector.h>
#include <iostream.h>

void main()
{
  vector<int> v1;
  vector<int> v2;
  for (int i=0; i<4; i++) v1.push_back(i+1);
  for (int i=0; i<3; i++) v2.push_back(i+1);
  
  cout << "v1: ";
  for (int i=0; i<v1.size(); i++) cout << v1[i] << ' ';
  cout << endl;

  cout << "v2: ";
  for (int i=0; i<v2.size(); i++) cout << v2[i] << ' ';
  cout << endl;

  cout << "v1 < v2 is: " << (v1<v2 ? "true" : "false") << endl;
}

The comparison operators <= and >= also work.

22.5 Iterators and the STL

See the section STL References

22.6 Lists

See the section STL References

22.7 Sets

The set container type allows an user to store and retrieve elements directly rather than through an index into the container. The set container acts as a mathematical set in that it holds only distinct elements. However unlike a mathematical set, elements in a set container are held in (an user-supplied) order. In practise this is only a minor restriction on treating a set container as an implementation of the mathematical set abstract data type, and it allows for a much more efficent implementation than an unordered approach.

Constructing Sets

Two template arguments are required to construct a set container -- the type of the objects the set is to contain and a function object that can compare two elements of the given type, that is:


set<T, Compare> s;

(The declaration set < T > s should also be possible -- it would use a default template argument less < T > as the second argument, but many C++ compilers (including g++) cannot as yet cope with default template arguments.)

For simple types T we can use the function object less < T > ( without having to worry about what a ``function object'' is), for example all the following are legal set declarations.


set<int, less<int> > s1;
set<double, less<double> > s2;
set<char, less<char> > s3;
set<string, less<string> > s4;

(Note that the space between the two final >'s in the template is required - otherwise the compiler will interpret >> as the right shift operator.) In each of these cases the function object makes use of the operator < as defined for the the underlying type (that is int, double, char and string).

The following code declares a set of integers, then adds some integers to the set using the insert method and then prints out the set members by iterating through the set. You will note that the set's contents are printed out in ascending order even though they were added in no particular order.


<set-construct1.cc>=
#include <iostream.h>
#include <set.h>

void main()
{
  set<int, less<int> > s;
  set<int, less<int> >::iterator i;

  s.insert(4);
  s.insert(0);
  s.insert(-9);
  s.insert(7);
  s.insert(-2);
  s.insert(4);
  s.insert(2);

  cout << The set contains the elements: ;
  for (i=s.begin(); i!=s.end(); i++) cout << *i << ' ';
  cout << endl;
}

Note that 4 is added twice but only turns up once on the list of elements -- which is what one expects of a set.

What are Function Objects?

One of the nifty features of C++ is the ability to overload operators, so that one can have + mean whatever one likes for your newly designed class. One of the operators C++ allows you to overload is the function call operator () and this allows you to create classes whose instances can behave like functions in many ways. These are function objects.

Here is a simple example.


<function-object.cc>=
#include <iostream.h>

template<class T>
class square {
public:
  T operator()(T x) { return x*x; }
};
// This can be used with any T for which * is defined.

void main()
{
  // Create some function objects.
  square<double> f1;
  square<int> f2;

  // Use them.
  cout << 5.1^2 =  << f1(5.1) << endl;
  cout << 100^2 =  << f2(100) << endl;

  // The following would result in a compile time error.
  // cout << 100.1^2 =  << f2(100.1) << endl;

}

Function objects are used in a number of places in the STL. In particular they are used when declaring sets and maps.

The function object required for these purposes, let's suppose it is called comp, must satisfy the following 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 < ) on numbers. The function object less < T > used above is defined in terms of a < operator for the type T. It's definition can be thought of as follows.


template<class T>
struct less {
  bool operator()(T x, T y) { return x<y; }
}

(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 < defined for it then you can use less < T > as the comparator when declaring sets of T. You might still want to use a special purpose comparator if the supplied < operator is not appropriate for your purposes. Here is another example. This defines a simple class with a definition of operator < and a function object that performs a different comparison. Note that the overloaded < and () operators should be given const annotations so that the functions work correctly with the STL.


<set-construct2.cc>=
#include <iostream.h>
#include <set.h>

// This class has two data members. The overloaded operator< compares
// 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<(myClass y) const
        { return (f1<y.field1()); }
};

// 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() < c2.field2()); }
};

void main()
{
  set<myClass, less<myClass> > s1;
  set<myClass, less<myClass> >::iterator i;
  set<myClass, comp_myClass> s2;
  set<myClass, comp_myClass>::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 << Set s1 contains: ;
  for (i=s1.begin(); i!=s1.end(); i++)
    { cout << ( << (*i).field1() << , 
                  << (*i).field2() << ) << ' ';
    }
  cout << endl;

  cout << Set s2 contains: ;
  for (j=s2.begin(); j!=s2.end(); j++)
    { cout << ( << (*j).field1() << , 
                  << (*j).field2() << ) << ' ';
    }
  cout << endl;

}

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<< has been written. It works fine for small sets with simple element types.


<printset.h>=
#ifndef _PRINTSET_H
#define _PRINTSET_H

#include <iostream.h>
#include <set.h>

template<class T, class Comp>
ostream& operator<<(ostream& os, const set<T,Comp>& s)
{
  set<T,Comp>::iterator iter = s.begin();
  int sz = s.size();
  int cnt = 0;

  os << {;
  while (cnt < sz-1)
    {
      os << *iter << ,;
      iter++;
      cnt++;
    }
  if (sz != 0) os << *iter;
  os << };

  return os;
}
#endif

The use here of << as an output routine for a set assumes that << has been defined for the set elements, and 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.

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.


<set-size.cc>=
#include <iostream.h>
#include <set.h>
#include printset.h

void main()
{
  set<int, less<int> > s;

  cout << The set s is  
       << (s.empty() ? empty. : non-empty.) << endl; 
  cout << It has  << s.size() <<  elements. << endl;

  cout << Now adding some elements... << endl;

  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 << The set s is now  
       << (s.empty() ? empty. : non-empty.) << endl;
  cout << It has  << s.size() <<  elements. << endl;
  cout << s =  << s << endl;
}

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==.


<set-equality.cc>=
#include <iostream.h>
#include <set.h>
#include printset.h

void main()
{
  set<int, less<int> > s1, s2 ,s3;
  
  for (int i=0; i<10; i++)
  {
    s1.insert(i);
    s2.insert(2*i);
    s3.insert(i);
  }

  cout << s1 =  << s1 << endl;
  cout << s2 =  << s2 << endl;
  cout << s3 =  << s3 << endl;
  cout << s1==s2 is:  << (s1==s2 ? true. : false.) << endl;
  cout << s1==s3 is:  << (s1==s3 ? true. : false.) << endl;
}

It is also possible to compare two sets using <. The comparison s1 < s2 is true if the set s1 is 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 < iterator, bool> 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.


<set-add-delete.cc>=
#include <iostream.h>
#include <set.h>
#include printset.h

void main()
{
  set<int, less<int> > s1;

  // Insert elements in the standard fashion.
  s1.insert(1);
  s1.insert(2);
  s1.insert(-2);

  // Insert elements at particular positions.
  s1.insert(s1.end(), 3);
  s1.insert(s1.begin(), -3);
  s1.insert((s1.begin()++)++, 0);

  cout << s1 =  << s1 << endl;

  // Check to see if an insertion has been successful.
  pair<set<int, less<int> >::iterator,bool> x = s1.insert(4);
  cout << Insertion of 4  << (x.second ? worked. : failed.) 
       <<  endl;
  x = s1.insert(0);
  cout << Insertion of 0  << (x.second ? worked. : failed.) 
       <<  endl;

  // The iterator returned by insert can be used as the position
  // component of the second form of insert.
  cout << Inserting 10, 8 and 7. << endl;
  s1.insert(10);
  x=s1.insert(7);
  s1.insert(x.first, 8);
  
  cout << s1 =  << s1 << endl;

  // Attempt to remove some elements.
  cout << Removal of 0  << (s1.erase(0) ? worked. : failed.)
       << endl;
  cout << Removal of 5  << (s1.erase(5) ? worked. : failed.)
       << endl;

  // Locate an element, then remove it. (See below for find.)
  cout << Searching for 7. << endl;
  set<int,less<int> >::iterator e = s1.find(7);
  cout << Removing 7. << endl;
  s1.erase(e);

  cout << s1 =  << s1 << endl;

  // Finally erase everything from the set.
  cout << Removing all elements from s1. << endl;
  s1.erase(s1.begin(), s1.end());
  cout << s1 =  << s1 << endl;
  cout << s1 is now  << (s1.empty() ? empty. : non-empty.)
       << endl;
}

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.)

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.)


<setmember.h>=
#ifndef _SETMEMBER_H
#define _SETMEMBER_H
#include <set.h>

template<class T, class Comp>
bool member(T x, set<T,Comp>& s)
{
 return (s.count(x)==1 ? true : false);
}
#endif

Which might be used as follows. 

<set-membership.cc>=
#include <iostream.h>
#include <set.h>
#include printset.h
#include setmember.h

void main()
{
  set<int, less<int> > s;
  for (int i= 0; i<10; i++) s.insert(i);
  cout << s =  << s << endl;
  cout << 1 is  << (member(1,s) ?  : not) <<  a member of s 
       <<  endl;
  cout << 10 is  << (member(10,s) ?  : not) <<  a member of s 
       <<  endl;
}

Set Theoretic Operations

The STL supplies as generic algorithms the set operations includes, union, intersection, difference and symmetric diffference. To gain access to these functions you need to include algo.h. (In what follows iter stands for an appropriate iterator).

  • bool includes(iter f1,iter l1,iter f2,iter l2).

    This checks to see if the set represented by the range [f2,l2] is included in the set [f1,l1]. It returns true if it is and false otherwise. So to check to see if one set is included in another you would use

    includes(s1.begin(), s1.end(), s2.begin(), s2.end())

    The includes function checks the truth of 3#3 ( that is of 4#4). This function assumes that the sets are ordered using the comparison operator <. If some other comparison operator has been used this needs to be passed to includes as an extra (function object) argument after the other arguments.

  • iter set_union(iter f1,iter l1,iter f2,iter l2,iter result).

    This forms the union of the sets represented by the ranges [f1,l1] and [f2,l2]. The argument result is an output iterator that points at the start of the set that is going to hold the union. The return value of the function is an output iterator that points at the end of the new set.

The fact that the result argument is an output iterator means that you cannot use set_union in the following, natural, fashion:


      set<int, less<int> > s1, s2, s3;
      // Add some elements to s1 and s2 ...
      // Then form their union. (This does not work!)
      set_union(s1.begin(), s1.end(), 
                s2.begin(), s2.end(), 
                s3.begin());

The reason is that begin() (also end()) when used with sets (or maps) returns a (constant) input iterator. This type of iterator allows you to access elements of the set for reading but not writing. (And this is a Good Thing since if you could assign to a dereferenced iterator (as in (*i)= ...) then you could destroy the underlying order of the set.)

The solution is to use an insert iterator based on the set type. This, basically, converts an assignment (*i)=value (which is illegal) into a (legal) insertion s.insert(i,value) (where s is the set object that the iterator i is pointing into). It is used as follows:


      // Typedef for convenience.
      typedef set<int, less<int> > intSet;  
      intSet s1, s2, s3;
      // Add some elements to s1 and s2 ...
      // Then form their union. 
      set_union(s1.begin(), s1.end(), 
                s2.begin(), s2.end(), 
                insert_iterator<intSet>(s3,s3.begin()) );

Here is an example illustrating all these operations.


<set-theory.cc>=
#include <iostream.h>
#include <set.h>
#include <algo.h>
#include <iterator.h>
#include printset.h

void main()
{
  typedef set<int, less<int> > intSet;

  intSet s1, s2, s3, s4;

  for (int i=0; i<10; i++)
  { s1.insert(i);
    s2.insert(i+4);
  }
  for (int i=0; i<5; i++) s3.insert(i);

  cout << s1 =  << s1 << endl;
  cout << s2 =  << s2 << endl;
  cout << s3 =  << s3 << endl;

  // Is s1 a subset of s2?
  bool test = includes(s2.begin(),s2.end(),s1.begin(),s1.end());
  cout << s1 subset of s2 is  << (test ? true. : false.) << endl;

  // Is s3 a subset of s1?
  test = includes(s1.begin(),s1.end(),s3.begin(),s3.end());
  cout << s3 subset of s1 is  << (test ? true. : false.) << endl;
  
  // Form the union of s1 and s2.
  set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
                   insert_iterator<intSet>(s4,s4.begin()) );
  cout << s1 union s2 =  << s4 << endl;

  // Erase s4 and form intersection of s1 and s2. (If we don't erase
  // s4 then we will get the previous contents of s4 as well).
  s4.erase(s4.begin(),s4.end());
  set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
                   insert_iterator<intSet>(s4,s4.begin()) );
  cout << s1 intersection s2 =  << s4 << endl;

  // Now set difference.
  s4.erase(s4.begin(),s4.end());
  set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
                   insert_iterator<intSet>(s4,s4.begin()) );
  cout << s1 minus s2 =  << s4 << endl;

  // Set difference is not symmetric.
  s4.erase(s4.begin(),s4.end());
  set_difference(s2.begin(), s2.end(), s1.begin(), s1.end(),
                   insert_iterator<intSet>(s4,s4.begin()) );
  cout << s2 minus s1 =  << s4 << endl;

  // Finally symmetric difference.
  s4.erase(s4.begin(),s4.end());
  set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
                   insert_iterator<intSet>(s4,s4.begin()) );
  cout << s1 symmetric_difference  s2 =  << s4 << endl;

  // Which is symmetric!
  s4.erase(s4.begin(),s4.end());
  set_symmetric_difference(s2.begin(), s2.end(), s1.begin(), s1.end(),
                   insert_iterator<intSet>(s4,s4.begin()) );
  cout << s2 symmetric_difference  s1 =  << s4 << endl;
}

22.8 Maps

See the section STL References

22.9 STL Algorithms

See the section STL References


Next Previous Contents