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("November"), 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
November 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("November")));
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
November 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 DIGITAL 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
