[ First ]  [ Previous ]  [ Next ]  [ Last ]  [ Manuals ]

 

Chapter 8.

 

23 Containers Library


Containers are used to store and manipulate collections of information.


Overview of Containers library

The containers library is divided into four parts.


23.1 Container Requirements

Container objects store other objects and control the allocation and de-allocation of those objects. There are five classes implementing these requirements.


All containers must meet basic requirements.

The swap(), equal() and lexicographical_compare() algorithms are defined in the algorithm library for more information see "Overview of Algorithms Library."

The member function size() returns the number of elements in a container.

The member function begin() returns an iterator to the first element and end returns an iterator to the last element.

If begin() equals end() the container is empty.

Copy constructors for container types copy and allocator argument from their first parameter. All other constructors take an Allocator reference argument.

The member function get_allocator() returns a copy of the Allocator object used in construction of the container.

If an iterator type of the container is bi-directional or a random access iterator the container is reversible.


Unless specified containers meet these requirements.

If an exception is thrown by an insert() function while inserting a single element, that function has no effects.

If an exception is thrown by a push_back() or push_front() function, that function has no effects.

The member functions erase(), pop_back() or pop_front() do not throw an exception.

None of the copy constructors or assignment operators of a returned iterator throw an exception.

The member function swap() does not throw an exception, Except if an exception is thrown by the copy constructor or assignment operator of the container's compare object.

The member function swap() does not invalidate any references, pointers, or iterators referring to the elements of the containers being swapped.


23.1.1 Sequences Requirements

A sequence is a kind of container that organizes a finite set of objects, all of the same type, into a strictly linear arrangement.

The Library includes three kinds of sequence containers vector, lists, deque and adaptors classes


Additional Requirements

The iterator and const_iterator types for sequences must be at least of the forward iterator category.

The iterator returned from a.insert(p,t) points to the copy of t inserted into a.

The iterator returned from a.erase(q) points to the element immediately following q prior to the element being erased.

If no prior element exists for a.erase then a.end() is returned.

The previous conditions are true for a.erase(q1,q2) as well.

For every sequence defined in this clause the constructor


  template <class InputIterator>   X(InputIterator f, InputIterator l,
   const Allocator& a = Allocator())

shall have the same effect as:


  X(static_cast<typename X::size_type>(f),   static_cast<typename X::value_type>(l),a)

if InputIterator is an integral type.

Member functions in the forms:


  template <class InputIterator>   rt fx1(iterator p, InputIterator f, InputIterator l);

  template <class InputIterator>   rt fx2(InputIterator f, InputIterator l);

  template <class InputIterator>   rt fx3(iterator i1, iteraror i2, InputIterator f, InputIterator l);

shall have the same effect, respectively, as:


  fx1(p, static_cast<typename X::size_type>(f),   static_cast<typename X::value_type>(l));

  fx2(static_cast<typename X::size_type>(f),   static_cast<typename X::value_type>(l));

  fx3(i1, i2, static_cast<typenameX::size_type>(f),   static_cast<typename X::value_type>(l));

if InputIterator is an integral type.

The member function at() provides bounds-checked access to container elements.

The member function at() throws out_of_range if n >= a.size().


23.1.2 Associative Containers Requirements

Associative containers provide an ability for optimized retrieval of data based on keys.

Associative container are parameterized on Key and an ordering relation. Furthermore, map and multimap associate an arbitrary type T with the key.

The phrase "equivalence of keys" means the equivalence relation imposed by the comparison and not the operator == on keys.

An associative container supports both unique keys as well as support fir equivalent keys.

The classes set and map support unique keys.

The classes multiset and multimap support equivalent keys.

An iterator of an associative container must be of the bidirectional iterator category.

The insert members shall not affect the validity of iterators..

Iterators of associative containers iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them.


23.2 Sequences

The sequence libraries consist of several headers.


23.2.1 Template Class Deque

A deque is a kind of sequence that supports random access iterators. The deque class also supports insert and erase operations at the beginning middle or the end. However, deque is especially optimized for pushing and popping elements at the beginning and end.

A deque satisfies all of the requirements of a container and of a reversible container as well as of a sequence.

Template Class Deque Synopsis: 

namespace std {
template <class T, class Allocator = allocator<T> >
class deque {
public:
typedef typename Allocator::reference 	reference 
typedef typename Allocator::const_reference	 const_reference
// Implementation defined types
typedef  	iterator;
typedef 	const_iterator; 
typedef 	size_type; 
typedef 	difference_type; 
typedef  T 	value_type; 
typedef Allocator allocator_type; 
typedef typename Allocator::pointer pointer; 
typedef typename Allocator::const_pointer const_pointer;
typedef std::reverse_iterator<iterator> reverse_iterator; 
typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 
 
explicit deque
	(const Allocator& = Allocator());
explicit deque
	(size_type n, const T& value = T(), 
	const Allocator& = Allocator()); 
template <class InputIterator>
deque
	(InputIterator first, InputIterator last,
	const Allocator& = Allocator());
deque(const deque<T,Allocator>& x);
~deque();

deque<T,Allocator>& operator=
	(const deque<T,Allocator>& x);
template <class InputIterator> void assign
	(InputIterator first, InputIterator last);
void assign(size_type n, const T& t);
allocator_type get_allocator() const;
// iterators:
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 sz, T c = T());
bool empty() const;
// element access
reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference at(size_type n);
const_reference at(size_type n) const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// Modifiers
void push_front(const T& x);
void push_back(const T& x);
iterator insert(iterator position, const T& x);
void insert(iterator position, size_type n, const T& x);
template <class InputIterator> void insert 
	(iterator position, InputIterator first, InputIterator last); 
void pop_front();
void pop_back();
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
void swap(deque<T,Allocator>&);
void clear();
};

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

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

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

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

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

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

template <class T, class Allocator>
void swap
	(deque<T,Allocator>& x, deque<T,Allocator>& y);
}

23.2.1.1 Constructors

The deque constructor creates an object of the class deque.

Prototype: 

explicit deque(const Allocator& = Allocator());


explicit deque(size_type n, const T& value = T(),
  const Allocator& = Allocator()); 
template <class InputIterator>
  deque(InputIterator first, InputIterator last,
  const Allocator& = Allocator());

assign

The assign function is overloaded to allow various types to be assigned to a deque.

Prototype: 

template <class InputIterator>
  void assign
  (InputIterator first, InputIterator last); 
void assign(size_type n, const T& t);

23.2.1.2 Deque Capacity

The class deque has one member function to resize the deque.


resize

This function resizes the deque.

Prototype:

void resize(size_type sz, T c = T());


23.2.1.3 Deque Modifiers

The deque class has member functions to modify the deque.


insert

The insert function is overloaded to insert a value into deque.

Prototype: 

iterator insert(iterator position, const T& x);


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


void insert
  (iterator position,InputIterator first,
  InputIterator last);

erase

An overloaded function that allows the removal of a value at a position.

Prototype: 

iterator erase(iterator position);


iterator erase(iterator first, iterator last);
Return:

An iterator to the position erased.

:

23.2.1.4 Deque Specialized Algorithms

Deque has one specialize swap function.


swap

Swaps the element at one position with another.

Prototype: 

template <class T, class Allocator>
  void swap
  (deque<T,Allocator>& x,deque<T,Allocator>& y);

23.2.2 Template Class List

A list is a sequence that supports bidirectional iterators and allows insert and erase operations anywhere within the sequence.

In a list fast random access to list elements is not supported.

A list satisfies all of the requirements of a container as well as those of a reversible container and of a sequence except for operator[] and the member function at which are not included.

Template Class List Synopsis: 

