Compaq C++ User Documentation

| United States

cxxlstd$help.HLP

##

##

##

##

##

##

##

##

##

##

##

##

##

    Associative Containers
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      Associative_Containers  - Associative	containers are ordered
      containers.  These containers provide member functions that allow
      the efficient insertion, retrieval and manipulation of keys.   The
      standard library provides the map, multimap, set and multiset
      associative containers. map and multimap associate values with the
      keys and allow for fast retrieval of the value, based upon fast
      retrieval of the key.	set and	multiset store only keys, allowing
      fast retrieval of the key itself.

    SEE ALSO

      For more information about associative containers, see the
      Containers section of this reference guide, or see the section on
      the specific container.

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

    Bitset
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      bitset  - A template class and related functions for storing and
      manipulating fixed-size sequences of bits.

    SYNOPSIS

      #include <bitset>

      template <size_t N>
      class	bitset ;

    DESCRIPTION

      bitset<size_t	N> is a	class that describes objects that can
      store a sequence consisting of a fixed number	of bits, N. Each
      bit represents either the value zero	(reset)	or one (set) and
      has a non-negative position pos.

      ERRORS AND EXCEPTIONS

      Bitset constructors and member functions may report the following
      three types of errors -- each associated with a distinct exception:

      +	  invalid-argument error or invalid_argument() exception;

      +	  out-of-range error or	out_of_range() exception;

      +	  overflow error or over-flow_error() exception;

      If exceptions	are not	supported on your compiler, you	will get an
      assertion failure instead of an exception.

    INTERFACE

      template <size_t N>
      class	bitset {

      public:

      // bit reference:

       class reference {
        friend class bitset<N>;
       public:

         ~reference();
        reference& operator= (bool);
        reference& operator= (const	reference&);
        bool operator~() const;
        operator bool() const;
        reference& flip();
        };

      // Constructors
       bitset ();
       bitset (unsigned long);
       explicit bitset (const string&, size_t = 0,
    		    size_t = (size_t)-1);
       bitset (const bitset<N>&);
       bitset<N>& operator=	(const bitset<N>&);

      // Bitwise Operators and Bitwise Operator Assignment
        bitset<N>& operator&= (const bitset<N>&);
        bitset<N>& operator|= (const bitset<N>&);
        bitset<N>& operator^= (const bitset<N>&);
        bitset<N>& operator<<= (size_t);
        bitset<N>& operator>>= (size_t);

      // Set, Reset, Flip
        bitset<N>& set ();
        bitset<N>& set (size_t, int	= 1);
        bitset<N>& reset ();
        bitset<N>& reset (size_t);
        bitset<N> operator~() const;
        bitset<N>& flip ();
        bitset<N>& flip (size_t);

      // element access
        reference operator[] (size_t);
        unsigned long to_ulong() const;
        string to_string() const;
        size_t count() const;
        size_t size() const;
        bool operator== (const bitset<N>&) const;
        bool operator!= (const bitset<N>&) const;
        bool test (size_t) const;
        bool any() const;
        bool none()	const;
        bitset<N> operator<< (size_t) const;
        bitset<N> operator>> (size_t) const;

      };

      // Non-member	operators
      template <size_t N>
      bitset<N> operator& (const bitset<N>&, const bitset<N>&);

      template <size_t N>
      bitset<N> operator| (const bitset<N>&, const bitset<N>&);

      template <size_t N>
      bitset<N> operator^ (const bitset<N>&, const bitset<N>&);

      template <size_t N>
      istream& operator>> (istream&, bitset<N>&);

      template <size_t N>
      ostream& operator<< (ostream&, const bitset<N>&);

    CONSTRUCTORS

      bitset();
         Constructs	an object of class bitset<N>, initializing all bit
         values to zero.

      bitset(unsigned long val);
         Constructs	an object of class bitset<N>, initializing the first M
         bit values to the corresponding bits in val. M is the smaller  of
         N and the value CHAR_BIT * sizeof(unsigned  long).  If M < N,
         remaining bit positions are initialized to zero.  Note:  CHAR_BIT
         is defined in <climits>.

      explicit
      bitset(const string& str, size_t pos = 0,
    	size_t n = (size_t)-1);
         Determines the effective length rlen	of the	initializing
         string as the smaller of n and str.size() -	pos. The
         function  throws an invalid_argument exception if any of the rlen
         characters in str, beginning at position pos,is other than 0  or
         1. Otherwise, the function  constructs an object of class
         bitset<N>, initializing the first M bit positions to	values
         determined from the corresponding characters in the string  str.
         M is the smaller of N and rlen.  This constructor  requires that
         pos <= str.size(), otherwise it throws an  out_of_range
         exception.

      bitset(const bitset<N>& rhs);
         Copy constructor.	Creates	a copy of rhs.

    ASSIGNMENT OPERATOR

      bitset<N>&
      operator=(const bitset<N>& rhs);
         Erases all	bits in	self, then inserts into	self a copy of each
         bit in rhs.  Returns a reference to *this.

    OPERATORS

      bool
      operator==(const bitset<N>& rhs) const;
         Returns true if the value of each bit in *this equals the value
         of	each corresponding bit in rhs.	Otherwise returns false.

      bool
      operator!=(const bitset<N>& rhs) const;
         Returns true if the value of any bit in *this is not equal	to
         the value of the corresponding bit in rhs. Otherwise returns
         false.

      bitset<N>&
      operator&=(const bitset<N>& rhs);
         Clears each bit in	*this for which	the corresponding bit in rhs
         is	clear and leaves	all other bits unchanged. Returns *this.

      bitset<N>&
      operator|=(const bitset<N>& rhs);
         Sets each bit in *this for	which the corresponding	bit in rhs
         is set, and leaves	all other bits unchanged. Returns *this.

      bitset<N>&
      operator^=(const bitset<N>& rhs);
         Toggles each bit in *this for which the corresponding bit in
         rhs is set, and leaves all other bits unchanged. Returns *this.

      bitset<N>&
      operator<<=(size_t pos);
         Replaces each bit at position I with 0 if	I < pos	or with	the
         value of the bit at	I - pos	if I >=	pos. Returns *this.

      bitset<N>&
      operator>>=(size_t pos);
         Replaces each bit at position I with 0 if pos >= N-I or with
         the value of the bit at position I + pos if pos < N-I. Returns
         * this.

      bitset<N>&
      operator>>(size_t pos) const;
         Returns bitset<N>(*this) >>= pos.

      bitset<N>&
      operator<<(size_t pos) const;
         Returns bitset<N>(*this) <<= pos.

      bitset<N>
      operator~() const;
         Returns the bitset	that is	the logical complement of each bit
         in *this.

      bitset<N>
      operator&(const bitset<N>& lhs,
    	   const bitset<N>& rhs);
    	      lhs gets logical AND of lhs with rhs.

      bitset<N>
      operator|(const bitset<N>& lhs,
    	   const bitset<N>& rhs);
    	      lhs gets logical OR of lhs with rhs.

      bitset<N>
      operator^(const bitset<N>& lhs,
    	   const bitset<N>& rhs);
    	      lhs gets logical XOR of lhs with rhs.

      template <size_t N>
      istream&
      operator>>(istream& is, bitset<N>& x);
         Extracts up to N characters (single-byte) from is.	 Stores
         these characters in a temporary object str of type string, then
         evaluates the expression x = bitset<N>(str).  Characters are
         extracted and stored until any of the following occurs:

    	  - N characters have been extracted and stored
              - An end-of-file occurs on the input sequence
              - The next character is neither '0' nor '1'.  In this case,
                the character is not extracted.

         Returns is.

      template <size_t N>
      ostream&
      operator<<(ostream& os, const	bitset<N>& x);
         Returns os	<< x.to_string()

    MEMBER FUNCTIONS

      bool
      any()	const;
         Returns true if any bit in	*this is  set.	Otherwise returns
         false.

      size_t
      count() const;
         Returns a count of	the number of bits set in *this.

      bitset<N>&
      flip();
         Flips all bits in *this, and returns *this.

      bitset<N>&
      flip(size_t pos);
         Flips the bit at position pos in *this and	returns	*this. Throws
         an out_of_range exception if pos does not correspond to a valid
         bit position.

      bool
      none() const;
         Returns true if no	bit in *this is	set.   Otherwise returns false.

      bitset<N>&
      reset();
         Resets all	bits in	*this, and returns *this.

      bitset<N>&
      reset(size_t pos);
         Resets the	bit at position	pos in *this. Throws an	out_of_range
         exception if pos does not correspond to a valid bit position.

      bitset<N>&
      set();
         Sets all bits in *this, and returns *this.

      bitset<N>&
      set(size_t pos, int val = 1);
         Stores a new value	in the bits at position	pos in *this.  If
         val is nonzero, the stored value is one, otherwise it is zero.
         Throws an out_of_range exception if pos does not correspond to a
         valid bit position.

      size_t
      size() const;
         Returns the template parameter N.

      bool
      test(size_t pos) const;
         Returns true if the bit at	position pos is	set.  Throws an
         out_of_range exception if pos does not correspond to a valid
         bit position.

      string
      to_string() const;
         Returns an	object of type string, N characters long.

         Each position in the new string is	initialized with a character
         ('0' for zero and '1' for  one) representing the value stored in
         the corresponding bit position of *this. Character position N-1
         corresponds to bit position 0.  Subsequent decreasing character
         positions correspond to increasing	bit positions.

      unsigned long
      to_ulong() const;
         Returns the integral value	corresponding to the bits in *this.
         Throws an overflow_error if these bits cannot be represented
         as type unsigned long.

    SEE ALSO

      Containers

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

    deque
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      deque	 - A sequence that supports random access iterators and
      efficient insertion/deletion at both beginning and end.

    SYNOPSIS

      #include <deque>

      template <class T, class Allocator = allocator<T> >
      class	deque;

    DESCRIPTION

      deque<T, Allocator> is a type	of sequence that supports random
      access iterators.  It supports constant time	insert and erase
      operations at the beginning or the end of the container. Insertion
      and erase in	the middle take linear time.  Storage management
      is handled by the Allocator template parameter.

      Any type used	for the	template parameter T must provide the following
      (where T is the type,	t is a value of	T and u	is a const value of T):

      Default constructor	T()

      Copy constructors    T(t) and	T(u)

      Destructor   t.~T()

      Address of   &t and &u yielding T* and const T* respectively

      Assignment   t = a where a is	a (possibly const) value of T

    INTERFACE

      template <class T, class Allocator = allocator<T> >
      class	deque {

      public:

       // Types

        class iterator;
        class const_iterator;
        typedef T value_type;
        typedef Allocator allocator_type;
        typename  reference;
        typename  const_reference;
        typename  size_type;
        typename  difference_type;
        typename reverse_iterator;
        typename  const_reverse_iterator;

       // Construct/Copy/Destroy

        explicit deque (const Allocator& = Allocator());
        explicit deque (size_type, const Allocator&	= Allocator ());
        deque (size_type, const T& value,
    	   const Allocator& = Allocator	());
        deque (const deque<T,Allocator>&);
        template <class InputIterator>
         deque (InputIterator, InputIterator,
    	    const Allocator& = Allocator ());
         ~deque ();
        deque<T,Allocator>&	operator= (const deque<T,Allocator>&);
        template <class InputIterator>
         void assign (InputIterator, InputIterator);
        template <class Size, class	T>
         void assign (Size);
        template <class Size, class	T>
         void assign (Size,	const T&);
        allocator_type get allocator () const;

       // Iterators

        iterator begin ();
        const_iterator begin () const;
        iterator end ();
        const_iterator end () const;
        reverse_iterator rbegin ();
        const_reverse_iterator rbegin () const;
        reverse_iterator rend ();
        const_reverse_iterator rend	() const;

      // Capacity

        size_type size () const;
        size_type max_size () const;
        void resize	(size_type);
        void resize	(size_type, T);
        bool empty () const;

      // Element access

        reference operator[] (size_type);
        const_reference operator[] (size_type) const;
        reference at (size_type);
        const_reference at (size_type) const;
        reference front ();
        const_reference front () const;
        reference back ();
        const_reference back () const;

       // Modifiers

        void push_front (const T&);
        void push_back (const T&);
        iterator insert (iterator);
        iterator insert (iterator, const T&);
        void insert	(iterator, size_type, const T&);
        template <class InputIterator>
         void insert (iterator, InputIterator, InputIterator);

        void pop_front ();
        void pop_back ();

        iterator erase (iterator);
        iterator erase (iterator, iterator);
        void swap (deque<T,	Allocator>&);
        void clear();
      };

       // Non-member Operators

      template <class T, class Allocator>
      bool operator== (const deque<T, Allocator>&,
    		   const deque<T, Allocator>&);

      template <class T, class Allocator>
      bool operator!= (const deque<T, Allocator>&,
    		   const deque<T, Allocator>&);

      template <class T, class Allocator>
      bool operator< (const	deque<T, Allocator>&,
    		  const	deque<T, Allocator>&);

      template <class T, class Allocator>
      bool operator> (const	deque<T, Allocator>&,
    		  const	deque<T, Allocator>&);

      template <class T, class Allocator>
      bool operator<= (const deque<T, Allocator>&,
    		  const	deque<T, Allocator>&);

      template <class T, class Allocator>
      bool operator>= (const deque<T, Allocator>&,
    		  const	deque<T, Allocator>&);

      // Specialized Algorithms

      template <class T, class Allocator>
      voice	swap (deque<T, Allocator>&, deque<T, Allocator>&);

    CONSTRUCTORS AND DESTRUCTOR

      explicit
      deque(const Allocator& alloc = Allocator());
         The default constructor.  Creates a deque of zero elements. The
         deque will use the allocator alloc for all storage management.

      explicit
      deque(size_type n, const Allocator& alloc = Allocator());
         Creates a list of length n, containing n copies of	the default
         value for type T. Requires that T have a default constructor.
         The deque will use the allocator alloc for all storage
         management.

      deque(size_type n, const T& value,
    	const Allocator& alloc = Allocator());
    	   Creates a list of length n,	containing n copies of
               value. The deque will use the allocator alloc for all
               storage management.

      deque(const deque<T, Allocator>& x);
         Copy constructor. Creates a copy of x.

      template <class InputIterator>
      deque(InputIterator first, InputIterator last,
    	const Allocator& alloc = Allocator());
    	   Creates a deque of length last - first, filled with
               all values obtained  by dereferencing the InputIterators
               on the range [first, last). The deque will use the allocator
               alloc for all storage management.

      ~deque();
         The destructor.  Releases any allocated memory for	self.

    ALLOCATOR

      allocator
      allocator_type get_allocator() const;
         Returns a copy of the allocator used by self for storage management.

    ITERATORS

      iterator begin();
         Returns a random access iterator that points to the first element.

      const_iterator begin() const;

         Returns a constant	random access iterator that points to the first
         element.

      iterator end();
         Returns a random access iterator that points to the past-the-end
         value.

      const_iterator end() const;
         Returns a constant	random access iterator that points to the
         past-the-end value.

      reverse_iterator rbegin();
         Returns a random access reverse_iterator that points to the
         past-the-end value.

      const_reverse_iterator rbegin() const;
         Returns a constant	random access reverse iterator that points
         to the past-the-end value.

      reverse_iterator rend();
         Returns a random access reverse_iterator that points to the
         first element.

      const_reverse_iterator rend()	const;
         Returns a constant	random access reverse iterator that points
         to the first element.

    ASSIGNMENT OPERATOR

      deque<T, Allocator>&
      operator=(const deque<T, Allocator>& x);
         Erases all	elements in self then inserts into self	a copy of
         each element in x.	Returns	a reference to self.

    REFERENCE OPERATORS

      reference operator[](size_type n);
         Returns a reference to element n of self.	 The  result can
         be used as an lvalue. The index n must be between 0 and the
         size less one.

      const_reference operator[](size_type n) const;
         Returns a constant	reference to element n of self.	 The index
         n must be between 0 and the size() -1.

    MEMBER FUNCTIONS

      template <class InputIterator>
      void
      assign(InputIterator first, InputIterator last);
         Erases all	elements contained in self, then inserts new elements
         from the range [first, last).

      template <class Size,	class T>
      void
      assign(Size n);
         Erases all	elements contained in self, then inserts n instances
         of	the default value of type T.

      template <class Size,	class T>
      void
      assign(Size n, const T& t);
         Erases all	elements contained in self, then inserts n instances
         of	the value of t.

      reference
      at(size_type n);
         Returns a reference to element n of self.	The  result can	be
         used as an lvalue.  The index n must be between 0 and the
         size() - 1.

      const_reference
      at(size_type)	const;
         Returns a constant	reference to element n of self.	 The index n
         must be between 0 and the size() -	1.

      reference
      back();
         Returns a reference to the	last element.

      const_reference
      back() const;
         Returns a constant	reference to the last element.

      void
      clear();
         Erases all	elements from the self.

      bool
      empty() const;
         Returns true if the size of self is zero.

      reference
      front();
         Returns a reference to the	first element.

      const_reference
      front() const;
         Returns a constant	reference to the first element.

      iterator
      erase(iterator first,	iterator last);
         Deletes the elements in the range (first, last). Returns an
         iterator pointing to the element following the last deleted
         element, or end() if there were no elements after the deleted
         range.

      iterator
      erase(iterator position);
         Removes the element pointed to by position. Returns an iterator
         pointing to the element following the deleted element, or end()
         if there were no elements after the deleted range.

      iterator
      insert(iterator position);
         Inserts a copy of the default value of type T before position.
         The return value points to the inserted element.  Requires that
         type T have a default constructor.

      iterator
      insert(iterator position, const T& x);
         Inserts x before position.	 The return value points to the
         inserted x.

      void
      insert(iterator position, size_type n, const T& x);
         Inserts n copies of x before position.

      template <class InputIterator>
      void
      insert(iterator position, InputIterator first,
    	 InputIterator last);
    	    Inserts copies of the elements in the range	(first,	last]
                before position.

      size_type
      max_size() const;
         Returns size() of the largest possible deque.

      void
      pop_back();
         Removes the last element.	Note that this function	does not return
         the element.

      void
      pop_front();
         Removes the first element.	 Note that this	function does not return
         the element

      void
      push_back(const T& x);
         Appends a copy of x to the	end.

      void
      push_front(const T& x);
         Inserts a copy of x at the	front.

      void
      resize(size_type sz);
         Alters the	size of	self.  If the new size (sz) is greater than
         the current size then sz-size() copies	of the default value
         of	type T  are inserted at the end of the	deque. If the new size
         is smaller  than the current capacity, then the deque is
         truncated by erasing  size()-sz	elements off the end.
         Otherwise, no action is	taken.  Requires that type T have a
         default constructor.

      void
      resize(size_type sz, T c);
         Alters the	size of	self.  If the new size (sz) is greater than
         the current size then sz-size() c's are  inserted at the end of
         the  deque.  If	the new	size is	smaller	than the current
         capacity, then	the deque is truncated by erasing size()-sz
         elements off the end.  Otherwise, no action is taken.

      size_type
      size() const;
         Returns the number	of elements.

      void
      swap(deque<T,Allocator>& x);
         Exchanges self with x.

    NON-MEMBER FUNCTIONS

      template <class T, class Allocator>
      bool operator==(const	deque<T, Allocator>& x,
    		  const	deque<T, Allocator>& y);
    		     Equality operator.	Returns	true if	x is the same
                         as y.

      template <class T, class Allocator>
      bool operator!=(const	deque<T, Allocator>& x,
    		  const	deque<T, Allocator>& y);
    		     Inequality	operator. Returns true if x is not the
                         same as y.

      template <class T, class Allocator>
      bool operator<(const deque<T,	Allocator>& x,
    		 const deque<T,	Allocator>& y);
    		    Returns true if the	elements contained in x	are
                        lexicographically less than the elements contained
                        in y.

      template <class T, class Allocator>
      bool operator>(const deque<T,	Allocator>& x,
    		 const deque<T,	Allocator>& y);
    		    Returns true if the	elements contained in x	are lexico-
    		    graphically	greater	than the elements contained in y.

      template <class T, class Allocator>
      bool operator<=(const	deque<T, Allocator>& x,
    		 const deque<T,	Allocator>& y);
    		    Returns true if the	elements contained in x	are lexico-
    		    graphically	less than or equal to the elements contained
    		    in y.

      template <class T, class Allocator>
      bool operator>=(const	deque<T, Allocator>& x,
    		 const deque<T,	Allocator>& y);
    		    Returns true if the	elements contained in x	are lexico-
    		    graphically	greater	 than or equal to the elements con-
    		    tained in y.

      template <class T, class Allocator>
      bool operator<(const deque<T,	Allocator>& x,
    		 const deque<T,	Allocator>& y);
    		    Returns true if the	elements contained in x	are lexico-
    		    graphically	less than the elements contained in y.

    SPECIALIZED ALGORITHMS

      template <class T, class Allocator>
      void swap(deque<T, Allocator>& a, deque<T, Allocator>& b);
         Efficiently swaps the contents of a and b.

    EXAMPLE

      //
      // deque.cpp
      //
       #include <deque>
       #include <string>

      deque<string,	allocator> deck_of_cards;
      deque<string,	allocator> current_hand;

      void initialize_cards(deque<string, allocator>& cards) {
        cards.push_front("aceofspades");
        cards.push_front("kingofspades");
        cards.push_front("queenofspades");
        cards.push_front("jackofspades");
        cards.push_front("tenofspades");
         //	etc.
       }

      template <class It, class It2>
      void print_current_hand(It start, It2	end)
       {
        while (start < end)
        cout << *start++ <<	endl;
       }

      template <class It, class It2>
      void deal_cards(It, It2 end) {
        for	(int i=0;i<5;i++) {
          current_hand.insert(current_hand.begin(),*end);
          deck_of_cards.erase(end++);
         }
       }

      void play_poker() {
        initialize_cards(deck_of_cards);
        deal_cards(current_hand.begin(),deck_of_cards.begin());
       }

      int main()
       {
        play_poker();
        print_current_hand(current_hand.begin(),current_hand.end());
        return 0;
       }

      Output :
      aceofspades
      kingofspades
      queenofspades
      jackofspades
      tenofspades

    WARNINGS

      Member function templates are	used in	all containers provided	by the
      Standard C++ Library.	 An example of this is the constructor for
      deque<T,Allocator> that takes	two templated iterators:

      template <class InputIterator>
      deque	(InputIterator,	InputIterator);

      deque	also has an insert function of this type. These	functions,
      when	not restricted by compiler limitations, allow you to use any
      type	of input iterator as arguments.  For compilers	that do	not
      support this feature we provide substitute functions that allow you
      to use an iterator obtained from the same type of container as the one
      you are constructing (or calling a member function on), or you
      can use a pointer to the type of element you have in the container.

      For example, if your compiler	does not support member	function
      templates you can construct a deque in the following two ways:

      int intarray[10];
      deque<int> first_deque(intarray, intarray + 10);
      deque<int> second_deque(first_deque.begin(),
    			 first_deque.end());

      But not this way:

      deque<long> long_deque(first_deque.begin(),
    				   first_deque.end());

      since	the long_deque and first_deque are not the same	type.

      Additionally,	many compilers do not support default template arguments.
      If your compiler is one of these, you need to always supply the
      Allocator template argument.  For instance, you'll have to write:

      deque<int, allocator<int> >

         instead of:

      deque<int>

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

    list
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      list	- A sequence that supports bidirectional iterators

    SYNOPSIS

      #include <list>

      template <class T, class Allocator = allocator<T> >
      class	list;

    DESCRIPTION

      list<T,Allocator> is a type of sequence that supports	bidirectional
      iterators.	 A list<T,Allocator> allows constant time insert and
      erase operations anywhere within the sequence, with storage
      management handled automatically. Constant time random access is
      not supported.

      Any type used	for the	template parameter T must provide  the
      following (where T is the type,	t is a value of	T and u	is a
      const value of T):

       Default constructor	 T()
       Copy	constructors	 T(t) and T(u)
       Destructor		 t.~T()
       Address of		 &t and	&u yielding T* and
    			  const	T* respectively
       Assignment		 t = a where a is a
    			   (possibly const) value of T

    INTERFACE

      template <class T, class Allocator = allocator<T> >
      class	list {

      public:

      // typedefs

        class iterator;
        class const_iterator;
        typename reference;
        typename const_reference;
        typename size_type;
        typename difference_type;
        typedef T value_type;
        typedef Allocator allocator_type;

        typename reverse_iterator;
        typename const_reverse_iterator;

      // Construct/Copy/Destroy

        explicit list (const Allocator& = Allocator());
        explicit list (size_type, const Allocator& = Allocator());
        list (size_type, const T&, const Allocator&	= Allocator())
        template <class InputIterator>
        list (InputIterator, InputIterator,
    	  const	Allocator& = Allocator());
        list(const list<T, Allocator>& x);
         ~list();
        list<T,Allocator>& operator= (const	list<T,Allocator>&);
        template <class InputIterator>
         void assign (InputIterator, InputIterator);
        template <class Size, class	T>
         void assign (Size n);
        template <class Size, class	T>
         void assign (Size n, const	T&);

        allocator_type get allocator () const;

      // Iterators

        iterator begin ();
        const_iterator begin () const;
        iterator end ();
        const_iterator end () const;
        reverse_iterator rbegin ();
        const_reverse_iterator rbegin () const;
        reverse_iterator rend ();
        const_reverse_iterator rend	() const;

      // Capacity

        bool empty () const;
        size_type size () const;
        size_type max_size () const;
        void resize	(size_type);
        void resize	 (size_type, T);

      // Element Access

        reference front ();
        const_reference front () const;
        reference back ();
        const_reference back () const;

      // Modifiers

        void push_front (const T&);
        void pop_front ();
        void push_back (const T&);
        void pop_back ();

        iterator insert (iterator);
        iterator insert (iterator, const T&);
        void insert	(iterator, size_type, const T&);
        template <class InputIterator>
         void insert  (iterator, InputIterator, InputIterator);

        iterator erase (iterator);
        iterator erase (iterator, iterator);

        void swap (list<T, Allocator>&);
        void clear ();

      // Special mutative operations on list

        void splice	(iterator, list<T, Allocator>&);
        void splice	(iterator, list<T, Allocator>&,	iterator);
        void splice	(iterator, list<T, Allocator>&,	iterator, iterator);

        void remove	(const T&);
        template <class Predicate>
         void remove_if (Predicate);

        void unique	();
        template <class BinaryPredicate>
         void unique (BinaryPredicate);

        void merge (list<T,	Allocator>&);
        template <class Compare>
         void merge	(list<T, Allocator>&, Compare);

        void sort ();
        template <class Compare>
         void sort (Compare);

        void reverse();
      };

      // Non-member	List Operators

      template <class T, class Allocator>
      bool operator== (const list<T, Allocator>&,
    		   const list<T, Allocator>&);

      template <class T, class Allocator>
      bool operator!= (const list<T, Allocator>&,
    		   const list<T, Allocator>&);

      template <class T, class Allocator>
      bool operator< (const	list<T,	Allocator>&,
    		  const	list<T,	Allocator>&);

      template <class T, class Allocator>
      bool operator> (const	list<T,	Allocator>&,
    		  const	list<T,	Allocator>&);

      template <class T, class Allocator>
      bool operator<= (const list<T, Allocator>&,
    		  const	list<T,	Allocator>&);

      template <class T, class Allocator>
      bool operator>= (const list<T, Allocator>&,
    		  const	list<T,	Allocator>&);

      // Specialized Algorithms

      template <class T, class Allocator>
      void swap (list<T,Allocator>&, list<T, Allocator>&);

    CONSTRUCTORS AND DESTRUCTORS

      explicit list(const Allocator& alloc = Allocator());
         Creates a list of zero elements. The list will use	the allocator
         alloc for all storage management.

      explicit list(size_type n,
    		const Allocator& alloc = Allocator());
    		   Creates a list of length n, containing n copies of the
    		   default value for type T. Requires that T have a default
    		   constructor.	The list will use the allocator	alloc for
                       all storage management.

      list(size_type n, const T& value,
           const Allocator&	alloc =	Allocator());
    	  Creates a list of length n, containing n copies of value. The
              list will use the allocator alloc for all storage management.

      template <class InputIterator>
      list(InputIterator first, InputIterator last,
           const Allocator&	alloc =	Allocator());
    	  Creates a list of length last	- first, filled	with all values
    	  obtained by dereferencing the	InputIterators on the range [first,
    	  last). The list will use the allocator alloc for all storage
    	  management.

      list(const list<T, Allocator>& x);
         Copy constructor.	Creates	a copy of x.

      ~list();
         The destructor. Releases any allocated memory for this list.

    ASSIGNMENT OPERATOR

      list<T, Allocator>&
      operator=(const list<T, Allocator>& x)
         Erases all	elements in self then inserts into self	a copy of each
         element in x. Returns a reference to *this.

    ALLOCATOR

      allocator_type
      get_allocator() const;
         Returns a copy of the allocator used by self for storage management.

    ITERATORS

      iterator
      begin();
         Returns a bidirectional iterator that points to the first element.

      const_iterator
      begin() const;
         Returns a constant	bidirectional iterator that points to the first
         element.

      iterator
      end();
         Returns a bidirectional iterator that points to the past-the-end
         value.

      const_iterator
      end()	const;
         Returns a constant	bidirectional iterator	that  points to	the
         past-the-end value.

      reverse_iterator
      rbegin();
         Returns a bidirectional iterator that points to the past-the-end
         value.

      const_reverse_iterator
      rbegin() const;
         Returns a constant	bidirectional iterator that points to the
         past-the-end value.

      reverse_iterator
      rend();
         Returns a bidirectional iterator that points to the first element.

      const_reverse_iterator
      rend() const;
         Returns a constant	bidirectional iterator that  points to the first
         element.

    MEMBER FUNCTIONS

      template <class InputIterator>
      void
      assign(InputIterator first, InputIterator last);
         Erases all	elements contained in self, then inserts new elements
         from the range [first, last).

      template <class Size,	class T>
      void
      assign(Size n);
         Erases all	elements contained in self, then inserts n instances of
         the default value of t.

      template <class Size,	class T>
      void
      assign(Size n, const T& t);
         Erases all	elements contained in self, then inserts n instances of
         the value of t.

      reference
      back();
         Returns a reference to the	last element.

      const_reference
      back() const;
         Returns a constant	reference to the last element.

      void
      clear();
         Erases all	elements from the list.

      bool
      empty() const;
         Returns true if the size is zero.

      iterator
      erase(iterator position);
         Removes the element pointed to by position. Returns an iterator
         pointing to the element following the deleted element, or end() if
         the deleted item was the last one in this list.

      iterator
      erase(iterator first,	iterator last);
         Removes the elements in the range (first, last). Returns an
         iterator pointing to the element following the element following
         the last  deleted element, or end() if there	were no
         elements after the deleted  range.

      reference
      front();
         Returns a reference to the	first element.

      const_reference
      front() const;
         Returns a constant	reference to the first element.

      iterator
      insert(iterator position);
         Inserts a copy of the default value for type T before position.
         Returns an	iterator that points to	the inserted value. Requires
         that  type T have a default constructor.

      iterator
      insert(iterator position, const T& x);
         Inserts x before position.	 Returns an iterator that points to the
         inserted x.

      void
      insert(iterator position, size_type n, const T& x);
         Inserts n copies of x before position.

      template <class InputIterator>
      void
      insert(iterator position, InputIterator first,
    	 InputIterator last);
    	    Inserts copies of the elements in the range	[first,	last)
                before position.

      size_type
      max_size() const;
         Returns size() of the largest possible list.

      void merge(list<T, Allocator>& x);
         Merges a sorted x with a sorted self using	operator<.  For	equal
         elements in the two lists, elements from self will always precede
         the elements from	x.  The	merge function leaves x	empty.

      template <class Compare>
      void
      merge(list<T,	Allocator>& x, Compare comp);
         Merges a sorted x with sorted self	using a	 compare function
         object,comp.  For	same elements in the two lists,	elements from
         self will always precede the elements from x.  The merge function
         leaves x empty.

      void
      pop_back();
         Removes the last element.

      void
      pop_front();
         Removes the first element.

      void
      push_back(const T& x);
         Appends a copy of x to the	end of the list.

      void
      push_front(const T& x);
         Appends a copy of x to the	front of the list.

      void
      remove(const T& value);
      template <class Predicate>
      void
      remove_if(Predicate pred);
         Removes all elements in the list referred by the list iterator i
         for which *i == value or pred(*i) == true, whichever is applicable.
         This is a stable operation, the relative order of list items  that
         are not removed is	preserved.

      void
      resize(size_type sz);
         Alters the	size of	self.  If the new size ( sz ) is greater than
         the current size, sz-size() copies of the default value of type T
         are inserted at the end of the list.  If the new size is smaller
         than  the current capacity, then the list is truncated by erasing
         size()-sz  elements off the end. Otherwise,  no action is taken.
         Requires that type T have a default constructor.

      void
      resize(size_type sz, T c);
         Alters the	size of	self.  If the new size ( sz ) is greater than
         the current size, sz-size() c's are inserted at the end of the
         list.  If the new size is smaller than the current capacity, then
         the list is truncated by erasing size()-sz elements off the end.
         Otherwise,  no action is taken.

      void
      reverse();
         Reverses the order	of the elements.

      size_type
      size() const;
         Returns the number	of elements.

      void
      sort();
         Sorts self	according to the  operator<.  sort  maintains the
         relative order of equal elements.

      template <class Compare>
      void
      sort(Compare comp);
         Sorts self	according to a comparison function object, comp.
         This is also a stable sort.

      void
      splice(iterator position, list<T, Allocator>&	x);
         Inserts x before position leaving x empty.

      void
      splice(iterator position, list<T, Allocator>&	 x, iterator i);
         Moves the elements	pointed	to by iterator i in x to self,
         inserting  it before position.  The element is removed from x.

      void
      splice(iterator position, list<T, Allocator >&  x,
    	 iterator first, iterator last);
         Moves the elements in the range [first, last) in x to self,
         inserting before position.	The elements in	 the range
         [first,last) are removed from x.

      void
      swap(list <T,	Allocator>& x);
         Exchanges self with x.

      void
      unique();
         Erases copies of consecutive repeated elements leaving the	first
         occurrence.

      template <class BinaryPredicate>
      void
      unique(BinaryPredicate binary_pred);
         Erases consecutive	elements matching a true condition of the
         binary_pred.  The first occurrence	is not removed.

    NON-MEMBER OPERATORS

      template <class T, class Allocator>
      bool operator==(const	list<T,	Allocator>& x,
    		  const	list<T,	Allocator>& y);
         Equality operator.	Returns	true if	x is the same  as y.

      template <class T, class Allocator>
      bool operator!=(const	list<T,	Allocator>& x,
    		  const	list<T,	Allocator>& y);
         Inequality	operator. Returns !(x==y).

      template <class T, class Allocator>
      bool operator<(const list<T, Allocator>& x,
    		 const list<T,Allocator>& y);
         Returns true if the	sequence defined by the	elements
         contained in x is lexicographically less than the  sequence
         defined by the elements contained in y.

      template <class T, class Allocator>
      bool operator>(const list<T, Allocator>& x,
    		 const list<T,Allocator>& y);
    		    Returns y <	x.

      template <class T, class Allocator>
      bool operator<=(const	list<T,	Allocator>& x,
    		 const list<T,Allocator>& y);
    		    Returns !(y	< x).

      template <class T, class Allocator>
      bool operator>=(const	list<T,	Allocator>& x,
    		 const list<T,Allocator>& y);
    		    Returns !(x	< y).

    SPECIALIZED ALGORITHMS

      template <class T, class Allocator>
      void swap(list<T, Allocator>&	a, list<T, Allocator>& b);
         Efficiently swaps the contents of a and b.

    EXAMPLE

      //
      // list.cpp
      //
       #include <list>
       #include <string>
       #include <iostream.h>
       // Print out	a list of strings
      ostream& operator<<(ostream& out, const list<string>&	l)
       {
        copy(l.begin(), l.end(),
    	 ostream_iterator<string,char>(cout," "));
        return out;
       }
      int main(void)
       {
         //	create a list of critters
        list<string> critters;
        int	i;
         //	insert several critters
        critters.insert(critters.begin(),"antelope");
        critters.insert(critters.begin(),"bear");
        critters.insert(critters.begin(),"cat");

         //	print out the list
        cout << critters <<	endl;

         //	Change cat to cougar
         *find(critters.begin(),critters.end(),"cat") = "cougar";
        cout << critters <<	endl;

         //	put a zebra at the beginning
         //	an ocelot ahead	of antelope
         //	and a rat at the end
        critters.push_front("zebra");
        critters.insert(find(critters.begin(),critters.end(),
    		     "antelope"),"ocelot");
        critters.push_back("rat");
        cout << critters <<	endl;

         //	sort the list (Use list's sort function	since the
         //	generic	algorithm requires a random access iterator
         //	and list only provides bidirectional)
        critters.sort();
        cout << critters <<	endl;

         //	now let's erase	half of	the critters
        int	half = critters.size() >> 1;
        for(i = 0; i < half; ++i) {
          critters.erase(critters.begin());
         }
        cout << critters <<	endl;
        return 0;
       }

      Output :
      cat bear antelope
      cougar bear antelope
      zebra	cougar bear ocelot antelope rat
      antelope bear	cougar ocelot rat zebra
      ocelot  rat zebra

    WARNINGS

      Member function templates are	used in	all containers provided	by the
      Standard C++ Library.  An example of this feature is the constructor
      for list<T, Allocator> that takes two templated iterators:

      template <class InputIterator>
      list (InputIterator, InputIterator,
           const Allocator&	= Allocator());

      list also has	an insert function of this type.  These	functions,
      when	not restricted by compiler limitations, allow you to use any
      type	of input iterator as arguments.  For compilers	that do	not
      support this feature, we provide substitute functions that allow you
      to use an iterator obtained from the same type of container as the
      one  you are constructing (or calling a member function on), or you
      can  use a pointer to the type of element you have in the container.

      For example, if your compiler	does not support member	 function
      templates you can construct a list in the following two ways:

      int intarray[10];
      list<int> first_list(intarray,intarray + 10);
      list<int> second_list(first_list.begin(),first_list.end());

      But not this way:

      list<long> long_list(first_list.begin(),first_list.end());

      since	the long_list and first_list are not the same type.

      Additionally,	list provides a	merge function of this type.

      template <class Compare> void	merge (list<T, Allocator>&,
       Compare);

      This function	allows you to specify a	compare	function object	to
      be used in merging two lists.  In this case, we were unable to
      provide a substitute function in addition to the merge that uses
      the operator< as the default. Thus,	if your	compiler does not
      support member function templates, all list mergers will use
      operator<.

      Also,	many compilers do not support default template arguments.
      If your compiler is one of these, you	need to	always supply the
      Allocator template argument. For instance, you'll have to write:

      list<int, allocator<int> >

      instead of:

      list<int>

    SEE ALSO

      allocator, Containers, Iterators

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

    map
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      map  - An associative	container providing access to non-key values
      using unique keys.	A map supports bidirectional iterators.

    SYNOPSIS

      #include <map>

      template <class Key, class T,	class Compare =	less<Key>
    	   class Allocator = allocator<T> >
      class	map;

    DESCRIPTION

      map <Key, T, Compare,	Allocator> provides fast access	to stored
      values of type T  which are indexed by unique keys of type Key.
      The default operation for key comparison is the < operator.

      map provides bidirectional iterators	that point to an instance of
      pair<const Key x, T y> where x is the	key and	y is the stored	value
      associated with that key.  The definition of map provides a typedef
      to this pair called value_type.

      The types used for both the template parameters  Key	and T must
      provide the following	(where T is the	type, t	is a value of T	and
      u is a const value of T):

       Copy	constructors -	T(t) and T(u)
       Destructor	     -	t.~T()
       Address of	     -	&t and &u yielding T* and
    			const T* respectively
       Assignment	     -	t = a where a is a
    			 (possibly const) value	of T

      The type used	for the	Compare	template parameter must	satisfy	the
      requirements	for binary functions.

    INTERFACE

      template <class Key, class T,	class Compare =	less<Key>
    	   class Allocator = allocator<T> >
      class	map {

      public:

      // types

        typedef Key	key_type;
        typedef T mapped_type;
        typedef pair<const Key, T> value_type;
        typedef Compare key_compare;
        typedef Allocator allocator_type;
        typename reference;
        typename const_reference;
        typename iterator;
        typename const_iterator;
        typename size_type;
        typename difference_type;
        typename reverse_iterator;
        typename const_reverse_iterator;

        class value_compare
    	: public binary_function<value_type, value_type, bool>
         {
          friend class map<Key, T, Compare,	Allocator>;

          public :
    	bool operator()	(const value_type&,
    			 const value_type&) const;
         };

      // Construct/Copy/Destroy

        explicit map (const	Compare& = Compare(),
    		  const	Allocator& = Allocator ());
        template <class InputIterator>
         map (InputIterator, InputIterator,
    	  const	Compare& = Compare(),
    	  const	Allocator& = Allocator ());
        map	(const map<Key,	T, Compare, Allocator>&);
         ~map();
        map<Key, T,	Compare, Allocator>&
         operator= (const map<Key, T, Compare, Allocator>&);
        allocator_type get_allocator () const;

      // Iterators

        iterator begin();
        const_iterator begin() const;
        iterator end();
        const_iterator end() const;
        reverse_iterator rbegin();
        const_reverse_iterator rbegin() const;
        reverse_iterator rend();
        const_reverse_iterator rend() const;

      // Capacity

        bool empty() const;
        size_type size() const;
        size_type max_size() const;

      // Element Access

        mapped_type& operator[] (const key_type&);
        const mapped_type& operator[] (const key_type&) const;

      // Modifiers

        pair<iterator, bool> insert	(const value_type&);
        iterator insert (iterator, const value_type&);
        template <class InputIterator>
         void insert (InputIterator, InputIterator);

        iterator erase (iterator);
        size_type erase (const key_type&);
        iterator erase (iterator, iterator);
        void swap (map<Key,	T, Compare, Allocator>&);

      // Observers

        key_compare	key_comp() const;
        value_compare value_comp() const;

      // Map operations

        iterator find (const key_value&);
        const_iterator find	(const key_value&) const;
        size_type count (const key_type&) const;
        iterator lower_bound (const	key_type&);
        const_iterator lower_bound (const key_type&) const;
        iterator upper_bound (const	key_type&);
        const_iterator upper_bound (const key_type&) const;
        pair<iterator, iterator> equal_range (const	key_type&);
        pair<const_iterator, const_iterator>
          equal_range (const key_type&) const;
      };

      // Non-member	Map Operators

      template <class Key, class T,	class Compare, class Allocator>
       bool	operator== (const map<Key, T, Compare, Allocator>&,
    		   const map<Key, T, Compare, Allocator>&);

      template <class Key, class T,	class Compare, class Allocator>
       bool	operator!= (const map<Key, T, Compare, Allocator>&,
    		   const map<Key, T, Compare, Allocator>&);

      template <class Key, class T,	class Compare, class Allocator>
      bool operator< (const	map<Key, T, Compare, Allocator>&,
    		  const	map<Key, T, Compare, Allocator>&);

      template <class Key, class T,	class Compare, class Allocator>
      bool operator> (const	map<Key, T, Compare, Allocator>&,
    		  const	map<Key, T, Compare, Allocator>&);

      template <class Key, class T,	class Compare, class Allocator>
      bool operator<= (const map<Key, T, Compare, Allocator>&,
    		  const	map<Key, T, Compare, Allocator>&);

      template <class Key, class T,	class Compare, class Allocator>
      bool operator>= (const map<Key, T, Compare, Allocator>&,
    		  const	map<Key, T, Compare, Allocator>&);

      // Specialized Algorithms

      template <class Key, class T,	class Compare, class Allocator>
      void swap (map<*Key,T,Compare,Allocator>&,
    	     map<Key,T,Compare,Allocator>&);

    CONSTRUCTORS AND DESTRUCTORS

      explicit map(const Compare& comp = Compare(),
    	      const Allocator& alloc = Allocator());
    		 Default constructor.  Constructs an empty map that
                     will use the relation comp to order keys, if it
                     is supplied.  The map will use the allocator alloc for
                     all storage management.

      template <class InputIterator>
      map(InputIterator first, InputIterator last,
         const Compare& comp = Compare(),
         const Allocator& alloc = Allocator());
    	Constructs a map containing values in the range	[first,	last).
            Creation of the new map is only guaranteed to succeed if
            the iterators first and  last return values of type
            pair<class Key, class Value> and all values of Key in the
            range[first, last) are unique. The map will use the relation
            comp to order keys, and the allocator alloc for all storage
            management.

      map(const map<Key,T,Compare,Allocator>& x);
         Copy constructor.	Creates	a new map by copying all pairs of key
         and value from x.

      ~map();
         The destructor.  Releases any allocated memory for	this map.

    ALLOCATOR

      allocator_type get_allocator() const;
         Returns a copy of the allocator used by self for storage management.

    ITERATORS

      iterator
      begin() ;
         Returns an	iterator pointing to the first element stored in the
         map. "First" is	defined	by the map's comparison	operator,
         Compare.

      const_iterator
      begin() const;
         Returns a const_iterator pointing to the first element stored in
         the map.

      iterator
      end()	;
         Returns an	iterator pointing to the last element  stored in the
         map, i.e., the off-the-end value.

      const_iterator
      end()	const;
         Returns a const_iterator pointing to the last element stored in
         the  map.

      reverse_iterator
      rbegin();
         Returns a reverse_iterator	pointing to the	first element stored
         in	the map.  "First" is defined by the map's comparison operator,
         Compare.

      const_reverse_iterator
      rbegin() const;
         Returns a const_reverse_iterator pointing to the  first element
         stored in	the map.

      reverse_iterator
      rend() ;
         Returns a reverse_iterator	pointing to the	last element stored
         in the map, i.e.,	the off-the-end	value.

      const_reverse_iterator
      rend() const;
         Returns a const_reverse_iterator pointing to the last element
         stored  in the map.

    MEMBER OPERATORS

      map<Key, T, Compare, Allocator>&
      operator=(const map<Key, T, Compare, Allocator>& x);
         Assignment.  Replaces the contents	of *this with a	copy of	the
         map	x.

      mapped_type&
      operator[](const key_type& x);
         If	an element with	the key	x exists in the	map, then a reference
         to  its associated value will be returned. Otherwise the pair
         x,T() will  be inserted into the map and a reference to the
         default object T()  will be returned.

    ALLOCATOR

      allocator_type
      get_allocator() const;
         Returns a copy of the allocator used by self for storage
         management.

    MEMBER FUNCTIONS

      void
      clear();
         Erases all	elements from the self.

      size_type
      count(const key_type&	x) const;
         Returns a 1 if a value with the key x exists in  the map,
         otherwise returns a 0.

      bool
      empty() const;
         Returns true if the map is	empty, false otherwise.

      pair<iterator, iterator>
      equal_range (const  key_type&	x);
         Returns the pair, (lower_bound(x),	upper_bound(x)).

      pair<const_iterator,const_iterator>
      equal_range(const key_type& x) const;
         Returns the pair, (lower_bound(x),	upper_bound(x)).

      iterator
      erase(iterator position);
         Deletes the map element pointed to	by the iterator	position.
         Returns an iterator pointing to the element following the deleted
         element, or end() if the deleted item was the last one in this
         list.

      iterator
      erase(iterator first,	iterator last);
         Providing the iterators first and last point to the same map and
         last is reachable from first, all elements	in the range  (first,
         last) will	be deleted from the map. Returns an iterator  pointing
         to the element following the last deleted element, or  end() if
         there were no elements after the deleted range.

      size_type
      erase(const key_type&	x);
         Deletes the element with the key value x from the map, if one
         exists. Returns 1 if x existed  in	the map, 0 otherwise.

      iterator
      find(const key_type& x);
         Searches the map for a pair with the key value x and returns an
         iterator to that pair if it is found.  If such  a  pair
         is not found  the value end() is returned.

      const_iterator find(const key_type& x) const;
         Same as find above	but returns a const_iterator.

      pair<iterator, bool>
      insert(const value_type& x);
      iterator
      insert(iterator position, const value_type& x);
         If	a value_type with the same key as  x  is  not present in the
         map, then x is inserted into the map. Otherwise, the pair is not
         inserted. A position may be supplied as a hint regarding where
         to do the insertion. If the insertion may be done right after
         position then it takes  amortized  constant time.  Otherwise it
         will take O(log N) time.

      template <class InputIterator>
      void
      insert(InputIterator first, InputIterator last);
         Copies of each element in the range [first, last) which  possess
         a unique key, one not already in the	map, will be inserted
         into the map. The  iterators first and last must	return values
         of type pair<T1,T2>. This  operation takes approximately
         O(N*log(size()+N)) time.

      key_compare
      key_comp() const;
         Returns a function	object capable of comparing key	values using
         the comparison operation,	Compare, of the	current	map.

      iterator
      lower_bound(const key_type& x);
         Returns a reference to the	first entry with a key greater than
         or equal to x.

      const_iterator
      lower_bound(const key_type& x) const;
         Same as  lower_bound above	but returns a const_iterator.

      size_type
      max_size() const;
         Returns the maximum possible size of the map.   This size is only
         constrained by the number of unique keys which can be represented
         by the type Key.

      size_type
      size() const;
         Returns the number	of elements in the map.

      void
      swap(map<Key,	T, Compare, Allocator>&	x);
         Swaps the contents	of the map x with the current map, *this.

      iterator
      upper_bound(const key_type& x);
         Returns a reference to the	first entry with a key less than or
         equal to x.

      const_iterator
      upper_bound(const key_type& x) const;
         Same as upper_bound above but returns a const_iterator.

      value_compare
      value_comp() const;
         Returns a function	object	capable	of comparing pair<const	Key,
         T> values using the comparison operation, Compare, of	the
         current map. This function is identical	to key_comp for	sets.

    NON-MEMBER OPERATORS

      template <class Key, class T,	class Compare, class Allocator>
      bool operator==(const	map<Key, T, Compare, Allocator>& x,
    		  const	map<Key, T, Compare, Allocator>& y);
    		     Returns true if all elements in x are element-wise
                         equal to all elements in y, using (T::operator==).
                         Otherwise it returns false.

      template <class Key, class T,	class Compare, class Allocator>
      bool operator!=(const	map<Key, T, Compare, Allocator>& x,
    		  const	map<Key, T, Compare, Allocator>& y);
    		     Returns !(x==y).

      template <class Key, class T,	class Compare, class Allocator>
      bool operator<(const map<Key,	T, Compare, Allocator>&	x,
    		 const map<Key,	T, Compare, Allocator>&	y);
    		    Returns true if x is lexicographically less	than y.
                        Otherwise, it returns false.

      template <class Key, class T,	class Compare, class Allocator>
      bool operator>(const map<Key,	T, Compare, Allocator>&	x,
    		 const map<Key,	T, Compare, Allocator>&	y);
    		    Returns y <	x.

      template <class Key, class T,	class Compare, class Allocator>
      bool operator<=(const	map<Key, T, Compare, Allocator>& x,
    		 const map<Key,	T, Compare, Allocator>&	y);
    		    Returns !(y	< x).

      template <class Key, class T,	class Compare, class Allocator>
      bool operator>=(const	map<Key, T, Compare, Allocator>& x,
    		 const map<Key,	T, Compare, Allocator>&	y);
    		    Returns !(x	< y).

    SPECIALIZED ALGORITHMS

      template <class Key, class T,	class Compare, class Allocator>
      void swap(map<Key, T,	Compare, Allocator>& a,
    	    map<Key, T,	Compare, Allocator>& b);
    	       Efficiently swaps the contents of a and b.

    EXAMPLE

      //
      // map.cpp
      //
       #include <string>
       #include <map>
       #include <iostream.h>

      typedef map<string, int, less<string>	> months_type;

       // Print out	a pair
      template <class First, class Second>
      ostream& operator<<(ostream& out,
    		      const pair<First,Second> & p)
       {
        cout << p.first << " has " << p.second << "	days";
        return out;
       }

       // Print out	a map
      ostream& operator<<(ostream& out, const months_type &	l)
       {
        copy(l.begin(),l.end(), ostream_iterator
    		  <months_type::value_type,char>(cout,"0));
        return out;
       }

      int main(void)
       {
         //	create a map of	months and the number of days
         //	in the month
        months_type	months;

        typedef months_type::value_type value_type;

         //	Put the	months in the multimap
        months.insert(value_type(string("January"),	  31));
        months.insert(value_type(string("February"),   28));
        months.insert(value_type(string("February"),   29));
        months.insert(value_type(string("March"),	  31));
        months.insert(value_type(string("April"),	  30));
        months.insert(value_type(string("May"),	  31));
        months.insert(value_type(string("June"),	  30));
        months.insert(value_type(string("July"),	  31));
        months.insert(value_type(string("August"),	  31));
        months.insert(value_type(string("September"), 30));
        months.insert(value_type(string("October"),	  31));
        months.insert(value_type(string("November"),  30));
        months.insert(value_type(string("December"),  31));

         //	print out the months
         //	Second February	is not present
        cout << months << endl;

         //	Find the Number	of days	in June
        months_type::iterator p = months.find(string("June"));

         //	print out the number of	days in	June
        if (p != months.end())
          cout << endl << *p << endl;

        return 0;
       }

      Output :
      April	has 30 days
      August has 31	days
      December has 31 days
      February has 28 days
      January has 31 days
      July has 31 days
      June has 30 days
      March	has 31 days
      May has 31 days
      November has 30 days
      October has 31 days
      September has	30 days

    WARNING

      Member function templates are	used in	all containers provided	by the
      Standard C++ Library.  An	example	of this	feature	is the constructor
      for map<Key,T,Compare,Allocator> that takes two templated iterators:

      template <class InputIterator>
      map (InputIterator, InputIterator, const Compare& = Compare(),
           const Allocator&	= Allocator());

      map also has an insert function of this type.	 These functions, when
      not restricted by compiler limitations, allow you to use any type
      of input iterator as arguments.  For compilers that do not support
      this  feature, we provide substitute functions that allow you to use
      an	iterator obtained from the same type of container as the one
      you are  constructing (or calling a member function on), or you can
      use a pointer  to the type of element you have in the container.

      For example, if your compiler	does not support member	function
      templates, you can construct a map in the following two ways:

      map<int, int,	less<int> >::value_type	intarray[10];
      map<int, int,	less<int> > first_map(intarray,	intarray + 10);
      map<int, int,	less<int> > second_map(first_map.begin(),
    				      first_map.end());

      But not this way:

      map<long, long, less<long> > long_map(first_map.begin(),
    				       first_map.end());

      Since	the long_map and first_map are not the same type.

      Also,	many compilers do not support default template arguments.   If
      your compiler is one of these, you	need to	always supply the
      Compare template argument and the Allocator template argument. For
      instance, you'll have to write:

      map<int, int,	less<int>,  allocator<int> >

      instead of:

      map<int, int>

    SEE ALSO

      allocator, Containers, Iterators, multimap

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

    multimap
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      multimap  - An associative container providing access	to non-key
      values using	keys.  multimap	keys are not required to be unique.
      A multimap supports	bidirectional iterators.

    SYNOPSIS

      #include <map>

      template <class Key, class T,	class Compare =	less<Key>,
    	   class Allocator = allocator<T> >
      class	multimap ;

    DESCRIPTION

      multimap <Key	,T, Compare, Allocator>	provides fast access to	stored
      values of type T which are indexed by keys of type Key.  The
      default operation for key comparison is the	< operator.  Unlike
      map, multimap  allows insertion of duplicate keys.

      multimap provides bidirectional iterators which point	to  an
      instance	of pair<const Key x, T y> where x is the key and y is
      the stored value  associated with that key. The  definition of
      multimap provides a typedef  to this pair called value_type.

      The types used for both the template parameters  Key	and T must
      provide the following	(where T is the	type, t	is a value of T	and u
      is a const value	of T):

      Copy constructors -  T(t) and	T(u)
       Destructor	     -	t.~T()
       Address of	     -	&t and &u yielding T* and
    			const T* respectively
       Assignment	     -	t = a where a is a
    			 (possibly const) value	of T

      The type used	for the	Compare	template parameter must	satisfy	the
      requirements	for binary functions.

    INTERFACE

      template <class Key, class T,	class Compare =	less<Key>,
    	   class Allocator = allocator<T> >
      class	multimap {

      public:

      // types

        typedef Key	key_type;
        typedef T mapped_type;
        typedef pair<const Key, T> value_type;
        typedef Compare key_compare;
        typedef Allocator allocator_type;
        typename reference;
        typename const_reference;
        typename iterator;
        typename const_iterator;
        typename size_type;
        typename difference_type;
        typename reverse_iterator;
        typename const_reverse_iterator;

      class	value_compare
          :	public binary_function<value_type, value_type, bool>
          {
          friend class multimap<Key, T, Compare, Allocator>;

          public :
    	bool operator()	(const value_type&, const value_type&) const;
          };

      // Construct/Copy/Destroy

        explicit multimap (const Compare& =	Compare(), const Allocator& =
    		       Allocator());
        template <class InputIterator>
         multimap (InputIterator, InputIterator,
    	       const Compare& =	Compare(),
    	       const Allocator&	= Allocator());
        multimap (const multimap<Key, T, Compare, Allocator>&);
         ~multimap ();
        multimap<Key, T, Compare, Allocator>& operator=
    	 (const	multimap<Key, T, Compare, Allocator>&);

      // Iterators

        iterator begin ();
        const_iterator begin () const;
        iterator end ();
        const_iterator end () const;
        reverse_iterator rbegin ();
        const_reverse_iterator rbegin () const;
        reverse_iterator rend ();
        const_reverse_iterator rend	() const;

      // Capacity

        bool empty () const;
        size_type size () const;
        size_type max_size () const;

      // Modifiers

        iterator insert (const value_type&);
        iterator insert (iterator, const value_type&);
        template <class InputIterator>
         void insert (InputIterator, InputIterator);

        iterator erase (iterator);
        size_type erase (const key_type&);
        iterator erase (iterator, iterator);
        void swap (multimap<Key, T,	Compare, Allocator>&);

      // Observers

        key_compare	key_comp () const;
        value_compare value_comp ()	const;

      // Multimap operations

        iterator find (const key_type&);
        const_iterator find	(const key_type&) const;
        size_type count (const key_type&) const;

        iterator lower_bound (const	key_type&);
        const_iterator lower_bound (const key_type&) const;
        iterator upper_bound (const	key_type&);
        const_iterator upper_bound (const key_type&) const;
        pair<iterator, iterator> equal_range (const	key_type&);
        pair<const_iterator, const_iterator>
          equal_range (const key_type&) const;
      };

      // Non-member	Operators

      template <class Key, class T,class Compare, class Allocator>
      bool operator== (const multimap<Key, T, Compare, Allocator>&,
    		   const multimap<Key, T, Compare, Allocator>&);

      template <class Key, class T,class Compare, class Allocator>
      bool operator!= (const multimap<Key, T, Compare, Allocator>&,
    		   const multimap<Key, T, Compare, Allocator>&);

      template <class Key, class T,	class Compare, class Allocator>
      bool operator< (const	multimap<Key, T, Compare, Allocator>&,
    		  const	multimap<Key, T, Compare, Allocator>&);

      template <class Key, class T,	class Compare, class Allocator>
      bool operator> (const	multimap<Key, T, Compare, Allocator>&,
    		  const	multimap<Key, T, Compare, Allocator>&);

      template <class Key, class T,	class Compare, class Allocator>
      bool operator<= (const multimap<Key, T, Compare, Allocator>&,
    		  const	multimap<Key, T, Compare, Allocator>&);

      template <class Key, class T,	class Compare, class Allocator>
      bool operator>= (const multimap<Key, T, Compare, Allocator>&,
    		  const	multimap<Key, T, Compare, Allocator>&);

      // Specialized Algorithms

      template <class Key, class T,	class Compare, class Allocator>
      void swap (multimap<Key, T, Compare, Allocator>&,
    	     multimap<Key, T, Compare, Allocator>&;

    CONSTRUCTORS AND DESTRUCTORS

      explicit multimap(const Compare& comp	= Compare(),
    		   const Allocator& alloc = Allocator());
         Default constructor.  Constructs an empty	multimap  that will
         use the optional relation comp to order  keys and the allocator
         alloc for all storage  management.

      template <class InputIterator>
      multimap(InputIterator first,
    	   InputIterator last,
    	   const Compare& comp = Compare()
    	   const Allocator& alloc = Allocator());
         Constructs a multimap containing values in  the  range
         [first,last).   Creation	of the new multimap is only
         guaranteed to succeed if the iterators first and  last  return
         values of	type pair<class Key, class T>.

      multimap(const multimap<Key, T, Compare, Allocator>& x);
         Copy constructor.	Creates	a new multimap by copying all pairs of
         key and value from x.

      ~multimap();
         The destructor.  Releases any allocated memory for	this multimap.

    ASSIGNMENT OPERATOR

      multimap<Key,	T, Compare, Allocator>&
      operator=(const multimap<Key,	T, Compare, Allocator>&	x);
         Replaces the contents of *this with a copy	of the multimap	x.

    ALLOCATOR

      allocator_type
      get_allocator() const;
         Returns a copy of the allocator used by self for storage
         management.

    ITERATORS

      iterator
      begin() ;
         Returns a bidirectional iterator pointing to the first element
         stored in	the multimap.  "First" is defined by the multimap's
         comparison operator, Compare.

      const_iterator
      begin() const;
         Returns a const_iterator pointing to the first element stored in
         the multimap. "First" is defined by the multimap's comparison
         operator,Compare.

      iterator
      end()	;
         Returns a bidirectional iterator pointing to the last element
         stored in the multimap, i.e. the off-the-end value.

      const_iterator
      end()	const;
         Returns a const_iterator pointing to the last element stored in
         the  multimap.

      reverse_iterator
      rbegin() ;
         Returns a reverse_iterator	pointing to the	first element stored
         in	the multimap. "First" is defined by the multimap's comparison
         operator, Compare.

      const_reverse_iterator
      rbegin() const;
         Returns a const_reverse_iterator pointing to the first element
         stored in the multimap.

      reverse_iterator
      rend() ;
         Returns a reverse_iterator	pointing to the	last element stored
         in the multimap, i.e., the off-the-end value.

      const_reverse_iterator
      rend() const;
         Returns a const_reverse_iterator pointing to the last element
         stored in the multimap.

    MEMBER FUNCTIONS

      void
      clear();
         Erases all	elements from the self.

      size_type
      count(const key_type&	x) const;
         Returns the number	of elements in the multimap with the key value
         x.

      bool
      empty() const;
         Returns true if the multimap is empty, false otherwise.

      pair<iterator,iterator>
      equal_range(const key_type& x);

      pair<const_iterator,const_iterator>
      equal_range(const key_type& x) const;
         Returns the pair (lower_bound(x), upper_bound(x)).

      iterator
      erase(iterator first,	iterator last);
         Providing the iterators first and last point to the same multimap
         and last is reachable from first, all elements in the range
         (first, last) will be deleted from the multimap. Returns an
         iterator  pointing to	the element following the last
         deleted	element, or end(),  if there were no elements after
         the	deleted	range.

      iterator
      erase(iterator position);
         Deletes the multimap element pointed to by	the iterator position.
         Returns an	iterator pointing to the element following the deleted
         element, or end(), if	the deleted item was the last one in
         this list.

      size_type
      erase(const key_type&	x);
         Deletes the elements with the key value x from the	map, if	any
         exist. Returns the number	of deleted elements, or	 0 otherwise.

      iterator
      find(const key_type& x);
         Searches the multimap for a pair with the key value x and	returns
         an iterator to that pair if it is found.  If such a pair is not
         found the value end()  is returned.

      const_iterator
      find(const key_type& x) const;
         Same as find above	but returns a const_iterator.

      iterator
      insert(const value_type& x);
      iterator
      insert(iterator position, const value_type& x);
         x is inserted into	the multimap.  A position may be supplied as a
         hint regarding where to	do the insertion.  If the insertion
         may	be done	right after position  then it takes amortized
         constant  time.  Otherwise it will take O(log N)	time.

      template <class InputIterator>
      void
      insert(InputIterator first, InputIterator last);
         Copies of each element in the range [first, last) will be
         inserted	into the multimap.  The	iterators first	and last must
         return values of type pair<T1,T2>.  This	operation takes
         approximately O(N*log(size()+N)) time.

      key_compare
      key_comp() const;
         Returns a function	object capable of comparing key	values using
         the comparison operation,	Compare, of the	current	multimap.

      iterator
      lower_bound(const key_type& x);
         Returns an	iterator to the	 first	multimap element whose key  is
         greater  than or equal to x.  If no such element exists then end()
         is returned.

      const_iterator
      lower_bound(const key_type& x) const;
         Same as lower_bound above but returns a const_iterator.

      size_type
      max_size() const;
         Returns the maximum possible size of the multimap.

      size_type
      size() const;
         Returns the number	of elements in the multimap.

      void
      swap(multimap<Key, T,	Compare, Allocator>& x);
         Swaps the contents	of the multimap	x with the current multimap,
         *this.

      iterator
      upper_bound(const key_type& x);
         Returns an	iterator to the	first element  whose key is less than
         or equal to x.  If no	such element exists, then end()	is
         returned.

      const_iterator
      upper_bound(const key_type& x) const;
         Same as upper_bound above but returns a const_iterator.

      value_compare
      value_comp() const;
         Returns a function	object capable of comparing value_types
         (key,value pairs) using the comparison operation, Compare, of
         the current multimap.

    NON-MEMBER OPERATORS

      bool
      operator==(const multimap<Key, T, Compare, Allocator>& x,
    	    const multimap<Key,	T, Compare, Allocator>&	y);
         Returns true if all  elements in	x are element-wise equal  to
         all elements in y, using	(T::operator==). Otherwise  it returns
         false.

      bool
      operator!=(const multimap<Key, T, Compare, Allocator>& x,
    	    const multimap<Key,	T, Compare, Allocator>&	y);
    	       Returns !(x==y).

      bool
      operator<(const multimap<Key,	T, Compare, Allocator>&	x,
    	    const multimap<Key,	T, Compare, Allocator>&	y);
    	       Returns true if x is lexicographically less than	y.
                   Otherwise, it	returns	false.

      bool
      operator>(const multimap<Key,	T, Compare, Allocator>&	x,
    	    const multimap<Key,	T, Compare, Allocator>&	y);
    	       Returns y < x.

      bool
      operator<=(const multimap<Key, T, Compare, Allocator>& x,
    	    const multimap<Key,	T, Compare, Allocator>&	y);
    	       Returns !(y < x).

      bool
      operator>=(const multimap<Key, T, Compare, Allocator>& x,
    	    const multimap<Key,	T, Compare, Allocator>&	y);
    	       Returns !(x < y).

    SPECIALIZED ALGORITHMS

      template<class Key, class T, class Compare, class Allocator>
      void swap(multimap<Key, T, Compare, Allocator>& a,
    	    multimap<Key, T, Compare, Allocator>& b);
    	       Efficiently swaps the contents of a and b.

    EXAMPLE

      //
      // multimap.cpp
      //
       #include <string>
       #include <map>
       #include <iostream.h>

      typedef multimap<int,	string,	less<int> > months_type;

       // Print out	a pair
      template <class First, class Second>
      ostream& operator<<(ostream& out,
    		      const pair<First,Second>&	p)
       {
        cout << p.second <<	" has "	<< p.first << "	days";
        return out;
       }

       // Print out	a multimap
      ostream& operator<<(ostream& out, months_type	l)
       {
        copy(l.begin(),l.end(), ostream_iterator
    	       <months_type::value_type,char>(cout,"0));
        return out;
       }

      int main(void)
       {
         //	create a multimap of months and	the number of
         //	days in	the month
        months_type	months;

        typedef months_type::value_type value_type;

         //	Put the	months in the multimap
        months.insert(value_type(31, string("January")));
        months.insert(value_type(28, string("February")));
        months.insert(value_type(31, string("March")));
        months.insert(value_type(30, string("April")));
        months.insert(value_type(31, string("May")));
        months.insert(value_type(30, string("June")));
        months.insert(value_type(31, string("July")));
        months.insert(value_type(31, string("August")));
        months.insert(value_type(30, string("September")));
        months.insert(value_type(31, string("October")));
        months.insert(value_type(30, string("November")));
        months.insert(value_type(31, string("December")));

         //	print out the months
        cout << "All months	of the year" <<	endl <<	months << endl;

         //	Find the Months	with 30	days
        pair<months_type::iterator,months_type::iterator> p	=
    	   months.equal_range(30);

         //	print out the 30 day months
        cout << endl << "Months with 30 days" << endl;
        copy(p.first,p.second,
          ostream_iterator<months_type::value_type,char>(cout,"0));

        return 0;
       }

      Output :
      All months of	the year
      February has 28 days
      April	has 30 days
      June has 30 days
      September has	30 days
      November has 30 days
      January has 31 days
      March	has 31 days
      May has 31 days
      July has 31 days
      August has 31	days
      October has 31 days
      December has 31 days

      Months with 30 days
      April	has 30 days
      June has 30 days
      September has	30 days
      November has 30 days

    WARNINGS

      Member function templates are	used in	all containers provided	by the
      Standard C++ Library.  An	example	of this	feature	is the constructor
      for multimap<Key,T,Compare,Allocator>  that takes	two templated
      iterators:

      template <class InputIterator>
      multimap (InputIterator, InputIterator,
    	    const Compare& = Compare(),
    	    const Allocator& = Allocator());

      multimap also	has an insert function of this type.  These functions,
      when not restricted by compiler limitations, allow	you to use any
      type of	input iterator as arguments. For compilers that do not
      support this	feature	we provide substitute functions that allow you
      to  use an	iterator obtained from the same	type of	container as
      the one you are constructing (or calling a member function on), or
      you	can use	a pointer to the type of element you have in the
      container.

      For example, if your compiler	does not support member	function
      templates you can construct a multimap in the following	two
      ways:

      multimap<int,int>::value_type	intarray[10];
      multimap<int,int> first_map(intarry, intarray	+ 10);
      multimap<int,int>
       second_multimap(first_multimap.begin(), first_multimap.end());

      but not this way:

      multimap<long,long>
       long_multimap(first_multimap.begin(),first_multimap.end());

      since	the long_multimap and first_multimap are not the same type.

      Also,	many compilers do not support default template arguments.  If
      your compiler is one of these you need to always supply the Compare
      template argument and the Allocator template argument.	For
      instance you'll have  to write:

      multimap<int,	int, less<int>,	allocator<int> >

      instead of:

      multimap<int,	int>

    SEE ALSO

      allocator, Containers, Iterators, map

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

    multiset
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      multiset  - An associative container providing fast access to
      stored key values.  Storage of duplicate	keys is	allowed.
      A multiset supports bidirectional	iterators.

    SYNOPSIS

      #include <set>

      template <class Key, class Compare = less<Key>,
    	   class Allocator = allocator<Key> >
      class	multiset;

    DESCRIPTION

      multiset <Key, Compare, Allocator> provides fast access to stored
      key values.  The default operation for key comparison is the <
      operator.  Insertion of duplicate keys is allowed with a multiset.

      multiset provides bidirectional iterators which point	to a stored
      key.

      Any type used	for the	template parameter  Key	must provide the
      following (where T is the type,	t is a value of	T and u	is a
      const value of T):

       Copy	constructors	T(t) and T(u)
       Destructor		t.~T()
       Address of		&t and &u yielding T* and
    			const T* respectively
       Assignment		t = a where a is a
    			 (possibly const) value	of T The type used
                             for the Compare template parameter must
                             satisfy the  requirements for binary
                             functions.

    INTERFACE

      template <class Key, class Compare = less<Key>,
    	   class Allocator = allocator<Key> >
      class	multiset {

      public:

      // typedefs

        typedef Key	key_type;
        typedef Key	value_type;
        typedef Compare key_compare;
        typedef Compare value_compare;
        typedef Allocator allocator_type;
        typename reference;
        typename const_reference;
        typename iterator;
        typename const_iterator;
        typename size_type;
        typename difference_type;
        typename reverse_iterator;
        typename const_reverse_iterator;

      // Construct/Copy/Destroy

        explicit multiset (const Compare& =	Compare(),
    		       const Allocator&	= Allocator());
        template <class InputIterator>
         multiset (InputIterator, InputIterator,
    	       const Compare& =	Compare(),
    	       const Allocator&	= Allocator());
        multiset (const multiset<Key, Compare, Allocator>&);
         ~multiset ();
        multiset<Key, Compare, Allocator>& operator= (const	multiset<Key,
    	      Compare,
    	      Allocator>&);

      // Iterators

        iterator begin ();
        const_iterator begin () const;
        iterator end ();
        const_iterator end () const;
        reverse_iterator rbegin ();
        const_reverse_iterator rbegin () const;
        reverse_iterator rend ();
        const_reverse_iterator rend	() const;

      // Capacity

        bool empty () const;
        size_type size () const;
        size_type max_size () const;

      // Modifiers

        iterator insert (const value_type&);
        iterator insert (iterator, const value_type&);
        template <class InputIterator>
         void insert (InputIterator, InputIterator);

        iterator erase (iterator);
        size_type erase (const key_type&);
        iterator erase (iterator, iterator);
        void swap (multiset<Key, Compare, Allocator>&);
        void clear ();

      // Observers

        key_compare	key_comp () const;
        value_compare value_comp ()	const;

      // Multiset operations

        iterator find (const key_type&) const;
        size_type count (const key_type&) const;
        iterator lower_bound (const	key_type&) const;
        iterator upper_bound (const	key_type&) const;
        pair<iterator, iterator> equal_range (const	key_type&) const;
         };

      // Non-member	Operators

      template <class Key, class Compare, class Allocator>
      bool operator==
          (const multiset<Key, Compare, Allocator>&,
          const multiset<Key, Compare, Allocator>&);

      template <class Key, class Compare, class Allocator>
      bool operator!=
          (const multiset<Key, Compare, Allocator>&,
          const multiset<Key, Compare, Allocator>&);

      template <class Key, class Compare, class Allocator>
      bool operator<
          (const multiset<Key, Compare, Allocator>&,
          const multiset<Key, Compare, Allocator>&);

      template <class Key, class Compare, class Allocator>
      bool operator>
          (const multiset<Key, Compare, Allocator>&,
          const multiset<Key, Compare, Allocator>&);

      template <class Key, class Compare, class Allocator>
      bool operator<=
          (const multiset<Key, Compare, Allocator>&,
          const multiset<Key, Compare, Allocator>&);

      template <class Key, class Compare, class Allocator>
      bool operator>=
          (const multiset<Key, Compare, Allocator>&,
          const multiset<Key, Compare, Allocator>&);

      // Specialized Algorithms

      template <class Key, class Compare, class Allocator>
      void swap ( multiset<Key, Compare, Allocator>&,
    	      multiset<Key, Compare, Allocator>&);

    CONSTRUCTOR AND	DESTRUCTOR

      explicit multiset(const Compare& comp	= Compare(),
    		    const Allocator& alloc = Allocator());
         Default	constructor.  Constructs an empty  multiset which
         will  use	the optional  relation comp to order keys, if	it is
         supplied,	and the	allocator alloc	for all storage management.

      template <class InputIterator>
      multiset(InputIterator first,	InputIterator last,
    	   const Compare& = Compare(),
    	   const Allocator& = Allocator());
         Constructs a multiset containing values in the range [first,
         last).

      multiset(const multiset<Key, Compare,	Allocator>& x);
         Copy constructor.	Creates	a new multiset	by copying all key
         values from x.

      ~multiset();
         The destructor.  Releases any allocated memory for	this multiset.

    ASSIGNMENT OPERATOR

      multiset<Key,	Compare, Allocator>&
      operator=(const multiset<Key,	Compare, Allocator>& x);
         Replaces the contents of *this with a copy	of the contents	of x.

    ALLOCATOR

      allocator_type
      get_allocator() const;
         Returns a copy of the allocator used by self for storage
         management.

    ITERATORS

      iterator
      begin();
         Returns an	iterator pointing to the first element stored in the
         multiset.  "First" is	defined	by the multiset's comparison
         operator,  Compare.

      const_iterator
      begin();
         Returns a const_iterator pointing to the first element stored in
         the multiset.

      iterator
      end();
         Returns an	iterator pointing to the last element stored in	the
         multiset, i.e., the off-the-end value.

      const_iterator
      end();
         Returns a const_iterator pointing to the last  element stored in
         the multiset, i.e., the off-the-end value.

      reverse_iterator
      rbegin();
         Returns a reverse_iterator	pointing to the	first element stored
         in	the multiset.	"First"	is defined by the multiset's
         comparison	operator, Compare.

      const_reverse_iterator
      rbegin();
         Returns a const_reverse_iterator pointing to the  first element
         stored in	the multiset.

      reverse_iterator
      rend();
         Returns a reverse_iterator	pointing to the	last element stored
         in the multiset, i.e., the off-the-end value.

      const_reverse_iterator
      rend();
         Returns a const_reverse_iterator pointing to the last element
         stored  in the multiset, i.e., the off-the-end value.

    MEMBER FUNCTIONS

      void
      clear();
         Erases all	elements from the self.

      size_type
      count(const key_type&	x) const;
         Returns the number	of elements in the multiset with the key value
         x.

      bool
      empty() const;
         Returns true if the multiset is empty, false otherwise.

      pair<iterator,iterator>
      equal_range(const key_type& x)const;
         Returns the pair (lower_bound(x), upper_bound(x)).

      size_type
      erase(const key_type&	x);
         Deletes all elements with the key value x from the	multiset, if
         any exist.  Returns the number	of deleted elements.

      iterator
      erase(iterator position);
         Deletes the multiset element pointed to by	the iterator position.
         Returns an	iterator pointing to the element following the deleted
         element, or end() if the deleted item	was the	last one in
         this  list.

      iterator
      erase(iterator first,	iterator last);
         Providing the iterators first and last point to the same multiset
         and last is reachable from first, all elements	in the range
         (first, last) will be deleted from the multiset.	Returns	an
         iterator pointing to	the element following the last
         deleted	element, or end() if there were	no elements after the
         deleted	range.

      iterator
      find(const key_type& x) const;
         Searches the multiset for a key value x and returns an iterator
         to	that key if it is found.  If such a value is not found the
         iterator end() is returned.

      iterator
      insert(const value_type& x);
      iterator
      insert(iterator position, const value_type& x);
         x is inserted into	the multiset.  A position may be supplied as a
         hint regarding where to	do the insertion.  If the insertion
         may	be done	right after position, then it takes amortized
         constant  time.  Otherwise,	it will take O(log N)	time.

      template <class InputIterator>
      void
      insert(InputIterator first, InputIterator last);
         Copies of each element in the range [first, last) will be
         inserted into the multiset.	 This insert takes
         approximately O(N*log(size()+N)) time.

      key_compare
      key_comp() const;
         Returns a function	object capable of comparing key	values using
         the comparison operation,	Compare, of the	current	multiset.

      iterator
      lower_bound(const key_type& x) const;
         Returns an	iterator to the	 first element whose key is greater
         than or equal to x.  If no	such element exists, end() is
         returned.

      size_type
      max_size() const;
         Returns the maximum possible size of the multiset size_type.

      size_type
      size() const;
         Returns the number	of elements in the multiset.

      void
      swap(multiset<Key, Compare, Allocator>& x);
         Swaps the contents	of the multiset	x with the current multiset,
         *this.

      iterator
      upper_bound(const key_type& x) const;
         Returns an	iterator to the	first  element whose key is smaller
         than or equal to x.  If no	such element exists then end() is
         returned.

      value_compare
      value_comp() const;
         Returns a function	object capable of comparing key	values using
         the comparison operation,	Compare, of the	current	 multiset.

    NON-MEMBER OPERATORS

      template <class Key, class Compare, class Allocator>
      operator==(const multiset<Key, Compare, Allocator>& x,
    	     const multiset<Key, Compare, Allocator>& y);
         Returns	true if	all  elements in x are element-wise  equal to
         all elements in	y, using (T::operator==).  Otherwise it
         returns	false.

      template <class Key, class Compare, class Allocator>
      operator!=(const multiset<Key, Compare, Allocator>& x,
    	     const multiset<Key, Compare, Allocator>& y);
    		Returns	!(x==y).

      template <class Key, class Compare, class Allocator>
      operator<(const multiset<Key,	Compare, Allocator>& x,
    	    const multiset<Key,	Compare, Allocator>& y);
    	       Returns true if x is lexicographically less than	y.
                   Otherwise, it returns false.

      template <class Key, class Compare, class Allocator>
      operator>(const multiset<Key,	Compare, Allocator>& x,
    	    const multiset<Key,	Compare, Allocator>& y);
    	       Returns y < x.

      template <class Key, class Compare, class Allocator>
      operator<=(const multiset<Key, Compare, Allocator>& x,
    	    const multiset<Key,	Compare, Allocator>& y);
    	       Returns !(y < x).

      template <class Key, class Compare, class Allocator>
      operator>=(const multiset<Key, Compare, Allocator>& x,
    	    const multiset<Key,	Compare, Allocator>& y);
    	       Returns !(x < y).

    SPECIALIZED ALGORITHMS

      template <class Key, class Compare, class Allocator>
      void swap(multiset<Key,Compare,Allocator>& a,
    	    multiset<Key,Compare,Allocator>&b);
    	       Efficiently swaps the contents of a and b.

    EXAMPLE

      //
      // multiset.cpp
      //
      #include <set>
      #include <iostream.h>

      typedef multiset<int,	less<int>, allocator> set_type;

      ostream& operator<<(ostream& out, const set_type& s)
       {
        copy(s.begin(),s.end(),
    	 ostream_iterator<set_type::value_type,char>(cout," "));
        return out;
       }

      int main(void)
       {
         //	create a multiset of ints
        set_type  si;
        int	 i;

        for	(int j = 0; j <	2; j++)
         {
          for(i = 0; i < 10; ++i) {
    	 // insert values with a hint
    	si.insert(si.begin(), i);
           }
         }

         //	print out the multiset
        cout << si << endl;

         //	Make another int multiset and an empty multiset
        set_type si2, siResult;
        for	(i = 0;	i < 10;	i++)
           si2.insert(i+5);
        cout << si2	<< endl;

         //	Try a couple of	set algorithms
        set_union(si.begin(),si.end(),si2.begin(),si2.end(),
    	   inserter(siResult,siResult.begin()));
        cout << "Union:" <<	endl <<	siResult << endl;

        siResult.erase(siResult.begin(),siResult.end());
        set_intersection(si.begin(),si.end(),
    	   si2.begin(),si2.end(),
    	   inserter(siResult,siResult.begin()));
        cout << "Intersection:" << endl << siResult	<< endl;

        return 0;
       }

      Output:
      0 0 1	1 2 2 3	3 4 4 5	5 6 6 7	7 8 8 9	9
      5 6 7	8 9 10 11 12 13	14
      Union:
      0 0 1	1 2 2 3	3 4 4 5	5 6 6 7	7 8 8 9	9 10 11	12 13 14
      Intersection:
      5 6 7	8 9

    WARNINGS

      Member function templates are	used in	all containers	provided by
      the	Standard C++ Library.  An	example	of this	feature	is the
      constructor for multiset<Key,	Compare, Allocator>, which takes two
      templated iterators:

      template <class InputIterator>
      multiset (InputIterator, InputIterator,
    	   const Compare& = Compare(),
    	   const Allocator& = Allocator());

      multiset also	has an insert function of  this	type.  These
      functions,	when not restricted by compiler limitations, allow
      you to use any  type of input iterator as arguments. For compilers
      that do not support this	feature, we provide substitute
      functions that allow you to use  an	iterator obtained from the
      same	type of	container as the one you  are constructing (or calling
      a member function on).  You can also	use a pointer to the type of
      element you have in the container.

      For example, if your compiler	does not support member	 function
      templates, you can construct a multiset in the following	two
      ways:

      int intarray[10];
      multiset<int>	first_multiset(intarray,
    						    intarray +10);
      multiset<int>
        second_multiset(first_multiset.begin(), first_multiset.end());

      but not this way:

      multiset<long>
        long_multiset(first_multiset.begin(),first_multiset.end());

      since	the long_multiset and first_multiset are not the  same type.

      Also,	many compilers do not support default template arguments.  If
      your compiler is one of these you need to always supply the Compare
      template argument and the Allocator template argument.	For
      instance, you'll have to  write:

      multiset<int,	less<int>, allocator<int> >

      instead of:

      multiset<int>

    SEE ALSO

      allocator, Containers, Iterators, set

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

    priority_queue
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      priority_queue  - A container	adapter	which behaves like a priority
      queue. Items	are popped from	the queue are in order with respect
      to a "priority."

    SYNOPSIS

      #include <queue>

      template <class T,
    	   class Container = vector<T>,
    	   class Compare = less<Container::value_type> >
      class	priority_queue;

    DESCRIPTION

      priority_queue is a container	adaptor	which allows a container to
      act	  as a priority queue.  This	means that the item with the
      highest  priority, as determined by	either the default comparison
      operator  (operator <) or the comparison Compare, is brought to the
      front of  the queue whenever anything is pushed onto or popped off
      the queue.

      priority_queue adapts	any container that  provides  front(),
      push_back() and pop_back().  In particular, deque	 and vector
      can	be used.

    INTERFACE

      template <class T,
    	   class Container = vector<T>,
    	   class Compare = less<typename Container::value_type>	>
      class	priority_queue {
      public:

      // typedefs
        typedef typename Container::value_type value_type;
        typedef typename Container::size_type size_type;
        typedef typename allocator_type allocator_type;

      //  Construct
        explicit priority_queue (const Compare& = Compare(),
    			     const allocator_type&=allocator_type());
        template <class InputIterator>
          priority_queue (InputIterator first,
    		      InputIterator last,
    		      const Compare& = Compare(),
    		      const allocator_type& = allocator_type());
        allocator_type get_allocator() const;
        bool empty () const;
        size_type size () const;
        const value_type& top () const;
        void push (const value_type&);
        void pop();
      };

    CONSTRUCTORS

      explicit priority_queue (const Compare& x = Compare(),
    	       const allocator_type& alloc = allocator_type());
    		  Default constructor.	Constructs a priority queue
                      that uses Container for	its underlying
                      implementation, x as its	standard for
                      determining priority, and the allocator alloc for
                      all storage management.

      template <class InputIterator>
      priority_queue (InputIterator	first, InputIterator last,
    	      const Compare& x = Compare(),
    	      const allocator_type& alloc = allocator_type());
         Constructs a new priority queue and places into it  every entity
         in the range [first, last).  The  priority_queue	will use x for
         determining the priority,  and  the allocator alloc  for all
         storage management.

    ALLOCATOR

      allocator_type get_allocator () const;
         Returns a copy of the allocator used by self for storage
         management.

    MEMBER FUNCTIONS

      bool
      empty	() const;
         Returns true if the priority_queue	is empty, false	otherwise.

      void
      pop();
         Removes the item with the highest priority	from the queue.

      void
      push (const value_type& x);
         Adds x to the queue.

      size_type
      size () const;
         Returns the number	of elements in the priority_queue.

      const	value_type&
      top () const;
         Returns a constant	reference to the element in the	queue with the
         highest priority.

    EXAMPLE

      //
      // p_queue.cpp
      //
       #include <queue>
       #include <deque>
       #include <vector>
       #include <string>
       #include <iostream.h>

      int main(void)
       {
         //	Make a priority	queue of int using a vector container
         priority_queue<int, vector<int>, less<int>	> pq;

         //	Push a couple of values
        pq.push(1);
        pq.push(2);

         //	Pop a couple of	values and examine the ends
        cout << pq.top() <<	endl;
        pq.pop();
        cout << pq.top() <<	endl;
        pq.pop();

         //	Make a priority	queue of strings using a deque container
         priority_queue<string, deque<string>, less<string>	>
           pqs;

         //	Push on	a few strings then pop them back off
        int	i;
        for	(i = 0;	i < 10;	i++)
         {
          pqs.push(string(i+1,'a'));
          cout << pqs.top()	<< endl;
         }
        for	(i = 0;	i < 10;	i++)
         {
          cout << pqs.top()	<< endl;
          pqs.pop();
         }

         //	Make a priority	queue of strings using a deque
         //	container, and greater as the compare operation
        priority_queue<string,deque<string>, greater<string> > pgqs;

         //	Push on	a few strings then pop them back off
        for	(i = 0;	i < 10;	i++)
         {
          pgqs.push(string(i+1,'a'));
          cout << pgqs.top() << endl;
         }

        for	(i = 0;	i < 10;	i++)
         {
          cout << pgqs.top() << endl;
          pgqs.pop();
         }

        return 0;
       }

      Output :
      2
      1
      a
      aa
      aaa
      aaaa
      aaaaa
      aaaaaa
      aaaaaaa
      aaaaaaaa
      aaaaaaaaa
      aaaaaaaaaa
      aaaaaaaaa
      aaaaaaaa
      aaaaaaa
      aaaaaa
      aaaaa
      aaaa
      aaa
      aa
      a
      a
      a
      a
      a
      a
      a
      a
      a
      a
      a
      a
      aa
      aaa
      aaaa
      aaaaa
      aaaaaa
      aaaaaaa
      aaaaaaaa
      aaaaaaaaa
      aaaaaaaaaa

    WARNING

      If your compiler does	not support default template parameters, you
      must always provide a Container template parameter, and a Compare
      template parameter  when declaring an instance	of
      priority_queue.  For	example, you would	not be able to write,

      priority_queue<int> var;

      Instead, you would have to write,

      priority_queue<int, vector<int>,
       less<typename vector<int>::value_type> > var;

    SEE ALSO

      Containers, queue

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

    queue
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      queue	 - A container adaptor that behaves like a queue (first	in,
      first out).

      This page describes ANSI queue class.	If you would like information
      on the Compaq C++ task queue class, use	the command:

           help cxxl

    SYNOPSIS

      #include <queue>

      template <class T, class Container = deque<T>	> class	queue ;

    DESCRIPTION

      The queue container adaptor lets a container function	as a queue.
      In	a queue, items are pushed into the back	of the container and
      removed from the front.  The first items pushed into the queue are
      the	first items to be popped off of	the queue (first in,  first
      out,	or "FIFO").

      queue	can adapt any container	that supports the front(), back(),
      push_back() and pop_front() operations.  In particular, deque	and
      list can be used.

    INTERFACE

      template <class T, class Container = deque<T>	>
      class	queue {

      public:

      // typedefs

        typedef typename Container::value_type value_type;
        typedef typename Container::size_type size_type;
        typedef typename Container::allocator_type allocator_type;

      // Construct/Copy/Destroy
        explicit queue (const allocator_type& = allocator_type());
        allocator_type get_allocator () const;

      // Accessors

        bool empty () const;
        size_type size () const;
        value_type&	front ();
        const value_type& front () const;
        value_type&	back ();
        const value_type& back () const;
        void push (const value_type&);
        void pop ();
      };

      // Non-member	Operators

      template <class T, class Container>
      bool operator== (const queue<T, Container>&,
    		   const queue<T, Container>&);

      template <class T, class Container>
      bool operator!= (const queue<T, Container>&,
    		   const queue<T, Container>&);

      template <class T, class Container>
      bool operator< (const	queue<T, Container>&,
    		  const	queue<T, Container>&);

      template <class T, class Container>
      bool operator> (const	queue<T, Container>&,
    		  const	queue<T, Container>&);

      template <class T, class Container>
      bool operator<= (const queue<T, Container>&,
    		  const	queue<T, Container>&);

      template <class T, class Container>
      bool operator>= (const queue<T, Container>&,
    		  const	queue<T, Container>&);

    CONSTRUCTORS

      explicit queue (const	allocator_type&	alloc= allocator_type());
         Creates a queue of	zero elements.	The queue will use the
         allocator alloc for all storage management.

    ALLOCATOR

      allocator_type get_allocator () const;
         Returns a copy of the allocator used by self for storage
         management.

    MEMBER FUNCTIONS

      value_type&
      back ();
         Returns a reference to the	item at	the back of the	queue (the
         last	item pushed into the queue).

      const	value_type&
      back() const;
         Returns a constant	reference to the item at the back of the queue
         as a const_value_type.

      bool
      empty	() const;
         Returns true if the queue is empty, otherwise false.

      value_type&
      front	();
         Returns a reference to the	item at	the front of the queue.	  This
         will be the first item pushed onto	the queue unless pop()  has
         been	called since then.

      const	value_type&
      front	() const;
         Returns a constant	reference to  the item at the front of the
         queue as a const_value_type.

      void
      pop ();
         Removes the item at the front of the queue.

      void
      push (const value_type& x);
         Pushes x onto the back of the queue.

      size_type
      size () const;
         Returns the number	of elements on the queue.

    NON-MEMBER OPERATORS

      template <class T, class Container>
       bool	operator== (const queue<T, Container>& x,
    		    const queue<T, Container>& y);
         Equality operator.  Returns true if x	is the  same as y.

      template <class T, class Container>
       bool	operator!= (const queue<T, Container>& x,
    		    const queue<T, Container>& y);
         Inequality operator.	Returns	!(x==y).

      template <class T, class Container>
       bool	operator< (const queue<T, Container>& x,
    		   const queue<T, Container>& y);
         Returns true if the queue	defined	by the  elements
         contained in	x is	lexicographically  less than the
         queue defined by the elements  contained	in y.

      template <class T, class Container>
       bool	operator> (const queue<T, Container>& x,
    		   const queue<T, Container>& y);
    		      Returns y	< x.

      template <class T, class Container>
       bool	operator< (const queue<T, Container>& x,
    		   const queue<T, Container>& y);
    		      Returns !(y < x).

      template <class T, class Container>
       bool	operator< (const queue<T, Container>& x,
    		   const queue<T, Container>& y);
    		      Returns !(x < y).

    EXAMPLE

      //
      // queue.cpp
      //
       #include <queue>
       #include <string>
       #include <deque>
       #include <list>
       #include <iostream.h>

      int main(void)
       {
         //	Make a queue using a list container
         queue<int,	list<int>> q;

         //	Push a couple of values	on then	pop them off
        q.push(1);
        q.push(2);
        cout << q.front() << endl;
        q.pop();
        cout << q.front() << endl;
        q.pop();

         //	Make a queue of	strings	using a	deque container
         queue<string,deque<string>> qs;

         //	Push on	a few strings then pop them back off
        int	i;
        for	(i = 0;	i < 10;	i++)
         {
          qs.push(string(i+1,'a'));
          cout << qs.front() << endl;
         }
        for	(i = 0;	i < 10;	i++)
         {
          cout << qs.front() << endl;
          qs.pop();
         }

        return 0;
       }

      Output :
      1
      2
      a
      a
      a
      a
      a
      a
      a
      a
      a
      a
      a
      aa
      aaa
      aaaa
      aaaaa
      aaaaaa
      aaaaaaa
      aaaaaaaa
      aaaaaaaaa
      aaaaaaaaaa

    WARNINGS

      If your compiler does	not support default template  parameters, you
      must always provide a Container template	parameter.  For
      example you would not be able to write:

      queue<int> var;

      rather, you would have to write,

      queue<int, deque<int>	> var;

    SEE ALSO

      allocator, Containers, priority_queue

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

    set
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      set  - An associative	container that supports	unique keys.  A	set
             supports bidirectional	iterators.

    SYNOPSIS

      #include <set>

      template <class Key, class Compare = less<Key>,
       class Allocator = allocator<Key> >
      class	set ;

    DESCRIPTION

      set<Key, Compare, Allocator> is an associative container that
      supports unique keys and provides for fast retrieval of the keys.  A
      set contains at most one of any key value.  The keys are sorted
      using	Compare.

      Since	a set maintains	a total	order on its elements, you cannot
      alter	the key values directly.	Instead, you must insert new
      elements with an insert_iterator.

      Any type used	for the	template parameter Key must provide the
      following (where T is the type,	t is a value of	T and u	is a
      const value of T):

       Copy	constructors	 T(t) and T(u)
       Destructor		 t.~T()
       Address of		 &t and	&u yielding T* and
    			 const T* respectively
       Assignment		 t = a where a is a
    			 (possibly const) value	of T

      The type used	for the	Compare	template parameter must	satisfy	the
      requirements	for binary functions.

    INTERFACE

      template <class Key, class Compare = less<Key>,
    	   class Allocator = allocator<Key> >
      class	set {

      public:

       // types

        typedef Key	key_type;
        typedef Key	value_type;
        typedef Compare key_compare;
        typedef Compare value_compare;
        typedef Allocator allocator_type;
        typename reference;
        typename const_reference;
        typename iterator;
        typename const_iterator;
        typename size_type;
        typename difference_type;
        typename reverse_iterator;
        typename const_reverse_iterator;

       // Construct/Copy/Destroy

        explicit set (const	Compare& = Compare(),
    		  const	Allocator& = Allocator ());
        template <class InputIterator>
         set (InputIterator, InputIterator,	const Compare& = Compare(),
    	  const	Allocator& = Allocator ());
        set	(const set<Key,	Compare, Allocator>&);
         ~set ();
        set<Key, Compare, Allocator>& operator= (const set <Key, Compare,
        Allocator>&);
        allocator_type get_allocator () const;

       // Iterators

        iterator begin ();
        const_iterator begin () const;
        iterator end ();
        const_iterator end () const;
        reverse_iterator rbegin ();
        const_reverse_iterator rbegin () const;
        reverse_iterator rend ();
        const_reverse_iterator rend	() const;

       // Capacity

        bool empty () const;
        size_type size () const;
        size_type max_size () const;

       // Modifiers

        pair<iterator, bool> insert	(const value_type&);
        iterator insert (iterator, const value_type&);
        template <class InputIterator>
         void insert (InputIterator, InputIterator);
        iterator erase (iterator);
        size_type erase (const key_type&);
        iterator erase (iterator, iterator);
        void swap (set<Key,	Compare, Allocator>&);
        void clear ();

       // Observers

        key_compare	key_comp () const;
        value_compare value_comp ()	const;

       // Set operations

        size_type count (const key_type&) const;
        pair<iterator, iterator> equal_range (const	 key_type&) const;
        iterator find (const key_type&) const;
        iterator lower_bound (const	key_type&) const;
        iterator upper_bound (const	key_type&) const

      };

       // Non-member Operators

      template <class Key, class Compare, class Allocator>
      bool operator== (const set<Key, Compare, Allocator>&,
    		   const set<Key, Compare, Allocator>&);

      template <class Key, class Compare, class Allocator>
      bool operator!= (const set<Key, Compare, Allocator>&,
    		   const set<Key, Compare, Allocator>&);

      template <class Key, class Compare, class Allocator>
      bool operator< (const	set<Key, Compare, Allocator>&,
    		  const	set<Key, Compare, Allocator>&);

      template <class Key, class Compare, class Allocator>
      bool operator> (const	set<Key, Compare, Allocator>&,
    		  const	set<Key, Compare, Allocator>&);

      template <class Key, class Compare, class Allocator>
      bool operator<= (const set<Key, Compare, Allocator>&,
    		  const	set<Key, Compare, Allocator>&);

      template <class Key, class Compare, class Allocator>
      bool operator>= (const set<Key, Compare, Allocator>&,
    		  const	set<Key, Compare, Allocator>&);

      // Specialized Algorithms

      template <class Key, class Compare, class Allocator>
      void swap (set <Key, Compare,	Allocator>&,
    	    set	<Key, Compare, Allocator>&);

    CONSTRUCTORS AND DESTRUCTORS

      explicit
      set(const Compare& comp = Compare(),
          const Allocator& alloc = Allocator());
    	 The default constructor.  Creates a set of zero elements.  If the
    	 function object comp is supplied, it is used to compare elements
             of the set.   Otherwise, the default function object in the
             template argument is used.  The	template argument
             defaults to less (<).	The allocator alloc is used for all
             storage management.

      template <class InputIterator>
      set(InputIterator first, InputIterator last,
          const Compare& comp = Compare()
          const Allocator& alloc = Allocator());
         Creates a set of length last -	first, filled with all values
         obtained by dereferencing the InputIterators on the range [first,
         last).	 If the	function object	comp is	supplied, it is	used
         to	compare elements of the set.  Otherwise, the default function
         object in the template argument is used.	 The template
         argument defaults	to less (<). Uses	the allocator  alloc
         for	all storage management.

      set(const set<Key, Compare, Allocator>& x);
         Copy constructor. Creates a copy of x.

      ~set();
         The destructor.  Releases any allocated memory for	self.

    ASSIGNMENT OPERATOR

      set<Key, Compare, Allocator>&
      operator=(const set<Key, Compare, Allocator>&	x);
         Assignment	operator.  Self	will share an implementation with x.
         Returns a reference to self.

    ALLOCATOR

      allocator_type
      get_allocator() const;
         Returns a copy of the allocator used by self for storage
         management.

    ITERATORS

      iterator
      begin();
         Returns an	iterator that points to	the first element in self.

      const_iterator
      begin() const;
         Returns a const_iterator that points to the first element in
         self.

      iterator
      end();
         Returns an	iterator that points to	the past-the-end value.

      const_iterator
      end()	const;
         Returns a const_iterator that points to the past-the-end value.

      reverse_iterator
      rbegin();
         Returns a reverse_iterator	that points to the past-the-end	value.

      const_reverse_iterator
      rbegin() const;
         Returns a const_reverse_iterator that points to the past-the-end
         value.

      reverse_iterator
      rend();
         Returns a reverse_iterator	that points to the first element.

      const_reverse_iterator
      rend() const;
         Returns a const_reverse_iterator that points to the first
         element.

    MEMBER FUNCTIONS

      void
      clear();
         Erases all	elements from the set.

      size_type
      count(const key_type&	x) const;
         Returns the number	of elements equal to x.	 Since a set supports
         unique keys, count will always return 1 or 0.

      bool
      empty() const;
         Returns true if the size is zero.

      pair<iterator, iterator>
      equal_range(const key_type&  x) const;
         Returns pair(lower_bound(x),upper_bound(x)).  The equal_range
         function indicates the valid range for insertion of x into the
         set.

      size_type
      erase(const key_type&	x);
         Deletes all the elements matching x.   Returns the	number of
         elements erased.  Since a set supports unique keys,	erase
         will always return  1 or 0.

      iterator
      erase(iterator position);
         Deletes the map element pointed to	by the iterator	position.
         Returns an iterator pointing to the element following	the
         deleted element, or end() if the deleted item was the last  one
         in this list.

      iterator
      erase(iterator first,	iterator last);
         Deletes the elements in the range (first, last). Returns an
         iterator pointing to the element following the last deleted
         element, or end() if there were	no elements after the deleted
         range.

      iterator
      find(const key_value&	x) const;
         Returns an	iterator that points to	the element equal to x.	 If
         there is no	such element, the iterator points to the
         past-the-end value.

      pair<iterator, bool>
      insert(const value_type& x);
         Inserts x into self according to the comparison function object.
         The template's	default	comparison function object is less
         (<).	If the insertion succeeds, it returns a pair composed
         of the iterator  position	where the insertion took	place,
         and true.   Otherwise, the pair contains the end value,	and
         false.

      iterator
      insert(iterator position, const value_type& x);
         x is inserted into	the set. A position may	be supplied as a hint
         regarding where to do the insertion. If the insertion may be done
         right after position then it takes amortized constant time.
         Otherwise it will take 0 (log N) time. The return value points
         to the inserted x.

      template <class InputIterator>
      void
      insert(InputIterator first, InputIterator last);
         Inserts copies of the elements in the range [first, last].

      key_compare
      key_comp() const;
         Returns the comparison function object for	the set.

      iterator
      lower_bound(const key_type& x) const;
         Returns an	iterator that points to	the first element that is
         greater than or equal to x.  If there is no such element, the
         iterator points  to the past-the-end value.

      size_type
      max_size() const;
         Returns size of the largest possible set.

      size_type
      size() const;
         Returns the number	of elements.

      void
      swap(set<Key,	Compare, Allocator>& x);
         Exchanges self with x.

      iterator
      upper_bound(const key_type& x) const
         Returns an	iterator that points to	the first element that is
         greater than or equal to x.  If there is no such element, the
         iterator points  to the past-the-end value.

      value_compare
      value_comp() const;
         Returns the set's comparison object. This is identical to the
         function key_comp().

    NON-MEMBER OPERATORS

      template <class Key, class Compare, class Allocator>
      bool operator==(const	set<Key, Compare, Allocator>& x,
    		   const set<Key, Compare, Allocator>& y);
         Equality operator. Returns true if x is the same as y.

      template <class Key, class Compare, class Allocator>
      bool operator!=(const	set<Key, Compare, Allocator>& x,
    		   const set<Key, Compare, Allocator>& y);
         Inequality operator. Returns !(x==y).

      template <class Key, class Compare, class Allocator>
      bool operator<(const set <Key, Compare, Allocator>& x,
    		 const set <Key, Compare, Allocator>& y);
         Returns true if the	elements contained in x	are lexico-
         graphically	less than the elements contained in y.

      template <class Key, class Compare, class Allocator>
      bool operator>(const set <Key, Compare, Allocator>& x,
    		 const set <Key, Compare, Allocator>& y);
    		    Returns y <	x.

      template <class Key, class Compare, class Allocator>
      bool operator<=(const	set <Key, Compare, Allocator>& x,
    		 const set <Key, Compare, Allocator>& y);
    		    Returns !(y	< x).

      template <class Key, class Compare, class Allocator>
      bool operator>=(const	set <Key, Compare, Allocator>& x,
    		 const set <Key, Compare, Allocator>& y);
    		    Returns !(x	< y).

    SPECIALIZED ALGORITHMS

      template <class Key, class Compare, class Allocator>
      void swap(set	<Key, Compare, Allocator>& a,
    	    set	<Key, Compare, Allocator>& b);
    	       Efficiently swaps the contents of a and b.

    EXAMPLE

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

      typedef set<double, less<double>, allocator<double> >	set_type;

      ostream& operator<<(ostream& out, const set_type& s)
       {
        copy(s.begin(), s.end(),
    	 ostream_iterator<set_type::value_type,char>(cout," "));
        return out;
       }

      int main(void)
       {
         //	create a set of	doubles
        set_type   sd;
        int		i;

        for(i = 0; i < 10; ++i) {
           // insert values
          sd.insert(i);
         }

         //	print out the set
        cout << sd << endl << endl;

         //	now let's erase	half of	the elements in	the set
        int	half = sd.size() >> 1;
        set_type::iterator sdi = sd.begin();
        advance(sdi,half);

        sd.erase(sd.begin(),sdi);

         //	print it out again
        cout << sd << endl << endl;

         //	Make another set and an	empty result set
        set_type sd2, sdResult;
        for	(i = 1;	i < 9; i++)
           sd2.insert(i+5);
        cout << sd2	<< endl;

         //	Try a couple of	set algorithms
        set_union(sd.begin(),sd.end(),sd2.begin(),sd2.end(),
    	      inserter(sdResult,sdResult.begin()));
        cout << "Union:" <<	endl <<	sdResult << endl;

        sdResult.erase(sdResult.begin(),sdResult.end());
        set_intersection(sd.begin(),sd.end(),
    		     sd2.begin(),sd2.end(),
    		     inserter(sdResult,sdResult.begin()));
        cout << "Intersection:" << endl << sdResult	<< endl;

        return 0;
       }

      Output :

      0 1 2	3 4 5 6	7 8 9
      5 6 7	8 9
      6 7 8	9 10 11	12 13
      Union:
      5 6 7	8 9 10 11 12 13
      Intersection:
      6 7 8	9

    WARNINGS

      Member function templates are	used in	all containers provided	by the
      Standard C++ Library.  An	example	of this	feature	is the
      constructor for set <Key,	Compare, Allocator> that takes two
      templated iterators:

      template <class InputIterator>
      set (InputIterator, InputIterator,
           const Compare& =	Compare(),
           const Allocator&	= Allocator());

      set also has an insert function of this type.	 These functions, when
      not restricted by	compiler limitations, allow you	to use any
      type	of input iterator as arguments.   For compilers that do not
      support this feature, we provide substitute functions that allow you
      to use an	iterator obtained from the same	type of	container as
      the one you are constructing (or calling a member function on), or
      you	can use	a pointer to the type of element you have in the
      container.

      For example, if your compiler	does not support member	function
      templates you can construct a set in the following two ways:

      int intarray[10];
      set<int> first_set(intarray, intarray	+ 10);
      set<int> second_set(first_set.begin(),
    					   first_set.end());

      but not this way:

      set<long> long_set(first_set.begin(),
    					   first_set.end());

      since	the long_set and first_set are not the same type.

      Also,	many compilers do not support default template arguments.  If
      your compiler is one of these you need to always supply the Compare
      template argument, and	the Allocator template argument. For
      instance, you need	to write	:

      set<int, less<int>, allocator<int> >

      instead of :

      set<int>

    SEE ALSO

         allocator, bidirectional_iterator, Cont ainer,
         lexicographical_compare

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

    Sequences
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      Sequences  - A sequence is a container that organizes	a set of
      objects, all the same type, into a	linear arrangement. vector,
      list, deque,  and string fall into this category.

      Sequences offer different complexity trade-offs.  vector offers fast
      inserts and deletes from the end of the container.  deque is useful
      when insertions and deletions will	take place at the beginning or
      end of the sequence.  Use list when there are frequent insertions
      and deletions from the middle of	the sequence.

    SEE ALSO

      For more information about sequences and their requirements, see
      the Containers section of this reference guide, or see the section
      on the specific container.

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

    stack
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      stack	 - A container adapter which behaves like a stack (last	in,
      first out).

    SYNOPSIS

      #include <stack>

      template <class T, class Container = deque<T>	>
      class	stack ;

    DESCRIPTION

      The stack container adapter causes a container to behave like	a
      "last	in, first	out" (LIFO)  stack.  The last item that	was
      put	("pushed") onto	the stack	is the first item removed
      ("popped" off).  The stack can adapt to any container that provides
      the operations, back(),  push_back(),	and pop_back().  In
      particular,  deque , list , and vector	can be used.

    INTERFACE

      template <class T, class Container = deque<T>	>
      class	stack {

      public:

      // typedefs

        typedef typename Container::value_type value_type;
        typedef typename Container::size_type size_type;
        typedef typename Container::allocator_type allocator_type

      // Construct

        explicit stack (const allocator_type& = allocator_type());
        allocator_type get_allocator () const;

      // Accessors

        bool empty () const;
        size_type size () const;
        value_type&	top ();
        const value_type& top () const;
        void push (const value_type&);
        void pop ();
      };

      // Non-member	Operators

      template <class T, class Container>
      bool operator== (const stack<T, Container>&,
    		   const stack<T, Container>&);

      template <class T, class Container>
      bool operator!= (const stack<T, Container>&,
    		   const stack<T, Container>&);

      template <class T, class Container>
      bool operator< (const	stack<T, Container>&,
    		  const	stack<T, Container>&);

      template <class T, class Container>
      bool operator> (const	stack<T, Container>&,
    		  const	stack<T, Container>&);

      template <class T, class Container>
      bool operator<= (const stack<T, Container>&,
    		  const	stack<T, Container>&);

      template <class T, class Container>
      bool operator>= (const stack<T, Container>&,
    		  const	stack<T, Container>&);

    CONSTRUCTOR

      explicit
      stack(const allocator_type& alloc = allocator_taype());
         Constructs	an empty stack.	The stack will use the allocator alloc
         for all storage management.

    ALLOCATOR

      allocator_type
      get_allocator() const;
           Returns a copy of the allocator used by self for	storage
           management.

    MEMBER FUNCTIONS

      bool
      empty() const;
         Returns true if the stack is empty, otherwise false.

      void
      pop();
         Removes the item at the top of the	stack.

      void
      push(const value_type& x);
         Pushes x onto the stack.

      size_type
      size() const;
         Returns the number	of elements on the stack.

      value_type&
      top();
         Returns a reference to the	item at	the top	of the stack.  This
         will be  the last item pushed onto the stack unless	pop()
         has been called since then.

      const	value_type&
      top()	const;
         Returns a constant	reference to the item at the top of the	stack
         as a const value_type.

    NON-MEMBER OPERATORS

      template <class T, class Container>
       bool	operator==(const stack<T, Container>& x,
    		    const stack<T, Container>& y);
         Equality	operator.  Returns true	if x is	the same as y.

      template <class T, class Container>
       bool	operator!=(const stack<T, Container>& x,
    		    const stack<T, Container>& y);
         Inequality operator.  Returns !(x==y).

      template <class T, class Container>
       bool	operator<(const	stack<T, Container>& x,
    		   const stack<T, Container>& y);
         Returns true if the stack	defined	by the elements	contained in
         x is lexicographically less than  the stack defined by the
         elements of y.

      template <class T, class Container>
       bool	operator>(const	stack<T, Container>& x,
    		   const stack<T, Container>& y);
    		      Returns y	< x.

      template <class T, class Container>
       bool	operator<=(const stack<T, Container>& x,
    		   const stack<T, Container>& y);
    		      Returns !(y < x).

      template <class T, class Container>
       bool	operator>=(const stack<T, Container>& x,
    		   const stack<T, Container>& y);
    		      Returns !(x < y).

    EXAMPLE

      //
      // stack.cpp
      //
       #include <stack>
       #include <vector>
       #include <deque>
       #include <string>
       #include <iostream.h>

      int main(void)
       {
         //	Make a stack using a vector container
         stack<int,vector<int> > s;

         //	Push a couple of values	on the stack
        s.push(1);
        s.push(2);
        cout << s.top() << endl;

         //	Now pop	them off
        s.pop();
        cout << s.top() << endl;
        s.pop();

         //	Make a stack of	strings	using a	deque
         stack<string,deque<string>	> ss;

         //	Push a bunch of	strings	on then	pop them off
        int	i;
        for	(i = 0;	i < 10;	i++)
         {
          ss.push(string(i+1,'a'));
          cout << ss.top() << endl;
         }
        for	(i = 0;	i < 10;	i++)
         {
          cout << ss.top() << endl;
          ss.pop();
         }

        return 0;
       }
      Output :
      2
      1
      a
      aa
      aaa
      aaaa
      aaaaa
      aaaaaa
      aaaaaaa
      aaaaaaaa
      aaaaaaaaa
      aaaaaaaaaa
      aaaaaaaaaa
      aaaaaaaaa
      aaaaaaaa
      aaaaaaa
      aaaaaa
      aaaaa
      aaaa
      aaa
      aa
      a

    WARNINGS

      If your compiler does	not support template parameter defaults,  you
      are required to supply a template	parameter for Container.   For
      example:

      You would not	be able	to write,

      stack<int> var;

      Instead, you would have to write,

      stack<int, deque<int>	> var;

    SEE ALSO

      allocator, Containers, deque,	list, vector

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

    vector
    			   Standard C++	Library
    		 Copyright 1996, Rogue Wave Software, Inc.

    NAME

      vector  - Sequence that supports random access iterators.

      This page describes the ANSI vector class.  If you would like
      information on the pre-ANSI vector class,	use the	command:

           help cxxl

    SYNOPSIS

      #include <vector>

      template <class T, class Allocator = allocator<T> >
      class	vector ;

    DESCRIPTION

      vector<T, Allocator> is a type of sequence that supports random
      access iterators.  In addition, it supports amortized constant time
      insert and erase	operations at the end.	Insert and erase in
      the	middle take linear time.	 Storage management is handled
      automatically.  In vector, iterator is a random access iterator
      referring to	T.  const_iterator is a	constant random access
      iterator  that returns a const T& when being dereferenced.	A
      constructor for  iterator and const_iterator is guaranteed.
      size_type	is an unsigned integral type.  difference_type is a
      signed integral	type.

      Any type used	for the	template parameter T must provide  the
      following (where T is the type,	t is a value of	T and u	is a
      const value of T):

      Default constructor	T()
       Copy	constructors	 T(t) and T(u)
       Destructor		 t.~T()
       Address of		 &t and	&u yielding T* and
    			  const	T* respectively
       Assignment		 t = a where a is a
    			  (possibly const) value of T

    SPECIAL	CASE

      Vectors of bit values	(boolean 1/0 values) are handled as a special
      case by the standard library,	so that	they can be efficiently	packed
      several elements	to a word.  The	operations for a boolean
      vector,  vector<bool>, are a superset of those for	an ordinary
      vector, only  the implementation is more efficient.

      Two member functions are available to	the boolean vector data	type.
      One is flip(), which inverts all the bits	of the vector.
      Boolean	vectors	also return as reference an internal value
      that also  supports the flip() member function.  The other
      vector<bool>-specific  member function is	a second form of the
      swap()	function

    INTERFACE

      template <class T, class Allocator = allocator<T> >
      class	vector {

      public:

       // Types

        typedef T value_type;
        typedef Allocator allocator_type;
        typename reference;
        typename const_reference;
        typename iterator;
        typename const_iterator;
        typename size_type;
        typename difference_type;
        typename reverse_iterator;
        typename const_reverse_iterator;

       // Construct/Copy/Destroy

        explicit vector (const Allocator& =	Allocator());
        explicit vector (size_type,	const Allocator& = Allocator ());
        vector (size_type, const T&, const Allocator& = Allocator());
        vector (const vector<T, Allocator>&);
        template <class InputIterator>
         vector (InputIterator, InputIterator,
    	     const Allocator& =	Allocator ());
         ~vector ();
        vector<T,Allocator>& operator= (const vector<T, Allocator>&);
        template <class InputIterator>
         void assign (InputIterator	first, InputIterator last);
        template <class Size, class	TT>
         void assign (Size n);
        template <class Size, class	TT>
         void assign (Size n, const	TT&);
        allocator_type get_allocator () const;

       // Iterators

        iterator begin ();
        const_iterator begin () const;
        iterator end ();
        const_iterator end () const;
        reverse_iterator rbegin ();
        const_reverse_iterator rbegin () const;
        reverse_iterator rend ();
        const_reverse_iterator rend	() const;

       // Capacity

        size_type size () const;
        size_type max_size () const;
        void resize	(size_type);
        void resize	(size_type, T);
        size_type capacity () const;
        bool empty () const;
        void reserve (size_type);

       // Element Access

        reference operator[] (size_type);
        const_reference operator[] (size_type) const;
        reference at (size_type);
        const_reference at (size_type) const;
        reference front ();
        const_reference front () const;
        reference back ();
        const_reference back () const;

       // Modifiers

        void push_back (const T&);
        void pop_back ();
        iterator insert (iterator);
        iterator insert (iterator, const T&);
        void insert	(iterator, size_type, const T&);
        template <class InputIterator>
         void insert (iterator, InputIterator, InputIterator);
        iterator erase (iterator);
        iterator erase (iterator, iterator);
        void swap (vector<T, Allocator>&);

      };

       // Non-member Operators

      template <class T>
      bool operator== (const vector<T,Allocator>&,
    		   const vector	<T,Allocator>&);

      template <class T>
      bool operator!= (const vector<T,Allocator>&,
    		   const vector	<T,Allocator>&);

      template <class T>
      bool operator< (const	vector<T,Allocator>&,
    		  const	vector<T,Allocator>&);

      template <class T>
      bool operator> (const	vector<T,Allocator>&,
    		  const	vector<T,Allocator>&);

      template <class T>
      bool operator<= (const vector<T,Allocator>&,
    		  const	vector<T,Allocator>&);

      template <class T>
      bool operator>= (const vector<T,Allocator>&,
    		  const	vector<T,Allocator>&);

      // Specialized Algorithms

      template <class T, class Allocator>
      void swap (const vector<T,Allocator>&, const vector<T,Allocator>&);

    CONSTRUCTORS AND DESTRUCTORS

      explicit vector(const	Allocator& alloc = Allocator());
         The default constructor.  Creates a vector	of length zero.	The
         vector will use the allocator alloc for all storage management.

      explicit vector(size_type n,
    		  const	Allocator& alloc = Allocator());
         Creates a vector of length	n, containing n	copies  of the default
         value for type T. Requires	that T  have a default constructor.
         The vector will use  the allocator alloc for all storage
         management.

      vector(size_type n, const T& value,
    	 const Allocator& alloc	= Allocator());
         Creates a vector of	length n, containing n copies of
         value.	  The vector will	use the	allocator alloc	for
         all	storage	management.

      vector(const vector<T, Allocator>& x);
         Creates a copy of x.

      template <class InputIterator>
      vector(InputIterator first, InputIterator last,
    	 const Allocator& alloc	= Allocator());
         Creates a vector of	length last - first, filled with all
         values obtained by	dereferencing the InputIterators on the	range
         [first, last). The vector will use the allocator alloc  for all
         storage management.

      ~vector();
         The destructor.  Releases any allocated memory for	this vector.

    ITERATORS

      iterator
      begin();
         Returns a random access iterator that points to the first
         element.

      const_iterator
      begin() const;
         Returns a random access const_iterator that points	to the first
         element.

      iterator
      end();
         Returns a random access iterator that points to the past-the-end
         value.

      const_iterator
      end()	const;
         Returns a random access const_iterator that points	to the
         past-the-end value.

      reverse_iterator
      rbegin();
         Returns a random access reverse_iterator that points to the
         past-the-end value.

      const_reverse_iterator
      rbegin() const;
         Returns a random access const_reverse_iterator that points	to the
         past-the-end value.

      reverse_iterator
      rend();
         Returns a random access reverse_iterator that points to the first
         element.

      const_reverse_iterator
      rend() const;
         Returns a random access const_reverse_iterator that points	to the
         first element.

    ASSIGNMENT OPERATOR

      vector<T, Allocator>&
      operator=(const vector<T, Allocator>&	x);
         Erases all	elements in self then inserts into self	a copy of each
         element in x.	 Returns a reference to	self.

    ALLOCATOR

      allocator_type
      get_allocator() const;
         Returns a copy of the allocator used by self for storage
         management.

    REFERENCE OPERATORS

      reference
      operator[](size_type n);
         a reference to element n of self.	The result can be used
         as  an lvalue.  The index	n must be between 0 and	the size less
         one.

      const_reference
      operator[](size_type n) const;
         Returns a constant	reference to element n of self.	The index n
         must  be between 0 and the size less one.

    MEMBER FUNCTIONS

      template <class InputIterator>
      void
      assign(InputIterator first, InputIterator last);
         Erases all	elements contained in self, then inserts new elements
         from the range [first, last).

      template <class Size,	class T>
      void
      assign(Size n, const T& t);
         Erases all	elements contained in self, then inserts n instances
         of	the default value of  type T.

      template <class Size,	class T>
      void
      assign(Size n, const T& t);
         Erases all	elements contained in self, then inserts n instances
         of	the value of t.

      reference
      at(size_type n);
         Returns a reference to element n of self.	 The result can	be
         used	as  an lvalue.  The index	n must be between 0
         and	the size less one.

      const_reference
      at(size_type)	const;
         Returns a constant	reference to element n of self.	The index n
         must  be between 0 and the size less one.

      reference
      back();
         Returns a reference to the	last element.

      const_reference
      back() const;
         Returns a constant	reference to the last element.

      size_type
      capacity() const;
         Returns the size of the allocated storage,	as the number of
         elements that can be stored.

      void
      clear() ;
         Deletes all elements from the vector.

      bool
      empty() const;
         Returns true if the size is zero.

      iterator
      erase(iterator position);
         Deletes the vector	element	pointed	to by the iterator position.
         Returns an	iterator pointing to the element following the deleted
         element,	or end() if the deleted element was the last one in
         this  vector.

      iterator
      erase(iterator first,	iterator last);
         Deletes the vector	elements in the	range (first, last).  Returns
         an iterator pointing to the element following	the last
         deleted element,  or end() if there were no elements in	the
         deleted range.

      void
      flip();
         Flips all the bits	in the vector.	This member function is	only
         defined for vector<bool>.

      reference
      front();
         Returns a reference to the	first element.

      const_reference
      front() const;
         Returns a constant	reference to the first element.

      iterator
      insert(iterator position);
         Inserts x before position.	 The return value  points to the
         inserted x.

      iterator
      insert(iterator position, const T& x);
         Inserts x before position.	 The return value  points to the
         inserted x.

      void
      insert(iterator position, size_type n, const	T& x);
         Inserts n copies of x before position.

      template <class InputIterator>
      void
      insert(iterator position, InputIterator first,
    	 InputIterator last);
    	    Inserts copies of the elements in the range	[first,	last]
                before position.

      size_type
      max_size() const;
         Returns size() of the largest possible vector.

      void
      pop_back();
         Removes the last element of self.

      void
      push_back(const T& x);
         Inserts a copy of x to the	end of self.

      void
      reserve(size_type n);
         Increases the capacity of self in anticipation of adding new
         elements. reserve itself does not add any new elements.  After a
         call to reserve, capacity()	is greater than	or equal to n
         and subsequent insertions	will not cause a reallocation until
         the	size of	the vector exceeds n.  Real location does not
         occur if	n is less than capacity().  If reallocation does
         occur, then all  iterators and	references pointing to
         elements	in the vector	are invalidated.  reserve takes	at
         most	linear time in the size of self.

      void
      resize(size_type sz);
         Alters the	size of	self.  If the new size (sz) is greater than
         the current size, then	sz-size() instances of the default
         value  of type T are inserted at the end of	the vector.
         If	the new	size is	smaller	than the current capacity, then	the
         vector is  truncated	by erasing size()-sz elements off the
         end. If sz is equal  to capacity then no action is taken.

      void
      resize(size_type sz, T c);
         Alters the	size of	self.  If the new size (sz) is greater than
         the current size, then	sz-size() c's are inserted at the end
         of the  vector. If	the new	size is	smaller	than the current
         capacity, then	the vector is truncated by erasing size()-sz
         elements off the end.  If sz	is equal to capacity then no
         action is	taken.

      size_type
      size() const;
         Returns the number	of elements.

      void
      swap(vector<T, Allocator>& x);
         Exchanges self with x, by swapping	all elements.

      void
      swap(reference x, reference y);
         Swaps the values of x and y.  This	is a member function of
         vector<bool> only.

    NON-MEMBER OPERATORS

      template <class T, class Allocator>
      bool operator==(const	vector<T, Allocator>& x,
    		  const	vector<T, Allocator>& y);
    		     Returns true if x is the same as y.

      template <class T, class Allocator>
      bool operator!=(const	vector<T, Allocator>& x,
    		  const	vector<T, Allocator>& y);
    		     Returns !(x==y).

      template <class T>
      bool operator<(const vector<T, Allocator>& x,
    		 const vector<T, Allocator>& y);
    		    Returns true if the	elements contained in x	are lexico-
    		    graphically	less than the elements contained in y.

      template <class T>
      bool operator>(const vector<T, Allocator>& x,
    		 const vector<T, Allocator>& y);
    		    Returns y <	x.

      template <class T>
      bool operator<=(const	vector<T, Allocator>& x,
    		 const vector<T, Allocator>& y);
    		    Returns !(y	< x).

      template <class T>
      bool operator>=(const	vector<T, Allocator>& x,
    		 const vector<T, Allocator>& y);
    		    Returns !(x	< y).

    SPECIALIZED ALGORITHMS

      template <class T, class Allocator>
      void swap(vector <T, Allocator>& a, vector <T, Allocator>& b);
         Efficiently swaps the contents of a and b.

    EXAMPLE

      //
      // vector.cpp
      //
       #include <vector>
       #include <iostream.h>
      ostream& operator<< (ostream&	out,
    		       const vector<int, allocator>& v)
       {
        copy(v.begin(), v.end(), ostream_iterator<int,char>(out," "));
        return out;
       }
      int main(void)
       {
         //	create a vector	of doubles
         vector<int>	 vi;
        int			i;
        for(i = 0; i < 10; ++i) {
           // insert values	before the beginning
          vi.insert(vi.begin(), i);
         }
         //	print out the vector
        cout << vi << endl;
         //	now let's erase	half of	the elements
        int	half = vi.size() >> 1;
        for(i = 0; i < half; ++i) {
          vi.erase(vi.begin());
         }
         //	print ir out again
        cout << vi << endl;
        return 0;
       }
      Output :

      9 8 7	6 5 4 3	2 1 0
      4 3 2	1 0

    WARNINGS

      Member function templates are	used in	all containers provided	by the
      Standard C++ Library.  An	example	of this	feature	is the
      constructor  for vector<T, Allocator> that takes two templated
      iterators:

      template <class InputIterator>
      vector (InputIterator, InputIterator,
    	  const	Allocator = Allocator());

      vector also has an insert function of	this type.  These functions,
      when  not restricted by	compiler limitations, allow you	to use
      any type	of input iterator as arguments.   For compilers that
      do not support  this feature we provide substitute functions that
      allow you to use an	iterator obtained from the same	type of
      container as the one you  are constructing (or calling a member
      function on), or you	can use	a  pointer to the type of element you
      have in the container.

      For example, if your compiler	does not support member	function
      templates you can construct a vector in	the following two
      ways:

      int intarray[10];
      vector<int> first_vector(intarray, intarray +	10);
      vector<int> second_vector(first_vector.begin(),
    				      first_vector.end());

      but not this way:

      vector<long>
      long_vector(first_vector.begin(),first_vector.end());

      since	the long_vector	and first_vector are not the same type.

      Additionally,	if your	compiler does not support default template
      parameters,	you will need to supply	the Allocator template
      argument.  For instance, you	will need to write :

      vector<int, allocator<int> >

      instead of :

      vector<int>

    SEE ALSO

      allocator, Containers, Iterators, lexicographical_compare

    STANDARDS CONFORMANCE
      ANSI X3J16/ISO WG21 Joint C++	Committee

|  | privacy statement and legal notices