Skip to Main Content United States    
PRODUCTS SUPPORT SOLUTIONS SERVICES
COMPAQ SOFTWARE
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

Buy Online or Call 1.800.888.0220      privacy statement and legal notices 
STORES CONTACT US SEARCH PRODUCTS SOLUTIONS OPTIONS DEVELOPERS