namespace std {
template <class T, class Allocator = allocator<T> >
class list {
public:
//Defined types: 
typedef typename Allocator::reference 	reference; 
typedef typename Allocator::const_reference 	const_reference; 
//implementation defined 
typedef 	iterator;  
typedef 	 const_iterator; 
typedef 	size_type; 
typedef 	difference_type;
typedef T 	value_type; 
typedef Allocator 	allocator_type; 
typedef typename Allocator::pointer 	pointer; 
typedef typename Allocator::const_pointer 	const_pointer; 
typedef std::reverse_iterator<iterator> 	reverse_iterator; 
typedef std::reverse_iterator<const_iterator>
	const_reverse_iterator; 

explicit list(const Allocator& = Allocator());
explicit list(size_type n, const T& value = T(),
	const Allocator& = Allocator()); 
template <class InputIterator>
list(InputIterator first, InputIterator last,
	const Allocator& = Allocator()); 
list(const list<T,Allocator>& x);
~list();
list<T,Allocator>& operator=(const list<T,Allocator>& x);
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
void assign(size_type n, const T& t);
allocator_type get_allocator() const;

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;

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

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

void push_front(const T& x);
void pop_front();
void push_back(const T& x);
void pop_back();
iterator insert(iterator position, const T& x);
void insert(iterator position, size_type n, const T& x);
template <class InputIterator>
void insert
	(iterator position, InputIterator first,InputIterator last); 
iterator erase(iterator position);
iterator erase(iterator position, iterator last);
void swap(list<T,Allocator>&);
void clear();

void splice(iterator position, list<T,Allocator>& x);
void splice(iterator position, list<T,Allocator>& x, iterator i);
void splice(iterator position, list<T,Allocator>& x, 
	iterator first, iterator last);
void remove(const T& value);
template <class Predicate> void remove_if(Predicate pred);
void unique();
template <class BinaryPredicate> 
void unique(BinaryPredicate binary_pred); 
void merge(list<T,Allocator>& x);
template <class Compare> 
void merge(list<T,Allocator>& x, Compare comp);
void sort();
template <class Compare> void sort(Compare comp);
void reverse();
};

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

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




 23.2.2.1 Constructors






 The overloaded list constructors create objects of type list. 



Prototype:



explicit list(const Allocator& = Allocator());

		
		
		
 
		
		
		
explicit list(size_type n, const T& value = T(),

		
		
		
  const Allocator& = Allocator());		
		


				

		
template <class InputIterator>

		
		
		
 
		
		
		
list(InputIterator first, InputIterator last,

		
		
		
  const Allocator& = Allocator());		
		


				

				

		
 assign

		
		
		
 

		
		
		
 The overloaded assign function allows values to be assigned to

		
		a list after construction.
		
		
		
Prototype:		

		
template <class InputIterator>

		
		
		
 
		
		
		
void assign(InputIterator first, 

		
		
		
  InputIterator last);		
		


				

		
void assign(size_type n, const T& t);

		
		
		


				
		
 23.2.2.2 List Capacity

		
		
		
 

		
		
		
 The list class provides for one member function to resize the

		
		list.
		
		
		


				

		
 resize

		
		
		
 

		
		
		
 Resizes the list.

		
		
		
Prototype:		

		
void resize(size_type sz, T c = T());

		
		
		


				
		
 23.2.2.3 List Modifiers

		
		
		
 

		
		
		
 The list class has several overloaded functions to allow modification

		
		of the list object.
		
		
		


				

		
 insert

		
		
		
 

		
		
		
 The insert member function insert a value at a position.

		
		
		
Prototype:		

		
iterator insert(iterator position, const T& x);

		
		
		
 
		
		
		
void insert(

		
		
		
  iterator position, size_type n, const T& x);		
		


				

		
template <class InputIterator>

		
		
		
 
		
		
		
void insert

		
		
		
  (iterator position, InputIterator first,		
		


				  InputIterator last);		

		


				

				

		
 push_front

		
		
		
 

		
		
		
 The push_front member function pushes a value at the front of

		
		the list.
		
		
		
Prototype:		

		
void push_front(const T& x);

		
		
		


				
		
 push_back

		
		
		
 

		
		
		
 The push_back member function pushes a value onto the end of

		
		the list.
		
		
		
Prototype:		

		
void push_back(const T& x);

		
		
		


				
		
 erase

		
		
		
 

		
		
		
 The erase member function removes a value at a position or range.

		
		
		
Prototype:		

		
iterator erase(iterator position);

		
		
		
 
		
		
		
iterator erase(iterator first, iterator last);

		
		
		
Return:		
		
 Returns an iterator to the last position.

		
		
		


				

		
 pop_front

		
		
		
 

		
		
		
 The pop_front member function removes a value from the top of

		
		the list.
		
		
		
Prototype:		

		
void pop_front();

		
		
		


				
		
 pop_back

		
		
		
 

		
		
		
 The pop_back member function removes a value from the end of

		
		the list.
		
		
		
Prototype:		

		
void pop_back();

		
		
		


				
		
 clear

		
		
		
 

		
		
		
 Clears a list by removing all elements.

		
		
		
Prototype:		

		
void clear();.

		
		
		


				
		
 23.2.2.4 List Operations

		
		
		
 

		
		
		
 The list class provides for operations to manipulate the list.

		
		
		


				

		
 splice

		
		
		
 

		
		
		
 Moves an element or a range of elements in front of a position

		
		specified.
		
		
		
Prototype:		

		
void splice

		
		
		
  (iterator position, list<T,Allocator>& x);		
		


				

		
void splice

		
		
		
  (iterator position, list<T,Allocator>& x,		
		


				  iterator i);		

		


				

		
void splice

		
		
		
  (iterator position, list<T,Allocator>& x,		
		


				  iterator first, iterator last);		

		


				

				

		
 remove

		
		
		
 

		
		
		
 Removes all element with a value.

		
		
		
Prototype:		

		
void remove(const T& value);

		
		
		


				
		
 remove_if

		
		
		
 

		
		
		
 Removes all element for which the predicate is true.

		
		
		
Prototype:		

		
template <class Predicate> 

		
		
		
  void remove_if(Predicate pred);		
		


				

				

		
 unique

		
		
		
 

		
		
		
 Removes duplicates of consecutive elements.

		
		
		
Prototype:		

		
void unique();

		
		
		
 
		
		
		
template <class BinaryPredicate> 

		
		
		
  void unique(BinaryPredicate binary_pred);		
		


				

				

		
 merge

		
		
		
 

		
		
		
 Moves sorted elements into a list according to the compare argument.

		
		
		
Prototype:		

		
void merge(list<T,Allocator>& x);

		
		
		
 
		
		
		
template <class Compare> 

		
		
		
  void merge(list<T,Allocator>& x, Compare comp);		
		


				

				

		
 reverse

		
		
		
 

		
		
		
 Reverses the order of the list.

		
		
		
Prototype:		

		
void reverse();

		
		
		


				
		
 sort

		
		
		
 

		
		
		
 Sorts a list according to the Compare function or by less than

		
		value for the parameterless version.
		
		
		
Prototype:		

		
void sort();

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

		
		
		


				
		
 23.2.2.5 List Specialized Algorithms

		
		
		
 

		
		
		
 The list class provides a swapping function.

		
		
		


				

		
 swap

		
		
		
 

		
		
		
 Changes the position of the first argument with the second argument.

		
		
		
Prototype:		

		
template <class T, class Allocator>

		
		
		
 
		
		
		
void swap

		
		
		
  (list<T,Allocator>& x, list<T,Allocator>& y);		
		


				

				

		
 23.2.3 Container adaptors

		
		
		
		

		
 

		
		
		
 Container adaptors take a Container template parameter so that

		
		the container is copied into the Container member of each adaptor.
		
		
		


				

		
 23.2.3.1 Template Class Queue

		
		
		
		

		
 

		
		
		
 Any of the sequence types supporting operations front(), back(),

		
		push_back() and pop_front() can be used to instantiate queue.
		
		
		
Template Class Queue Synopsis:		
		

				

		
namespace std {
template <class T, class Container = deque<T> >
class queue {
public:
typedef typename Container::value_type 	value_type;
typedef typename Container::size_type 	size_type;
typedef Container container_type; 

protected:
Container c;

public:
explicit queue(const Container& = Container());
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
value_type& front() { return c.front(); }
const value_type& front() const { return c.front(); }
value_type& back() { return c.back(); }
const value_type& back() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_front(); }
};
template <class T, class Container>
bool operator==
	(const queue<T, Container>& x,const queue<T, Container>& y);
 template <class T, class Container>
bool operator< 
	(const queue<T, Container>& x, const queue<T, Container>& y); 
template <class T, class Container>
bool operator!=
	(const queue<T, Container>& x, const queue<T, Container>& y); 
template <class T, class Container>
bool operator>
	(const queue<T, Container>& x, const queue<T, Container>& y); 
template <class T, class Container>
bool operator>=
	(const queue<T, Container>& x, const queue<T, Container>& y); 
template <class T, class Container>
bool operator<=
	(const queue<T, Container>& x, const queue<T, Container>& y); 
}

		
		
		
 
		
		
		

				

				
		
 operator ==

		
		
		
 

		
		
		
 A user supplied operator for the queue class that compares the

		
		queue's data member.
		
		
		
Prototype:		

		
bool operator ==

		
		
		
Return:		
		
 Returns true if the data members are equal.

		
		
		


				

		
 operator <

		
		
		
 

		
		
		
 A user supplied operator for the queue class that compares the

		
		queue's data member.
		
		
		
Prototype:		

		
bool operator <

		
		
		
Return:		
		
 Returns true if the data member is less than the compared queue.

		
		
		


				

		
 23.2.3.2 Template Class Priority_queue

		
		
		
		

		
 

		
		
		
 You can instantiate any priority_queue with any sequence that has random access iterator and supporting

		
		operations front(), push_back() and pop_back().
		
		
		
 

		
		
		
 Instantiation of a priority_queue requires supplying a function

		
		or function object for making the priority comparisons.
		
		
		
Template Class Priority_queue Synopsis:		
		

				

		
namespace std {
template <class T, class Container = vector<T>,
	class Compare = less<typename Container::value_type> > 
class priority_queue {
public:
typedef typename Container::value_type 	value_type;
typedef typename Container::size_type 	size_type;
typedef Container 	container_type; 

protected:
Container c;
Compare comp;

public:
explicit priority_queue(const Compare& x = Compare(),
	const Container& = Container());
template <class InputIterator>
priority_queue
	(InputIterator first, InputIterator last,
	const Compare& x = Compare(), const Container& = Container()); 
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const value_type& top() const { return c.front(); }
void push(const value_type& x);
void pop();
};
}

		
		
		
 
		
		
		

				

				
		
 23.2.3.2.1 Constructors

		
		
		
 

		
		
		
 Creates an object of type priority_queue.

		
		
		
Prototype:		

		
priority_queue(const Compare& x = Compare(),

		
		
		
  const Container& y = Container());		
		


				

		
template <class InputIterator>

		
		
		
 
		
		
		
priority_queue

		
		
		
  (InputIterator first, InputIterator last,		
		


				  const Compare& x = Compare(),		

		


				  const Container& y = Container());		

		


				

				

		
 23.2.3.2.2 priority_queue members

		
		
		
 

		
		
		
 The class priority_queue provides public member functions for

		
		manipulation the priority_queue.
		
		
		


				

		
 push

		
		
		
 

		
		
		
 Inserts an element into the priority_queue.

		
		
		
Prototype:		

		
 void push(const value_type& x);

		
		
		


				

		
 pop

		
		
		
 

		
		
		
 Removes an element from a priority_queue.

		
		
		
Prototype:		

		
 void pop();

		
		
		


				

		
 23.2.3.3 Template Class Stack

		
		
		
		

		
 

		
		
		
 A stack class may be instantiated by any sequence supporting

		
		operations back(), push_back() and pop_back().
		
		
		
Template Class Stack Synopsis:		
		

				

		
namespace std {
template <class T, class Container = deque<T> >
class stack {
public:
typedef typename Container::value_type 	value_type;
typedef typename Container::size_type 	size_type;
typedef Container 	container_type; 

protected:
Container c;


public:
explicit stack(const Container& = Container());
bool empty() const;}
size_type size() const;
value_type& top();
const value_type& top() ;
void push(const value_type& x) ;}
void pop();
};
template <class T, class Container>
bool operator==
(const stack<T, Container>& x, const stack<T, Container>& y);
template <class T, class Container>
bool operator<
(const stack<T, Container>& x, const stack<T, Container>& y); 
template <class T, class Container>
bool operator!=
(const stack<T, Container>& x, const stack<T, Container>& y); 
template <class T, class Container>
bool operator>
(const stack<T, Container>& x, const stack<T, Container>& y); 
template <class T, class Container>
bool operator>=
(const stack<T, Container>& x, const stack<T, Container>& y);
template <class T, class Container>
bool operator<=(
const stack<T, Container>& x, const stack<T, Container>& y); }

		
		
		
 
		
		
		

				

				
		
 Public Member Functions

		
		
		


				

		
 Constructors

		
		
		
 

		
		
		
 Creates an object of type stack with a container object.

		
		
		
Prototype:		

		
explicit stack(const Container& = Container());

		
		
		


				
		
 empty

		
		
		
 

		
		
		
 Signifies when the stack is empty

		
		
		
Prototype:		

		
bool empty() const;

		
		
		
Return:		
		
 Returns true if there are no elements in the stack.

		
		
		


				

		
 size

		
		
		
 

		
		
		
 Gives the number of elements in a stack.

		
		
		
Prototype:		

		
size_type size() const;

		
		
		
Return:		
		
 Returns the number of elements in a stack.

		
		
		


				

		
 top

		
		
		
 

		
		
		
 Gives the top element in the stack.

		
		
		
Prototype:		

		
value_type& top()

		
		
		
 
		
		
		
const value_type& top() const 

		
		
		
Return:		
		
 Returns the value at the top of the stack.

		
		
		


				

		
 push

		
		
		
 

		
		
		
 Puts a value onto a stack.

		
		
		
Prototype:		

		
void push(const value_type& x) { c.push_back(x); }

		
		
		


				
		
 pop

		
		
		
 

		
		
		
 Removes an element from a stack.

		
		
		
Prototype:		

		
void pop()

		
		
		


				
		
 23.2.4 Template Class Vector

		
		
		
		

		
 

		
		
		
 A vector is a kind of sequence container that supports random

		
		access iterators. You can use insert and erase operations at
		the
		
		end and in the middle but at the end is faster.
		
		
		
 

		
		
		
 A vector satisfies all of the requirements of a container and

		
		of a reversible container and of a sequence. It also satisfies
		
		most of the optional sequence requirements with the exceptions
		
		being push_front and pop_front member functions.
		
		
		
Template Class Vector Synopsis:		
		

				

		
namespace std {
template <class T, class Allocator = allocator<T> >
class vector {
public:
typedef typename Allocator::reference reference; 
typedef typename Allocator::const_reference const_reference;
// Implementation Defined Types 
typedef 	iterator; 
typedef 	const_iterator; 
typedef 	size_type; 
typedef 	difference_type;

typedef T 	value_type; 
typedef Allocator 	allocator_type; 
typedef typename Allocator::pointer 	pointer; 
typedef typename Allocator::const_pointer 	const_pointer; 
typedef std::reverse_iterator<iterator> 	reverse_iterator; 
typedef std::reverse_iterator<const_iterator>
	const_reverse_iterator;

explicit vector(const Allocator& = Allocator());
explicit vector
	(size_type n, const T& value = T(), 
	const Allocator& = Allocator()); 
template <class InputIterator> vector
	(InputIterator first, InputIterator 
	last, const Allocator& = Allocator()); 
vector(const vector<T,Allocator>& x);

~vector();

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

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;

size_type size() const;
size_type max_size() const;
void resize(size_type sz, T c = T());
size_type capacity() const;
bool empty() const;
void reserve(size_type n);

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

void push_back(const T& x);
void pop_back();
iterator insert(iterator position, const T& x);
void insert(iterator position, size_type n, const T& x);
template <class InputIterator>
void insert
	(iterator position, InputIterator first, InputIterator last); 
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
void swap(vector<T,Allocator>&);
void clear();
};
template <class T, class Allocator>
bool operator==
	(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 
template <class T, class Allocator>
bool operator< 
	(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 
template <class T, class Allocator>
bool operator!=
	(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 
template <class T, class Allocator>
bool operator> 
	(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 
template <class T, class Allocator>
bool operator>=
	(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 
template <class T, class Allocator>
bool operator<=
	(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 

template <class T, class Allocator>
void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
}

		
		
		
 
		
		
		

				

				
		
 23.2.4.1 Constructors

		
		
		
 

		
		
		
 The vector class provides overloaded constructors for creation

		
		of a vector object.
		
		
		
Prototype:		

		
vector(const Allocator& = Allocator());

		
		
		
 
		
		
		
explicit vector

		
		
		
  (size_type n, const T& value = T(),		
		


				  const Allocator& = Allocator());		

		


				

		
template <class InputIterator>

		
		
		
 
		
		
		
vector

		
		
		
  (InputIterator first, InputIterator last,		
		


				  const Allocator& = Allocator());		

		


				

		
vector(const vector<T,Allocator>& x);

		
		
		


				
		
 assign

		
		
		
 

		
		
		
 The member function assign allows you to assign values to an

		
		already created object.
		
		
		
Prototype:		

		
template <class InputIterator>

		
		
		
 
		
		
		
void assign

		
		
		
  (InputIterator first, InputIterator last);		
		


				

		
void assign(size_type n, const T& t);

		
		
		


				
		
 capacity

		
		
		
 

		
		
		
 Tells the maximum number of elements the vector can hold.

		
		
		
Prototype:		

		
size_type capacity() const;

		
		
		
Return:		
		
 Returns the maximum number of elements the vector can hold.

		
		
		


				

		
 resize

		
		
		
 

		
		
		
 Resizes a vector if a second argument is give the elements are

		
		filled with that value.
		
		
		
Prototype:		

		
void resize(size_type sz, T c = T());

		
		
		


				
		
 23.2.4.3 Vector Modifiers

		
		
		
 

		
		
		
 The vector class provides various member functions for vector

		
		data manipulation.
		
		
		


				

		
 insert

		
		
		
 

		
		
		
 The member function insert inserts a value or a range of values

		
		at a set position.
		
		
		
Prototype:		

		
iterator insert(iterator position, const T& x);

		
		
		
 
		
		
		
void insert

		
		
		
  (iterator position, size_type n, const T& x);		
		


				

		
template <class InputIterator>

		
		
		
 
		
		
		
void insert

		
		
		
  (iterator position, InputIterator first,		
		


				  InputIterator last);		

		


				

				

		
 erase

		
		
		
 

		
		
		
 Removes elements at a position or for a range.

		
		
		
Prototype:		

		
iterator erase(iterator position);

		
		
		
 
		
		
		
iterator erase(iterator first, iterator last);

		
		
		


				
		
 23.2.4.4 Vector Specialized Algorithms

		
		
		
 

		
		
		
 The vector class provides for a specialized swap function.

		
		
		


				

		
 swap

		
		
		
 

		
		
		
 Swaps the data of one argument with the other argument.

		
		
		
Prototype:		

		
template <class T, class Allocator>

		
		
		
 
		
		
		
void swap

		
		
		
  (vector<T,Allocator>& x, 		
		


				  vector<T,Allocator>& y);		

		


				

				

		
 23.2.5 Class Vector<bool>

		
		
		
		

		
 

		
		
		
 A specialized vector for bool elements is provided to optimize allocated space.

		
		
		
Class Vector <Bool> Synopsis:		
		

				

		
namespace std {
template <class Allocator> class vector<bool, Allocator> {
public:
typedef bool const_reference; 
// Implementation Defined  Types
typedef 	iterator; 
typedef 	const_iterator; 
typedef 	 size_type; 
typedef 	difference_type;
typedef 	pointer; 
typedef	 const_pointer; 

typedef bool 	value_type; 
typedef Allocator 	allocator_type; 
typedef std::reverse_iterator<iterator> 	reverse_iterator; 
typedef std::reverse_iterator<const_iterator> 	const_reverse_iterator; 

class reference {
friend class vector;
reference();
public:
~reference();
operator bool() const;
reference& operator=(const bool x);
reference& operator=(const reference& x);
void flip(); 
};

explicit vector(const Allocator& = Allocator());
explicit vector(
	size_type n, const bool& value = bool(), 
	const Allocator& = Allocator()); 
template <class InputIterator>
vector
	(InputIterator first, InputIterator last, 
	const Allocator& = Allocator()); 
vector(const vector<bool,Allocator>& x);

~vector();

vector<bool,Allocator>& operator=
	(const vector<bool,Allocator>& x);

template <class InputIterator>
void assign(InputIterator first, InputIterator last);
void assign(size_type n, const T& t);

allocator_type get_allocator() const;

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;

size_type size() const;
size_type max_size() const;
void resize(size_type sz, bool c = false);
size_type capacity() const;
bool empty() const;
void reserve(size_type n);

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

void push_back(const bool& x);
void pop_back();

iterator insert(iterator position, const bool& x);
void insert (iterator position, size_type n, const bool& x);
template <class InputIterator>
void insert
	(iterator position, InputIterator first, InputIterator last);

iterator erase(iterator position);
iterator erase(iterator first, iterator last);

void swap(vector<bool,Allocator>&);
static void swap(reference x, reference y);

void flip(); 
void clear();
};
template <class Allocator>
bool operator==
	(const vector<bool,Allocator>& x,
	const vector<bool,Allocator>& y); 
template <class Allocator>
bool operator< 
	(const vector<bool,Allocator>& x,
	const vector<bool,Allocator>& y); 
template <class Allocator>
bool operator!=
	(const vector<bool,Allocator>& x,
	const vector<bool,Allocator>& y); 
template <class Allocator>
bool operator> 
	(const vector<bool,Allocator>& x,
	const vector<bool,Allocator>& y);
template <class Allocator>
bool operator>=
	(const vector<bool,Allocator>& x,
	const vector<bool,Allocator>& y); 
template <class Allocator>
bool operator<=
	(const vector<bool,Allocator>& x, 
	const vector<bool,Allocator>& y); 

template <class Allocator>
void swap(vector<bool,Allocator>& x, vector<bool,Allocator>& y);
}




 23.3 Associative Containers






 The associative container library consists of four template container classes.






			
			
			
			
			

					

		
		
		
		


				

		
 23.3.1 Template Class Map

		
		
		
		

		
 

		
		
		
 The map class is an associative container that supports unique

		
		keys and provides for retrieval of values of another type T based on the keys. The map template class supports bidirectional
		
		iterators.
		
		
		
 

		
		
		
 The template class map satisfies all of the requirements of a

		
		normal container and those of a reversible container, as well
		
		as an associative container. 
		
		
		
 

		
		
		
 A map also provides operations for unique keys. 

		
		
		
Template Class Map Synopsis:		
		

				

		
namespace std {
template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator<pair<const Key, T> > > class map {
public:
typedef Key key_type; 
typedef T mapped_type; 
typedef pair<const Key, T> value_type; 
typedef Compare key_compare;
typedef Allocator allocator_type; 
typedef typename Allocator::reference reference; 
typedef typename Allocator::const_reference const_reference;
// Implementation Defined Types
typedef 	iterator; 
typedef 	const_iterator; 
typedef 	size_type; 
typedef 	difference_type;

typedef typename Allocator::pointer pointer; 
typedef typename Allocator::const_pointer const_pointer; 
typedef std::reverse_iterator<iterator> reverse_iterator; 
typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 


 



class value_compare
	:public binary_function<value_type,value_type,bool> {
friend class map;
protected:
Compare comp;
value_compare(Compare c) : comp(c) {}

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

explicit map(
	const Compare& comp = Compare(), 
	const Allocator& = Allocator());
template <class InputIterator>
map
	(InputIterator first, InputIterator last,
	const Compare& comp = Compare(), 
	const Allocator& = Allocator()); 
map(const map<Key,T,Compare,Allocator>& x);

~map();

map<Key,T,Compare,Allocator>&
operator=(
	const map<Key,T,Compare,Allocator>& x);

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;

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

T& operator[](const key_type& x); 

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

void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);

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

void clear();

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

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

iterator lower_bound(const key_type& x);
const_iterator lower_bound(const key_type& x) const;
iterator upper_bound(const key_type& x);
const_iterator upper_bound(const key_type& x) const;

pair<iterator,iterator>
equal_range(const key_type& x);
 pair<const_iterator,const_iterator>
equal_range(const key_type& x) const; };
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); 
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); 
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); 
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);
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);
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); 

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

		
		
		
 
		
		
		

				

				
		
 23.3.1.1 Constructors

		
		
		
 

		
		
		
 The map class provides an overloaded constructor for creating

		
		an object of type map.
		
		
		
Prototype:		

		
explicit map

		
		
		
  (const Compare& comp = Compare(),		
		


				  const Allocator& = Allocator());		

		


				

		
template <class InputIterator> map

		
		
		
  (InputIterator first, InputIterator last,		
		


				  const Compare& comp = Compare(), 		

		


				  const Allocator& = Allocator());		

		


				

				

		
 23.3.1.2 Map Element Access

		
		
		
 

		
		
		
 The map class includes an element access operator.

		
		
		


				

		
 operator []

		
		
		
 

		
		
		
 Access an indexed element.

		
		
		
Prototype:		

		
T& operator[] 

		
		
		
  (const key_type& x); 		
		


				Return:		

		
 Returns the value at the position indicated.

		
		
		


				

		
 23.3.1.3 Map Operations

		
		
		
 

		
		
		
 The map class includes member functions for map operations.

		
		
		


				

		
 find

		
		
		
 

		
		
		
 Finds an element based upon a key.

		
		
		
Prototype:		

		
iterator find

		
		
		
  (const key_type& x);		
		


				

		
const_iterator find

		
		
		
  (const key_type& x) const;		
		


				Return:		

		
 Returns the position where the element is found.

		
		
		


				

		
 lower_bound

		
		
		
 

		
		
		
 Finds the first position where an element based upon a key would

		
		be inserted.
		
		
		
Prototype:		

		
iterator lower_bound

		
		
		
  (const key_type& x);		
		


				

		
const_iterator lower_bound

		
		
		
  (const key_type& x) const;		
		


				Return:		

		
 Returns the first position where an element would be inserted.

		
		
		


				

		
 upper_bound

		
		
		
 

		
		
		
 Finds the last position where an element based upon a key would

		
		be inserted.
		
		
		
Prototype:		

		
iterator upper_bound

		
		
		
  (const key_type& x);		
		


				

		
const_iterator upper_bound

		
		
		
  (const key_type &x) const;		
		


				Return:		

		
 Returns the last position where an element would be inserted.

		
		
		


				

		
 equal_range

		
		
		
 

		
		
		
 Finds both the first and last position in a range where an element

		
		based upon a key would be inserted.
		
		
		
Prototype:		

		
pair<iterator, iterator>

		
		
		
 
		
		
		
equal_range

		
		
		
  (const_key_type &x);		
		


				

		
pair<const_iterator, const_iterator>

		
		
		
 
		
		
		
equal_range

		
		
		
  (const key_type& x) const;		
		


				Return:		

		
 Returns a pair of elements representing a range for insertion.

		
		
		


				

		
 23.3.1.4 Map Specialized Algorithms

		
		
		
 

		
		
		
 The map class provides for a method to swap elements.

		
		
		


				

		
 swap

		
		
		
 

		
		
		
 Swaps the first argument with the second argument.

		
		
		
Prototype:		

		
template <class Key, class T, 

		
		
		
  class Compare, class Allocator>		
		


				

		
void swap

		
		
		
  (map<Key,T,Compare,Allocator>& x,		
		


				  map<Key,T,Compare,Allocator>& y);		

		


				

				

		
 23.3.2 Template Class Multimap

		
		
		
		

		
 

		
		
		
 A multimap container supports equivalent keys that may contain multiple copies

		
		of the same key value. Multimap provides for fast retrieval
		of
		
		values of another type based on the keys.
		
		
		
 

		
		
		
 Multimap supports bidirectional iterators.

		
		
		
 

		
		
		
 The multimap satisfies all of the requirements of a container, reversible container

		
		and associative containers.
		
		
		
 

		
		
		
 Multimap supports the a_eq operations but not the a_uniq operations.

		
		
		
 

		
		
		
 For a multimap<Key,T> the key_type is Key and the value_type is pair<const Key,T>

		
		
		
Template Class Multimap Synopsis:		
		

				

		
namespace std {
template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator<pair<const Key, T> > > class multimap {
public:
typedef Key key_type; 
typedef T mapped_type; 
typedef pair<const Key,T> value_type; 
typedef Compare key_compare; 
typedef Allocator allocator_type; 
typedef typename Allocator::reference reference; 
typedef typename Allocator::const_reference const_reference;
//Implementation Defined Types
typedef 	iterator;
typedef 	const_iterator; 
typedef 	size_type; 
typedef 	difference_type;

typedef typename Allocator::pointer pointer; 
typedef typename Allocator::const_pointer const_pointer; 
typedef std::reverse_iterator<iterator> reverse_iterator; 
typedef std::reverse_iterator<const_iterator> const_reverse_iterator; class value_compare
	: public binary_function<value_type,value_type,bool> {
friend class multimap;

protected:
Compare comp;
value_compare(Compare c) : comp(c) {}

public:
bool operator()
	(const value_type& x, const value_type& y) const {
	return comp(x.first, y.first); }  
};

explicit multimap(const Compare& comp = Compare(),
	const Allocator& = Allocator()); 
template <class InputIterator>
multimap
	(InputIterator first, InputIterator last,
	const Compare& comp = Compare(), 
	const Allocator& = Allocator()); 
multimap(const multimap<Key,T,Compare,Allocator>& x);

~multimap();

multimap<Key,T,Compare,Allocator>&
operator=(
	const multimap<Key,T,Compare,Allocator>& x);

allocator_type get_allocator() const;

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;

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

terator insert(const value_type& x);
iterator insert(iterator position, const value_type& x);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);
void swap(multimap<Key,T,Compare,Allocator>&);
void clear();

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

iterator find(const key_type& x);
const_iterator find(const key_type& x) const;

size_type count(const key_type& x) const;

iterator lower_bound(const key_type& x);
const_iterator lower_bound(const key_type& x) const;

iterator upper_bound(const key_type& x);
const_iterator upper_bound(const key_type& x) const;
pair<iterator,iterator> equal_range(const key_type& x);
pair<const_iterator,const_iterator> equal_range
	(const key_type& x) const; };
template <class Key, class T, class Compare, class Allocator>
bool operator==
	(const multimap<Key,T,Compare,Allocator>& x,
	const multimap<Key,T,Compare,Allocator>& y);
 template <class Key, class T, class Compare, class Allocator>
bool operator< 
	(const multimap<Key,T,Compare,Allocator>& x,
	const multimap<Key,T,Compare,Allocator>& y); 
template <class Key, class T, class Compare, class Allocator>
bool operator!=
	(const multimap<Key,T,Compare,Allocator>& x,
	const multimap<Key,T,Compare,Allocator>& y); 
template <class Key, class T, class Compare, class Allocator>
bool operator> 
	(const multimap<Key,T,Compare,Allocator>& x,
	const multimap<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
bool operator>=
	(const multimap<Key,T,Compare,Allocator>& x,
	const multimap<Key,T,Compare,Allocator>& y); 
template <class Key, class T, class Compare, class Allocator>
bool operator<=
	(const multimap<Key,T,Compare,Allocator>& x,
const multimap<Key,T,Compare,Allocator>& y); 

template <class Key, class T, class Compare, class Allocator>
void swap
	(multimap<Key,T,Compare,Allocator>& x,
	multimap<Key,T,Compare,Allocator>& y); }

		
		
		
 
		
		
		

				

				
		
 23.3.2.1 Constructors

		
		
		
 

		
		
		
 The multimap constructor is overloaded for creation of a multimap

		
		object.
		
		
		
Prototype:		

		
explicit multimap

		
		
		
  (const Compare& comp = Compare(),		
		


				  const Allocator& = Allocator());		

		


				

		
template <class InputIterator>

		
		
		
 
		
		
		
multimap

		
		
		
  (InputIterator first, InputIterator last,		
		


				  const Compare& comp = Compare(),		

		


				  const Allocator& = Allocator()0;		

		


				

				

		
 23.3.2.2 Multimap Operations

		
		
		
 

		
		
		
 The multimap class includes member functions for manipulation

		
		of multimap data.
		
		
		


				

		
 find

		
		
		
 

		
		
		
 Finds a value based upon a key argument.

		
		
		
Prototype:		

		
iterator find(const key_type &x);

		
		
		
 
		
		
		
const_iterator find(const key_type& x) const;

		
		
		
Return:		
		
 Returns the position where the element is at.

		
		
		


				

		
 lower_bound

		
		
		
 

		
		
		
 Finds the first position where an element based upon a key would

		
		be inserted.
		
		
		
Prototype:		

		
iterator lower_bound

		
		
		
  (const key_type& x);		
		


				

		
const_iterator lower_bound

		
		
		
  (const key_type& x) const;		
		


				Return:		

		
 Returns the position where an element was found.

		
		
		


				

		
 equal_range

		
		
		
 

		
		
		
 Finds the first and last positions where a range of elements

		
		based upon a key would be inserted.
		
		
		
Prototype:		

		
pair<iterator, iterator>

		
		
		
 
		
		
		
equal_range

		
		
		
  (const key_type& x);		
		


				

		
pair<const_iterator, const_iterator>

		
		
		
 
		
		
		
equal_range

		
		
		
  (const_key_type& x) const;		
		


				Return:		

		
 Returns a pair object that represents the first and last position

		
		where a range is found.
		
		
		


				

		
 23.3.2.3 Multimap Specialized Algorithms

		
		
		
 

		
		
		
 The multimap class provides a specialized function for swapping

		
		elements.
		
		
		


				

		
 swap

		
		
		
 

		
		
		
 Swaps the first argument for the last argument.

		
		
		
Prototype:		

		
template <class Key, class T, 

		
		
		
  class Compare, class Allocator>		
		


				

		
void swap

		
		
		
  (multimap<Key,T,Compare,Allocator>& x,		
		


				  multimap<Key,T,Compare,Allocator>& y);		

		


				

				

		
 23.3.3 Template Class Set

		
		
		
		

		
 

		
		
		
 The template class set is a container that supports unique keys and provides for fast

		
		retrieval of the keys themselves.
		
		
		
 

		
		
		
 Set supports bidirectional iterators.

		
		
		
 

		
		
		
 The class set satisfies all of the requirements of a container, a reversible

		
		container and an associative container.
		
		
		
 

		
		
		
 A set supports the a_uniq operations but not the a_eq operations.

		
		
		
Template Class Set Synopsis:		
		

				

		
namespace std {
template <class Key, class Compare = less<Key>,
class Allocator = allocator<Key> > class set {
public:
typedef Key key_type; 
typedef Key value_type; 
typedef Compare key_compare; 
typedef Compare value_compare; 
typedef Allocator allocator_type; 
typedef typename Allocator::reference reference; 
typedef typename Allocator::const_reference const_reference; 
//implementation Defined Types
typedef 	iterator; 
typedef 	const_iterator; 
typedef 	size_type; 
typedef 	difference_type;

typedef typename Allocator::pointer pointer; 
typedef typename Allocator::const_pointer const_pointer; 
typedef std::reverse_iterator<iterator> reverse_iterator; 
typedef std::reverse_iterator<const_iterator>
	 const_reverse_iterator; 

explicit set
	(const Compare& comp = Compare(), 
	const Allocator& = Allocator()); 
template <class InputIterator>
set
(InputIterator first, InputIterator last,
	const Compare& comp = Compare(),
	 const Allocator& = Allocator()); 
set(const set<Key,Compare,Allocator>& x);

~set();

set<Key,Compare,Allocator>&
operator=
	 (const set<Key,Compare,Allocator>& x); 
allocator_type get_allocator() const;

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;

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

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

void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);

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

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

iterator find(const key_type& x) const;
size_type count(const key_type& x) const;
iterator lower_bound(const key_type& x) const;
iterator upper_bound(const key_type& x) const;
pair<iterator,iterator> equal_range(const key_type& x) const;
};
template <class Key, class Compare, class Allocator>
bool operator==(
	const set<Key,Compare,Allocator>& x,
	const set<Key,Compare,Allocator>& y); 
template <class Key, class Compare, class Allocator>
bool operator<
	(const set<Key,Compare,Allocator>& x,
	const set<Key,Compare,Allocator>& y); 
template <class Key, class Compare, class Allocator>
bool operator!=
	(const set<Key,Compare,Allocator>& x,
	const set<Key,Compare,Allocator>& y);
 template <class Key, class Compare, class Allocator>
bool operator> 
	(const set<Key,Compare,Allocator>& x,
	const set<Key,Compare,Allocator>& y); 
template <class Key, class Compare, class Allocator>
bool operator>=
	const set<Key,Compare,Allocator>& x,
	const set<Key,Compare,Allocator>& y); 
template <class Key, class Compare, class Allocator>
bool operator<=(
	const set<Key,Compare,Allocator>& x,
	const set<Key,Compare,Allocator>& y); 

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

		
		
		
 
		
		
		

				

				
		
 23.3.3.1 Constructors

		
		
		
 

		
		
		
 The set class includes overloaded constructors for creation of

		
		a set object.
		
		
		
Prototype:		

		
explicit set

		
		
		
  (const Compare& comp = Compare(),		
		


				  const Allocator& = Allocator());		

		


				

		
template <class InputIterator> set

		
		
		
  (InputIterator first, last,		
		


				  const Compare& comp = Compare(), 		

		


				  const Allocator& = Allocator());		

		


				

				

		
 23.3.3.2 Set Specialized Algorithms

		
		
		
 

		
		
		
 The set class specializes the swap function.

		
		
		


				

		
 swap

		
		
		
 

		
		
		
 Swaps the first argument with the second argument.

		
		
		
Prototype:		

		
template <class Key, class Compare,

		
		
		
  class Allocator>		
		


				

		
void swap

		
		
		
  (set<Key,Compare,Allocator>& x,		
		


				  set<Key,Compare,Allocator>& y);		

		


				

				

		
 23.3.4 Template Class Multiset

		
		
		
		

		
 

		
		
		
 The template class multiset is an associative container that

		
		supports equivalent keys and retrieval of the keys themselves.
		
		
		
		
		
 

		
		
		
 Multiset supports bidirectional iterators.

		
		
		
 

		
		
		
 The multiset satisfies all of the requirements of a container,

		
		reversible container and an associative container.
		
		
		
 

		
		
		
 A multiset supports the a_eq operations but not the a_uniq operations. 

		
		
		
Template Class Multiset Synopsis:		
		

				

		
namespace std {
template <class Key, class Compare = less<Key>,
class Allocator = allocator<Key> > class multiset {
public:
typedef Key key_type; 
typedef Key value_type; 
typedef Compare key_compare; 
typedef Compare value_compare; 
typedef Allocator allocator_type; 
typedef typename Allocator::reference reference; 
typedef typename Allocator::const_reference const_reference; 
 // Implementation Defined Types
typedef 	iterator; 
typedef 	const_iterator; 
typedef 	 size_type;
typedef 	difference_type;

typedef typename Allocator::pointer pointer; 
typedef typename Allocator::const_pointer const_pointer; 
typedef std::reverse_iterator<iterator> reverse_iterator; 
typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 

explicit multiset
	(const Compare& comp = Compare(),
	const Allocator& = Allocator()); 
template <class InputIterator>
multiset
	(InputIterator first, InputIterator last,
	const Compare& comp = Compare(), 
	const Allocator& = Allocator()); 
multiset(const multiset<Key,Compare,Allocator>& x);

~multiset();

multiset<Key,Compare,Allocator>&
operator=
	(const multiset<Key,Compare,Allocator>& x); 
allocator_type get_allocator() const;

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;

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

iterator insert(const value_type& x);
iterator insert(iterator position, const value_type& x);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);

void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);

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

void clear();

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

iterator find(const key_type& x) const;

size_type count(const key_type& x) const;

iterator lower_bound(const key_type& x) const;
iterator upper_bound(const key_type& x) const;

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

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

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

		
		
		
 
		
		
		

				

				
		
 23.3.4.1 Constructors

		
		
		
 

		
		
		
 The multiset class includes overloaded constructors for creation

		
		of a multiset object.
		
		
		
Prototype:		

		
explicit multiset

		
		
		
  (const Compare& comp = Compare(),		
		


				  const Allocator& = Allocator());		

		


				

		
template <class InputIterator>

		
		
		
 
		
		
		
multiset

		
		
		
  (InputIterator first, last,		
		


				  const Compare& comp = Compare(), 		

		


				  const Allocator& = Allocator());		

		


				

				

		
 23.3.4.2 Multiset Specialized Algorithms

		
		
		
 

		
		
		
 The multiset class provides a specialized swap function.

		
		
		


				

		
 swap

		
		
		
 

		
		
		
 Swaps the first argument with the second argument.

		
		
		
Prototype:		

		
template <class Key, class 

		
		
		
  Compare, class Allocator>		
		


				

		
void swap

		
		
		
  (multiset<Key,Compare,Allocator>& x,		
		


				  multiset<Key,Compare,Allocator>& y);		

		


				

				

		
 23.3.5 Template Class Bitset

		
		
		
		

		
 

		
		
		
 The bitset header defines a template class and related procedures for representing

		
		and manipulating fixed-size sequences of bits.
		
		
		
Header <Bitset> Synopsis:		
		

				

		
#include <cstddef> 
#include <stdexcept>
#include <iosfwd>
namespace std {
template <size_t N> class bitset;

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 <class charT, class traits, size_t N>
	basic_istream<charT, traits>&
	operator>>
	(basic_istream<charT, traits>& is, bitset<N>& x);
template <class charT, class traits, size_t N>
	basic_ostream<charT, traits>&
	operator<<
	(basic_ostream<charT, traits>& os, const bitset<N>& x);
}

		
		
		
 
		
		
		

				Template Class Bitset Synopsis:		
		

				
		
namespace std {
template<size_t N> class bitset {
public:
class reference {
friend class bitset;
reference();
public:
~reference();
reference& operator=(bool x); 
reference& operator=(const reference&);
 bool operator~() const; 
operator bool() const; 
reference& flip(); /
};
bitset();
bitset(unsigned long val);
template<class charT, class traits, class Allocator>
explicit bitset(
const basic_string<charT,traits,Allocator>& str, 
	typename basic_string<charT,traits,
	Allocator>::size_type pos = 0, 
	typename basic_string<charT,traits, Allocator>::size_type n =
	basic_string<charT,traits,Allocator>::npos);

 bitset<N>& operator&=(const bitset<N>& rhs);
bitset<N>& operator|=(const bitset<N>& rhs);
bitset<N>& operator^=(const bitset<N>& rhs);
bitset<N>& operator<<=(size_t pos);
bitset<N>& operator>>=(size_t pos);
bitset<N>& set();
bitset<N>& set(size_t pos, int val = true);
bitset<N>& reset();
bitset<N>& reset(size_t pos);
bitset<N> operator~() const;
bitset<N>& flip();
bitset<N>& flip(size_t pos);

reference operator[](size_t pos);

unsigned long to_ulong() const;
template <class charT, class traits, class Allocator>
	basic_string<charT, traits, Allocator> to_string() const;
size_t count() const;
size_t size() const;
bool operator==(const bitset<N>& rhs) const;
bool operator!=(const bitset<N>& rhs) const;
bool test(size_t pos) const;
bool any() const;
bool none() const;
bitset<N> operator<<(size_t pos) const;
bitset<N> operator>>(size_t pos) const;
};
}

		
		
		
 
		
		
		

				

				
		
 Template Class Bitset

		
		
		
		

		
 

		
		
		
 The template class bitset can store a sequence consisting of

		
		a fixed number of bits.
		
		
		
 

		
		
		
 In the bitset class each bit represents either the value zero (reset) or one (set), there is no negative position.You can toggle a bit to change the value. 

		
		
		
 

		
		
		
 When converting between an object of class bitset and an integral

		
		value, the integral value corresponding to two or more bits
		is
		
		the sum of their bit values.
		
		
		
 

		
		
		
 The bitset functions can report three kinds of errors as exceptions.

		
		
		
 

		
		
		

		
		
		
 See "19.1 Exception Classes," for more information on exception classes.

		
		
		


				

		
 23.3.5.1 Constructors

		
		
		
 

		
		
		
 The bitset class includes overloaded constructors for creation

		
		of a bitset object.
		
		
		
Prototype:		

		
bitset();

		
		
		
 
		
		
		
bitset(unsigned long val);

		
		
		
 
		
		
		
template <class charT, 

		
		
		
  class traits, class Allocator>		
		


				

		
explicit bitset

		
		
		
  (const basic_string<charT, traits, 		
		


				  Allocator>& str, typename basic_string		

		


				  <charT, traits, Allocator>::size_type pos = 0,		

		


				  typename basic_string<charT, traits,		

		


				  Allocator>::size_type n = basic_string		

		


				  <charT, traits, Allocator>::npos);		

		


				

				

		
 23.3.5.2 Bitset Members

		
		
		
 

		
		
		
 The bitset class provides various member operators.

		
		
		


				

		
 operator &=

		
		
		
 

		
		
		
 A bitwise "and equal" operator.

		
		
		
Prototype:		

		
bitset<N>& operator&=(const bitset<N>& rhs);

		
		
		
 Return:		
		
 Returns the result of the "and equals" operation.

		
		
		


				

		
 operator |=

		
		
		
 

		
		
		
 A bitwise "not equal" operator.

		
		
		
Prototype:		

		
bitset<N>& operator|=(const bitset<N>& rhs);

		
		
		
Return:		
		
 Returns the result of the "not equals" operation.

		
		
		


				

		
 operator ^=

		
		
		
 

		
		
		
 A bitwise "exclusive or equals" operator.

		
		
		
Prototype:		

		
bitset<N>& operator^=(const bitset<N>& rhs);

		
		
		
Return:		
		
 Returns the result of the "exclusive or equals" operation.

		
		
		


				

		
 operator <<=

		
		
		
 

		
		
		
 A bitwise "left shift equals" operator.

		
		
		
Prototype:		

		
bitset<N>& operator <<=(size_t pos);

		
		
		
Return:		
		
 Returns the result of the "left shift equals" operation.

		
		
		


				

		
 operator >>=

		
		
		
 

		
		
		
 A bitwise "right shift equals" operator.

		
		
		
Prototype:		

		
bitset<N>& operator>>=(size_t pos);

		
		
		
Return:		
		
 Returns the result of the "right shifts equals" operation.

		
		
		


				

		
 Set

		
		
		
 

		
		
		
 Sets all the bits or a single bit to a value.

		
		
		
Prototype:		

		
bitset<N>& set();

		
		
		
 
		
		
		
bitset<N>& set(size_t pos, int val = 1);

		
		
		
 For the function with no parameters sets all the bits to true.

		
		For the overloaded function with just a position argument sets
		
		that bit to true. For the function with both a position and
		a
		
		value sets the bit at that position to the value.
		
		
		
Return:		

		
 Returns the altered bitset.

		
		
		


				

		
 reset

		
		
		
 

		
		
		
 Sets the bits to false.

		
		
		
Prototype:		

		
bitset<N>& reset();

		
		
		
 
		
		
		
bitset<N>& reset(size_t pos);

		
		
		
 The reset function without any arguments sets all the bits to

		
		false. The reset function with an argument sets the bit at that
		
		position to false.
		
		
		
Return:		

		
 Returns the modified bitset.

		
		
		


				

		
 operator ~

		
		
		
 

		
		
		
 Toggles all bits in the bitset.

		
		
		
Prototype:		

		
bitset<N> operator~() const;

		
		
		
Return:		
		
 Returns the modified bitset.

		
		
		


				

		
 flip

		
		
		
 

		
		
		
 Toggles all the bits in the bitset.

		
		
		
Prototype:		

		
bitset<N>& flip();

		
		
		
 
		
		
		
bitset<N>& flip(size_t pos);

		
		
		
Return:		
		
 Returns the modified bitset.

		
		
		


				

		
 to_ulong

		
		
		
 

		
		
		
 Gives the value as an unsigned log.

		
		
		
Prototype:		

		
unsigned long to_ulong() const;

		
		
		
Return:		
		
 Returns the unsigned long value that the bitset represents.

		
		
		


				

		
 to_string

		
		
		
 

		
		
		
 Gives the string as zero and ones that the bitset represents.

		
		
		
Prototype:		

		
template <class charT, 

		
		
		
  class traits, class Allocator>		
		


				

		
basic_string<charT, traits, Allocator> 

		
		
		
  to_string() const;		
		


				Return:		

		
 Returns a string that the bitset represents.

		
		
		


				

		
 count

		
		
		
 

		
		
		
 Tells the number of bits that are true.

		
		
		
Prototype:		

		
size_t count() const;

		
		
		
Return:		
		
 Returns the number of set bits.

		
		
		


				

		
 size

		
		
		
 

		
		
		
 Tells the size of the bitset as the number of bits.

		
		
		
Prototype:		

		
 size_t size() const;

		
		
		
Return:		

		
 Returns the size of the bitset.

		
		
		


				

		
 operator ==

		
		
		
 

		
		
		
 The equality operator.

		
		
		
Prototype:		

		
bool operator==(const bitset<N>& rhs) const;

		
		
		
Return:		
		
 Returns true if the argument is equal to the right side bitset.

		
		
		


				

		
 operator !=

		
		
		
 

		
		
		
 The inequality operator.

		
		
		
Prototype:		

		
bool operator!=(const bitset<N>& rhs) const;

		
		
		
Return:		
		
 Returns true if the argument is not equal to the right side bitset.

		
		
		


				

		
 test

		
		
		
 

		
		
		
 Test if a bit at a position is set.

		
		
		
Prototype:		

		
bool test(size_t pos) const;

		
		
		
Return:		
		
 Returns true if the bit at the position is true.

		
		
		


				

		
 any

		
		
		
 

		
		
		
 Tests if all bits are set to true.

		
		
		
Prototype:		

		
bool any() const;

		
		
		
Return:		
		
 Returns true if any bits in the bitset are true.

		
		
		


				

		
 none

		
		
		
 

		
		
		
 Tests if all bits are set to false.

		
		
		
Prototype:		

		
bool none() const;

		
		
		
Return:		
		
 Returns true if all bits are false.

		
		
		


				

		
 operator <<

		
		
		
 

		
		
		
 Shifts the bitset to the left a number of positions.

		
		
		
Prototype:		

		
bitset<N> operator<<(size_t pos) const;

		
		
		
Return:		
		
 Returns the modified bitset.

		
		
		


				

		
 operator >>

		
		
		
 

		
		
		
 Shifts the bitset to the right a number of positions.

		
		
		
Prototype:		

		
bitset<N> operator>>(size_t pos) const;

		
		
		
Return:		
		
 Returns the modified bitset.

		
		
		


				

		
 23.3.5.3 Bitset Operators

		
		
		
 

		
		
		
 Bitwise operators are included in the bitset class.

		
		
		


				

		
 operator &

		
		
		
 

		
		
		
 A bitwise and operator.

		
		
		
Prototype:		

		
bitset<N> operator&

		
		
		
  (const bitset<N>& lhs, const bitset<N>& rhs);		
		


				Return:		

		
 Returns the modified bitset.

		
		
		


				

		
 operator |

		
		
		
 

		
		
		
 A bitwise or operator.

		
		
		
Prototype:		

		
bitset<N> operator|

		
		
		
  (const bitset<N>& lhs, const bitset<N>& rhs);		
		


				Return:		

		
 Returns the modified bitset.

		
		
		


				

		
 operator ^

		
		
		
 

		
		
		
 A bitwise exclusive or operator.

		
		
		
Prototype:		

		
bitset<N> operator^

		
		
		
  (const bitset<N>& lhs, const bitset<N>& rhs);		
		


				Return:		

		
 Returns the modified bitset.

		
		
		


				

		
 operator >>

		
		
		
 

		
		
		
 An extractor operator for a bitset input.

		
		
		
Prototype:		

		
template <class charT, class traits, size_t N>

		
		
		
  basic_istream<charT, traits>&		
		


				

		
operator>>

		
		
		
  (basic_istream<charT,		
		


				  traits>& is, bitset<N>& x);		

		


				Return:		

		
 Returns the bitset.

		
		
		


				

		
 operator <<

		
		
		
 

		
		
		
 An inserter operator for a bitset output.

		
		
		
Prototype:		

		
template <class charT, class traits, size_t N>

		
		
		
  basic_ostream<charT, traits>&		
		


				

		
operator<<

		
		
		
  (basic_ostream<charT, traits>& os, 		
		


				  const bitset<N>& x);		

		


				Return:		

		
 Returns the bitset.

		
		
		
 

		
		
		
  

		
		
		
 

		
		
		
 

		
		
		
		
		

				[ First ]  [ Previous ]  [ Next ]  [ Last ]  [ Manuals ]		
		

				Visit the Metrowerks website at: http://www.metrowerks.com

				For assistance contact Metrowerks Technical Support at: cw_support@metrowerks.com

				Copyright © 2000, Metrowerks Corp. All rights reserved.

		
		
		


				

				

		
Last updated: July 21, 2000