23 Containers library [lib.containers]

1 A deque is a kind of sequence that, like a vector (23.2.4), supports random access iterators. In addition, it supports constant time insert and erase operations at the beginning or the end; insert and erase in the middle take linear time. That is, a deque is especially optimized for pushing and popping elements at the beginning and end. As with vectors, storage management is handled automatically.

2 A deque satisfies all of the requirements of a container and of a reversible container (given in tables in 23.1) and of a sequence, including the optional sequence requirements (23.1.1). Descriptions are provided here only for operations on deque that are not described in one of these tables or for operations where there is additional semantic information.

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

const Allocator& = Allocator());

deque(InputIterator first, InputIterator last,
      const Allocator& = Allocator());

void assign(InputIterator first, InputIterator last);

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

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

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

}

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

1 Effects: Constructs an empty deque, using the specified allocator.

2 Complexity: Constant.

explicit deque(size_type     n, const T&  value  = T(),
                 const Allocator& = Allocator());

3 Effects: Constructs a deque with n copies of value, using the specified allocator.

4 Complexity: Linear in n.

template <class InputIterator>
   deque(InputIterator   first, InputIterator    last,
         const Allocator& = Allocator());

5 Effects: Constructs a deque equal to the the range [first, last), using the specified allocator.

6 Complexity: If the iterators first and last are forward iterators, bidirectional iterators, or random access iterators the constructor makes only N calls to the copy constructor, and performs no reallocations, where N is last - first. It makes at most 2N calls to the copy constructor of T and log N reallocations if they are input iterators.²⁴⁶⁾ template <class InputIterator>

void assign(InputIterator first, InputIterator last);

7 Effects:

erase(begin(), end());
insert(begin(), first, last);

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

8 Effects:

erase(begin(), end());
insert(begin(), n, t);

246) The complexity is greater in the case of input iterators because each element must be added individually: it is impossible to determine the distance between first abd last before doing the copying. [back to text]

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

1 Effects:

if (sz > size())
  insert(end(), sz-size(), c);
else if (sz < size())
  erase(begin()+sz, end());
else
  ;                                  // do nothing

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

1 Effects: An insert in the middle of the deque invalidates all the iterators and references to elements of the deque. An insert at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.

2 Notes: If an exception is thrown other than by the copy constructor or assignment operator of T there are no effects.

3 Complexity: In the worst case, inserting a single element into a deque takes time linear in the minimum of the distance from the insertion point to the beginning of the deque and the distance from the insertion point to the end of the deque. Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to the copy constructor of T.

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

4 Effects: An erase in the middle of the deque invalidates all the iterators and references to elements of the deque. An erase at either end of the deque invalidates only the iterators and the references to the erased elements.

5 Complexity: The number of calls to the destructor is the same as the number of elements erased, but the number of the calls to the assignment operator is at most equal to the minimum of the number of elements before the erased elements and the number of elements after the erased elements.

6 Throws: Nothing unless an exception is thrown by the copy constructor or assignment operator of T.

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

1 Effects:

x.swap(y);

1 A list is a kind of sequence that supports bidirectional iterators and allows constant time insert and erase operations anywhere within the sequence, with storage management handled automatically. Unlike vectors (23.2.4) and deques (23.2.1), fast random access to list elements is not supported, but many algorithms only need sequential access anyway.

2 A list satisfies all of the requirements of a container and of a reversible container (given in two tables in 23.1) and of a sequence, including most of the the optional sequence requirements (23.1.1). The exceptions are the operator[] and at member functions, which are not provided.²⁴⁷⁾ Descriptions are provided here only for operations on list that are not described in one of these tables or for operations where there is additional semantic information.

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

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

     // 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;

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

iterator last);

void unique(BinaryPredicate binary_pred);

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

// specialized algorithms:
template <class T, class Allocator>
  void swap(list<T,Allocator>& x, list<T,Allocator>& y);

}

247) These member functions are only provided by containers whose iterators are random access iterators. [back to text]

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

1 Effects: Constructs an empty list, using the specified allocator.

2 Complexity: Constant.

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

3 Effects: Constructs a list with n copies of value, using the specified allocator.

4 Complexity: Linear in n.

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

5 Effects: Constructs a list equal to the range [first, last).

6 Complexity: Linear in first - last.

template <class InputIterator>
  void assign(InputIterator first, InputIterator last);

7 Effects:

erase(begin(), end());
insert(begin(), first, last);

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

8 Effects:

erase(begin(), end());
insert(begin(), n, t);

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

1 Effects:

if (sz > size())
  insert(end(), sz-size(), c);
else if (sz < size())
  erase(begin()+sz, end());
else
  ;                                 // do nothing

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


void push_front(const T& x);
void push_back(const T& x);

1 Notes: Does not affect the validity of iterators and references. If an exception is thrown there are no effects.

2 Complexity: Insertion of a single element into a list takes constant time and exactly one call to the copy constructor of T. Insertion of multiple elements into a list is linear in the number of elements inserted, and the number of calls to the copy constructor of T is exactly equal to the number of elements inserted. iterator erase(iterator position); iterator erase(iterator first, iterator last); void pop_front(); void pop_back(); void clear();

3 Effects: Invalidates only the iterators and references to the erased elements.

4 Throws: Nothing.

5 Complexity: Erasing a single element is a constant time operation with a single call to the destructor of T. Erasing a range in a list is linear time in the size of the range and the number of calls to the destructor of type T is exactly equal to the size of the range.

1 Since lists allow fast insertion and erasing from the middle of a list, certain operations are provided specifically for them.

2 list provides three splice operations that destructively move elements from one list to another.

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

3 Requires: &x != this.

4 Effects: Inserts the contents of x before position and x becomes empty. Invalidates all iterators and references to the list x.

5 Throws: Nothing

6 Complexity: Constant time.

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

7 Effects: Inserts an element pointed to by i from list x before position and removes the element from x. The result is unchanged if position == i or position == ++i. Invalidates only the iterators and references to the spliced element.

8 Throws: Nothing

9 Requires: i is a valid dereferenceable iterator of x.

10 Complexity: Constant time.

void splice(iterator     position, list<T,Allocator>&       x, iterator   first,
              iterator   last);

11 Effects: Inserts elements in the range [first, last) before position and removes the elements from x.

12 Requires: [first, last) is a valid range in x. The result is undefined if position is an iterator in the range [first, last). Invalidates only the iterators and references to the spliced elements.

13 Throws: Nothing

14 Complexity: Constant time if &x == this; otherwise, linear time.

void remove(const T&     value);

template <class Predicate> void remove_if(Predicate           pred);

15 Effects: Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value, pred(*i) != false.

16 Throws: Nothing unless an exception is thrown by *i == value or pred(*i) != false.

17 Notes: Stable: the relative order of the elements that are not removed is the same as their relative order in the original list.

18 Complexity: Exactly size() applications of the corresponding predicate.

void unique();

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

19 Effects: Eliminates all but the first element from every consecutive group of equal elements referred to by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version of unique with no arguments) or pred(*i, *(i - 1)) (for the version of unique with a predicate argument) holds.

20 Throws: Nothing unless an exception in thrown by *i == *(i-1) or pred(*i, *(i - 1))

21 Complexity: If the range (last - first) is not empty, exactly (last - first) - 1 applications of the corresponding predicate, otherwise no applications of the predicate.

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

22 Requires: comp defines a strict weak ordering (25.3), and the list and the argument list are both sorted according to this ordering.

23 Effects: Merges the argument list into the list.

24 Notes: Stable: for equivalent elements in the two lists, the elements from the list always precede the elements from the argument list. x is empty after the merge.

25 Complexity: At most size() + x.size() - 1 comparisons. If an exception is thrown other than by a comparison there are no effects.

void reverse();

26 Effects: Reverses the order of the elements in the list.

27 Throws: Nothing.

28 Complexity: Linear time.

void sort();

29 Requires: operator< (for the first version, or comp (for the second version) defines a strict weak ordering (25.3).

30 Effects: Sorts the list according to the operator< or a Compare function object.

31 Notes: Stable: the relative order of the equivalent elements is preserved. If an exception is thrown the order of the elements in the list is indeterminate.

32 Complexity: Approximately NlogN comparisons, where N == size().

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

1 Effects:

x.swap(y);

23.2.3 Container adaptors [lib.container.adaptors]

1 The container adaptors each take a Container template parameter, and each constructor takes a Container reference argument. This container is copied into the Container member of each adaptor.

1 Any sequence supporting operations front(), back(), push_back() and pop_front() can be used to instantiate queue. In particular, list (23.2.2) and deque (23.2.1) can be used.

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

  public:
     explicit queue(const Container& = Container());

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


operator==

2 Returns: x.c == y.c.

operator<

3 Returns: x.c < y.c.

1 Any sequence with random access iterator and supporting operations front(), push_back() and pop_back() can be used to instantiate priority_queue. In particular, vector (23.2.4) and deque (23.2.1) can be used. Instantiating priority_queue also involves supplying a function or function object for making priority comparisons; the library assumes that the function or function object defines a strict weak ordering (25.3).

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

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

priority_queue(const Compare& x = Compare(),
                const Container& y = Container());

1 Requires: x defines a strict weak ordering (25.3).

2 Effects: Initializes comp with x and c with y; calls make_heap(c.begin(), c.end(), comp).

template <class InputIterator>
  priority_queue(InputIterator first, InputIterator last,
                  const Compare& x = Compare(),
                  const Container& y = Container());

3 Requires: x defines a strict weak ordering (25.3).

4 Effects: Initializes c with y and comp with x; calls c.insert(c.end(), first, last); and finally calls make_heap(c.begin(), c.end(), comp).

void push(const value_type& x);

1 Effects:

c.push_back(x);
push_heap(c.begin(), c.end(), comp);

void pop();

2 Effects:

pop_heap(c.begin(), c.end(), comp);
c.pop_back();

1 Any sequence supporting operations back(), push_back() and pop_back() can be used to instantiate stack. In particular, vector (23.2.4), list (23.2.2) and deque (23.2.1) can be used.

namespace std {
  template <class T, class Container = deque<T> >
  class stack {
  public:
    typedef typename Container::value_type                value_type;
    typedef typename Container::size_type                 size_type;
    typedef           Container                           container_type;
  protected:
    Container c;
  public:
    explicit stack(const Container& = Container());

    bool       empty() const                { return c.empty(); }
    size_type size()    const               { return c.size(); }
    value_type&         top()               { return c.back(); }
    const value_type& top() const           { return c.back(); }
    void push(const value_type& x)          { c.push_back(x); }
    void pop()                              { c.pop_back(); }
  };

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

1 A vector is a kind 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, though hints can be given to improve efficiency.

2 A vector satisfies all of the requirements of a container and of a reversible container (given in two tables in 23.1) and of a sequence, including most of the optional sequence requirements (23.1.1). The exceptions are the push_front and pop_front member functions, which are not provided. Descriptions are provided here only for operations on vector that are not described in one of these tables or for operations where there is additional semantic information.

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

const Allocator& = Allocator());

vector(InputIterator first, InputIterator last,
  const Allocator& = Allocator());

void assign(InputIterator first, InputIterator last);

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

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

// specialized algorithms:
template <class T, class Allocator>
  void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);

}

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

1 Complexity: The constructor template <class InputIterator> vector(InputIterator

first, InputIterator last)      makes only N calls to the copy constructor of T (where N is the

template <class InputIterator>
  void assign(InputIterator first, InputIterator last);

2 Effects:

erase(begin(), end());
insert(begin(), first, last);

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

3 Effects:

erase(begin(), end());
insert(begin(), n, t);

size_type capacity() const;

1 Returns: The total number of elements that the vector can hold without requiring reallocation.

void reserve(size_type n);

2 Effects: A directive that informs a vector of a planned change in size, so that it can manage the storage allocation accordingly. After reserve(), capacity() is greater or equal to the argument of reserve if reallocation happens; and equal to the previous value of capacity() otherwise. Reallocation happens at this point if and only if the current capacity is less than the argument of reserve().

3 Complexity: It does not change the size of the sequence and takes at most linear time in the size of the sequence.

4 Throws: length_error if n > max_size().²⁴⁸⁾

5 Notes: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. It is guaranteed that no reallocation takes place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the size specified in the most recent call to reserve().

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

6 Effects:

if (sz > size())
   insert(end(), sz-size(), c);
else if (sz < size())
   erase(begin()+sz, end());
else
   ;                                  // do nothing

248) reserve() uses Allocator::allocate() which may throw an appropriate exception. [back to text]

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

1 Notes: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor or assignment operator of T there are no effects.

2 Complexity: If first and last are forward iterators, bidirectional iterators, or random access iterators, the complexity is linear in the number of elements in the range [first, last) plus the distance to the end of the vector. If they are input iterators, the complexity is proportional to the number of elements in the range [first, last) times the distance to the end of the vector.

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

3 Effects: Invalidates all the iterators and references after the point of the erase.

4 Complexity: The destructor of T is called the number of times equal to the number of the elements erased, but the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

5 Throws: Nothing unless an exception is thrown by the copy constructor or assignment operator of T.

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

1 Effects:

x.swap(y);

1 To optimize space allocation, a specialization of vector for bool elements is provided:

namespace std {
   template <class Allocator> class vector<bool, Allocator> {
   public:
     // types:
     typedef bool                                    const_reference;
     typedef implementation defined                  iterator;        // See 23.1
     typedef implementation defined                  const_iterator; //  See 23.1
     typedef implementation defined                  size_type;       // See 23.1
     typedef implementation defined                  difference_type;//  See 23.1
     typedef bool                                    value_type;
     typedef Allocator                               allocator_type;
     typedef implementation defined                  pointer;
     typedef implementation defined                  const_pointer
     typedef std::reverse_iterator<iterator>         reverse_iterator;
     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

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

     // construct/copy/destroy:
     explicit vector(const Allocator& = Allocator());
     explicit vector(size_type n, const bool& value = bool(),
                      const Allocator& = Allocator());
     template <class InputIterator>
       vector(InputIterator first, InputIterator last,
         const Allocator& = Allocator());
     vector(const vector<bool,Allocator>& x);
    ~vector();
     vector<bool,Allocator>& operator=(const vector<bool,Allocator>& x);
     template <class InputIterator>
       void assign(InputIterator first, InputIterator last);
     void assign(size_type n, const T& t);
     allocator_type get_allocator() const;

// 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 sz, bool c = false);
size_type capacity() const;
bool       empty() const;
void       reserve(size_type n);

// element access:
reference        operator[](size_type n);
const_reference operator[](size_type n) const;
const_reference at(size_type n) const;
reference        at(size_type n);
reference        front();
const_reference front() const;
reference        back();
const_reference back() const;

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

iterator erase(iterator position);
iterator erase(iterator first, iterator last);
void swap(vector<bool,Allocator>&);
static void swap(reference x, reference y);
void flip();                 // flips all bits
void clear();

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

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

2 reference is a class that simulates the behavior of references of a single bit in vector<bool>.

23.3 Associative containers [lib.associative]

1 Headers <map> and <set>: Header <map> synopsis

namespace std {
  template <class Key, class T, class Compare = less<Key>,
            class Allocator = allocator<pair<const Key, T> > >
    class map;
  template <class Key, class T, class Compare, class Allocator>
    bool operator==(const map<Key,T,Compare,Allocator>& x,
                     const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator< (const map<Key,T,Compare,Allocator>& x,
                     const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator!=(const map<Key,T,Compare,Allocator>& x,
                     const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator> (const map<Key,T,Compare,Allocator>& x,
                     const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator>=(const map<Key,T,Compare,Allocator>& x,
                     const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator<=(const map<Key,T,Compare,Allocator>& x,
                     const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    void swap(map<Key,T,Compare,Allocator>& x,
               map<Key,T,Compare,Allocator>& y);

class Allocator = allocator<pair<const Key, T> > >

class multimap;

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

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

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

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

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

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

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

namespace std {
  template <class Key, class Compare = less<Key>,
            class Allocator = allocator<Key> >
    class set;
  template <class Key, class Compare, class Allocator>
    bool operator==(const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator< (const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator!=(const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator> (const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator>=(const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator<=(const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    void swap(set<Key,Compare,Allocator>& x,
              set<Key,Compare,Allocator>& y);
          template <class Key, class Compare = less<Key>,
                     class Allocator = allocator<Key> >
            class multiset;
          template <class Key, class Compare, class Allocator>
            bool operator==(const multiset<Key,Compare,Allocator>& x,
                             const multiset<Key,Compare,Allocator>& y);
          template <class Key, class Compare, class Allocator>
            bool operator< (const multiset<Key,Compare,Allocator>& x,
                             const multiset<Key,Compare,Allocator>& y);
          template <class Key, class Compare, class Allocator>
            bool operator!=(const multiset<Key,Compare,Allocator>& x,
                             const multiset<Key,Compare,Allocator>& y);
          template <class Key, class Compare, class Allocator>
            bool operator> (const multiset<Key,Compare,Allocator>& x,
                             const multiset<Key,Compare,Allocator>& y);
          template <class Key, class Compare, class Allocator>
            bool operator>=(const multiset<Key,Compare,Allocator>& x,
                             const multiset<Key,Compare,Allocator>& y);
          template <class Key, class Compare, class Allocator>
            bool operator<=(const multiset<Key,Compare,Allocator>& x,
                             const multiset<Key,Compare,Allocator>& y);
          template <class Key, class Compare, class Allocator>
            void swap(multiset<Key,Compare,Allocator>& x,
                       multiset<Key,Compare,Allocator>& y);
        }

1 A map is a kind of associative container that supports unique keys (contains at most one of each key value) and provides for fast retrieval of values of another type T based on the keys. Map supports bidirectional iterators.

2 A map satisfies all of the requirements of a container and of a reversible container (23.1) and of an associative container (23.1.2). A map also provides most operations described in (23.1.2) for unique keys. This means that a map supports the a_uniq operations in (23.1.2) but not the a_eq operations. For a map<Key,T> the key_type is Key and the value_type is pair<const Key,T>. Descriptions are provided here only for operations on map that are not described in one of those tables or for operations where there is additional semantic information.

namespace std {
  template <class Key, class T, class Compare = less<Key>,
             class Allocator = allocator<pair<const Key, 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;
    typedef typename Allocator::reference            reference;
    typedef typename Allocator::const_reference      const_reference;
    typedef  implementation defined                  iterator;         // See 23.1
    typedef  implementation defined                  const_iterator; //  See 23.1
    typedef  implementation defined                  size_type;        // See 23.1
    typedef  implementation defined                  difference_type;//  See 23.1
    typedef typename Allocator::pointer              pointer;
    typedef typename Allocator::const_pointer        const_pointer;
    typedef std::reverse_iterator<iterator>          reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

: public binary_function<value_type,value_type,bool> {

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

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

const Allocator& = Allocator());

map(InputIterator first, InputIterator last,
    const Compare& comp = Compare(), const Allocator& = Allocator());

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

void insert(InputIterator first, InputIterator last);

// 23.3.1.3 map operations:
iterator       find(const key_type& x);
const_iterator find(const key_type& x) const;
size_type      count(const key_type& x) const;

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

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

};

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

// specialized algorithms:
template <class Key, class T, class Compare, class Allocator>
  void swap(map<Key,T,Compare,Allocator>& x,
            map<Key,T,Compare,Allocator>& y);

}

explicit map(const Compare& comp = Compare(),
              const Allocator& = Allocator());

1 Effects: Constructs an empty map using the specified comparison object and allocator.

2 Complexity: Constant.

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

3 Effects: Constructs an empty map using the specified comparison object and allocator, and inserts elements from the range [first, last).

4 Complexity: Linear in N if the range [first, last) is already sorted using comp and otherwise N log N, where N is last - first.

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

1 Returns: (*((insert(make_pair(x, T()))).first)).second.

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


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


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


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

1 The find, lower_bound, upper_bound and equal_range member functions each have two versions, one const and the other non-const. In each case the behavior of the two functions is identical except that the const version returns a const_iterator and the non-const version an iterator (23.1.2).

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

1 Effects:

x.swap(y);

1 A multimap is a kind of associative container that supports equivalent keys (possibly containing multiple copies of the same key value) and provides for fast retrieval of values of another type T based on the keys. Multimap supports bidirectional iterators.

2 A multimap satisfies all of the requirements of a container and of a reversible container (23.1) and of an associative container (23.1.2). A multimap also provides most operations described in (23.1.2) for equal keys. This means that a multimap supports the a_eq operations in (23.1.2) but not the a_uniq operations. For a multimap<Key,T> the key_type is Key and the value_type is pair<const Key,T>. Descriptions are provided here only for operations on multimap that are not described in one of those tables or for operations where there is additional semantic information. namespace std {

template <class Key, class T, class Compare = less<Key>,
           class Allocator = allocator<pair<const Key, 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;
  typedef typename Allocator::reference          reference;
  typedef typename Allocator::const_reference    const_reference;
  typedef  implementation defined                iterator;        // See 23.1
  typedef  implementation defined                const_iterator; // See 23.1
  typedef  implementation defined                size_type;       // See 23.1
  typedef  implementation defined                difference_type;// See 23.1
  typedef typename Allocator::pointer            pointer;
  typedef typename Allocator::const_pointer      const_pointer;
  typedef std::reverse_iterator<iterator>        reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

  class value_compare
    : public binary_function<value_type,value_type,bool> {
  friend class multimap;
  protected:
    Compare comp;
    value_compare(Compare c) : comp(c) {}
  public:
    bool operator()(const value_type& x, const value_type& y) const {
      return comp(x.first, y.first);
    }
  };

  // construct/copy/destroy:
  explicit multimap(const Compare& comp = Compare(),
                     const Allocator& = Allocator());
  template <class InputIterator>
    multimap(InputIterator first, InputIterator last,
              const Compare& comp = Compare(),
              const Allocator& = Allocator());
  multimap(const multimap<Key,T,Compare,Allocator>& x);
 ~multimap();
  multimap<Key,T,Compare,Allocator>&
    operator=(const multimap<Key,T,Compare,Allocator>& x);
  allocator_type get_allocator() const;

  // 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& x);
  iterator insert(iterator position, const value_type& x);
  template <class InputIterator>
    void insert(InputIterator first, InputIterator last);

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

  // observers:
  key_compare     key_comp() const;
  value_compare   value_comp() const;

  // map operations:
  iterator        find(const key_type& x);
  const_iterator find(const key_type& x) const;
  size_type       count(const key_type& x) const;

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

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

template <class Key, class T, class Compare, class Allocator>
  bool operator==(const multimap<Key,T,Compare,Allocator>& x,
                   const multimap<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
  bool operator< (const multimap<Key,T,Compare,Allocator>& x,
                   const multimap<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
  bool operator!=(const multimap<Key,T,Compare,Allocator>& x,
                   const multimap<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
  bool operator> (const multimap<Key,T,Compare,Allocator>& x,
                   const multimap<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
  bool operator>=(const multimap<Key,T,Compare,Allocator>& x,
                   const multimap<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
  bool operator<=(const multimap<Key,T,Compare,Allocator>& x,
                   const multimap<Key,T,Compare,Allocator>& y);
         // specialized algorithms:
         template <class Key, class T, class Compare, class Allocator>
           void swap(multimap<Key,T,Compare,Allocator>& x,
                      multimap<Key,T,Compare,Allocator>& y);
      }

explicit multimap(const Compare& comp = Compare(),
                     const Allocator& = Allocator());

1 Effects: Constructs an empty multimap using the specified comparison object and allocator.

2 Complexity: Constant.

template <class InputIterator>
   multimap(InputIterator   first, InputIterator    last,
             const Compare& comp = Compare(),
             const Allocator& = Allocator()0;

3 Effects: Constructs an empty multimap using the specified comparison object and allocator, and inserts elements from the range [first, last).

4 Complexity: Linear in N if the range [first, last). is already sorted using comp and otherwise N log N, where N is last - first.

equal_range(const key_type& x);

equal_range(const_key_type& x) const;

1 The find, lower_bound, upper_bound, and equal_range member functions each have two versions, one const and one non-const. In each case the behavior of the two versions is identical except that the const version returns a const_iterator and the non-const version an iterator(_lib.associative.reqmts).

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

1 Effects:

x.swap(y);

1 A set is a kind of associative container that supports unique keys (contains at most one of each key value) and provides for fast retrieval of the keys themselves. Set supports bidirectional iterators.

2 A set satisfies all of the requirements of a container and of a reversible container (23.1), and of an associative container (23.1.2). A set also provides most operations described in (23.1.2) for unique keys. This means that a set supports the a_uniq operations in (23.1.2) but not the a_eq operations. For a set<Key> both the key_type and value_type are Key. Descriptions are provided here only for operations on set that are not described in one of these tables and for operations where there is additional semantic information.

namespace std {
  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;
    typedef typename Allocator::reference             reference;
    typedef typename Allocator::const_reference       const_reference;
    typedef  implementation defined                   iterator;        // See 23.1
    typedef  implementation defined                   const_iterator; //  See 23.1
    typedef  implementation defined                   size_type;       // See 23.1
    typedef  implementation defined                   difference_type;//  See 23.1
    typedef typename Allocator::pointer               pointer;
    typedef typename Allocator::const_pointer         const_pointer;
    typedef std::reverse_iterator<iterator>           reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    // 23.3.3.1 construct/copy/destroy:
    explicit set(const Compare& comp = Compare(),
                  const Allocator& = Allocator());
    template <class InputIterator>
      set(InputIterator first, InputIterator last,
           const Compare& comp = Compare(), const Allocator& = Allocator());
    set(const set<Key,Compare,Allocator>& x);
   ~set();
    set<Key,Compare,Allocator>& operator=
      (const set<Key,Compare,Allocator>& x);
    allocator_type get_allocator() const;

    // 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& x);
   iterator             insert(iterator position, const value_type& x);
   template <class InputIterator>
        void insert(InputIterator first, InputIterator last);

   void       erase(iterator position);
   size_type erase(const key_type& x);
   void       erase(iterator first, iterator last);
   void swap(set<Key,Compare,Allocator>&);
   void clear();

   // observers:
   key_compare    key_comp() const;
   value_compare value_comp() const;

   // set operations:
   iterator   find(const key_type& x) const;
   size_type count(const key_type& x) const;

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

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

 // specialized algorithms:
 template <class Key, class Compare, class Allocator>
   void swap(set<Key,Compare,Allocator>& x,
              set<Key,Compare,Allocator>& y);

}

explicit set(const Compare& comp = Compare(),
              const Allocator& = Allocator());

1 Effects: Constructs an empty set using the specified comparison objects and allocator.

2 Complexity: Constant.

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

3 Effects: Constructs an empty set using the specified comparison object and allocator, and inserts elements from the range [first, last).

4 Complexity: Linear in N if the range [first, last) is already sorted using comp and otherwise N log N, where N is last - first.

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

1 Effects:

x.swap(y);

1 A multiset is a kind of associative container that supports equivalent keys (possibly contains multiple copies of the same key value) and provides for fast retrieval of the keys themselves. Multiset supports bidirectional iterators.

2 A multiset satisfies all of the requirements of a container and of a reversible container (23.1), and of an associative container (23.1.2). multiset also provides most operations described in (23.1.2) for duplicate keys. This means that a multiset supports the a_eq operations in (23.1.2) but not the a_uniq operations. For a multiset<Key> both the key_type and value_type are Key. Descriptions are provided here only for operations on multiset that are not described in one of these tables and for operations where there is additional semantic information.

namespace std {
   template <class Key, class Compare = less<Key>,
              class Allocator = allocator<Key> >
   class multiset {
   public:
     // types:
     typedef Key                                         key_type;
     typedef Key                                         value_type;
     typedef Compare                                     key_compare;
     typedef Compare                                     value_compare;
     typedef Allocator                                   allocator_type;
     typedef typename Allocator::reference               reference;
     typedef typename Allocator::const_reference         const_reference;
     typedef  implementation defined                     iterator;         // See 23.1
     typedef  implementation defined                     const_iterator; //  See 23.1
     typedef  implementation defined                     size_type;        // See 23.1
     typedef  implementation defined                     difference_type;//  See 23.1
     typedef typename Allocator::pointer                 pointer;
     typedef typename Allocator::const_pointer           const_pointer;
     typedef std::reverse_iterator<iterator>             reverse_iterator;
     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

const Allocator& = Allocator());

multiset(InputIterator first, InputIterator last,
         const Compare& comp = Compare(),
         const Allocator& = Allocator());

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

void insert(InputIterator first, InputIterator last);

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

// specialized algorithms:
template <class Key, class Compare, class Allocator>
  void swap(multiset<Key,Compare,Allocator>& x,
            multiset<Key,Compare,Allocator>& y);

}

explicit multiset(const Compare&  comp  = Compare(),
                   const Allocator& = Allocator());

1 Effects: Constructs an empty set using the specified comparison object and allocator.

2 Complexity: Constant.

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

3 Effects: Constructs an empty multiset using the specified comparison object and allocator, and inserts elements from the range [first, last).

4 Complexity: Linear in N if the range [first, last) is already sorted using comp and otherwise N log N, where N is last - first.

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

1 Effects:

x.swap(y);

#include <cstddef>               // for size_t
#include <string>
#include <stdexcept>             // for invalid_argument,
                                 //      out_of_range, overflow_error
#include <iosfwd>                // for istream, ostream
namespace std {
  template <size_t N> class bitset;

  // 23.3.5.3 bitset operations:
  template <size_t N>
    bitset<N> operator&(const bitset<N>&, const bitset<N>&);
  template <size_t N>
    bitset<N> operator|(const bitset<N>&, const bitset<N>&);
  template <size_t N>
    bitset<N> operator^(const bitset<N>&, const bitset<N>&);
  template <class charT, class traits, size_t N>
    basic_istream<charT, traits>&
    operator>>(basic_istream<charT, traits>&   is, bitset<N>&  x);
  template <class charT, class traits, size_t N>
    basic_ostream<charT, traits>&
    operator<<(basic_ostream<charT, traits>&   os, const bitset<N>&  x);
}

1 The header <bitset> defines a template class and several related functions for representing and manipulating fixed-size sequences of bits.

namespace std {
  template<size_t N> class bitset {
  public:
    // bit reference:
    class reference {
      friend class bitset;
      reference();
    public:
     ~reference();
      reference& operator=(bool x);               // for b[i] = x;
      reference& operator=(const reference&);     // for b[i] = b[j];
      bool operator~() const;                     // flips the bit
      operator bool() const;                      // for x = b[i];
      reference& flip();                          // for b[i].flip();
    };

    // 23.3.5.1 constructors:
    bitset();
    bitset(unsigned long  val);
    template<class charT, class traits, class Allocator>
      explicit bitset(
        const basic_string<charT,traits,Allocator>&    str,
        typename basic_string<charT,traits,Allocator>::size_type    pos  = 0,
        typename basic_string<charT,traits,Allocator>::size_type    n  =
          basic_string<charT,traits,Allocator>::npos);
     // 23.3.5.2 bitset operations:
     bitset<N>& operator&=(const bitset<N>&       rhs);
     bitset<N>& operator|=(const bitset<N>&       rhs);
     bitset<N>& operator^=(const bitset<N>&       rhs);
     bitset<N>& operator<<=(size_t      pos);
     bitset<N>& operator>>=(size_t      pos);
     bitset<N>& set();
     bitset<N>& set(size_t    pos, int   val = true);
     bitset<N>& reset();
     bitset<N>& reset(size_t     pos);
     bitset<N>    operator~() const;
     bitset<N>& flip();
     bitset<N>& flip(size_t     pos);

     // element access:
     reference operator[](size_t     pos);           // for b[i];

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

2 The template class bitset<N> describes an object that can store a sequence consisting of a fixed number of bits, N.

3 Each bit represents either the value zero (reset) or one (set). To toggle a bit is to change the value zero to one, or the value one to zero. Each bit has a non-negative position pos. When converting between an object of class bitset<N> and a value of some integral type, bit position pos corresponds to the bit value 1 << pos. The integral value corresponding to two or more bits is the sum of their bit values.

4 The functions described in this subclause can report three kinds of errors, each associated with a distinct exception:

• an invalid-argument error is associated with exceptions of type invalid_argument (19.1.3);
• an out-of-range error is associated with exceptions of type out_of_range (19.1.5);
• an overflow error is associated with exceptions of type overflow_error (19.1.8).

bitset();

1 Effects: Constructs an object of class bitset<N>, initializing all bits to zero.

bitset(unsigned long     val);

2 Effects: Constructs an object of class bitset<N>, initializing the first M bit positions to the corresponding bit values 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.

template <class charT, class traits, class Allocator>
explicit
bitset(const basic_string<charT, traits, Allocator>&            str,
        typename basic_string<charT, traits, Allocator>::size_type pos = 0,
        typename basic_string<charT, traits, Allocator>::size_type n =
           basic_string<charT, traits, Allocator>::npos);

3 Requires: pos <= str.size().

4 Throws: out_of_range if pos > str.size().

5 Effects: Determines the effective length rlen of the initializing string as the smaller of n and str.size() - pos. The function then throws invalid_argument 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.

6 An element of the constructed string has value zero if the corresponding character in str, beginning at position pos, is 0. Otherwise, the element has the value one. Character position pos + M - 1 corresponds to bit position zero. Subsequent decreasing character positions correspond to increasing bit positions.

7 If M < N, remaining bit positions are initialized to zero.

249) The macro CHAR_BIT is defined in <climits> (18.2). [back to text]

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

1 Effects: Clears each bit in *this for which the corresponding bit in rhs is clear, and leaves all other bits unchanged.

2 Returns: *this.

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

3 Effects: Sets each bit in *this for which the corresponding bit in rhs is set, and leaves all other bits unchanged.

4 Returns: *this.

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

5 Effects: Toggles each bit in *this for which the corresponding bit in rhs is set, and leaves all other bits unchanged.

6 Returns: *this.

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

7 Effects: Replaces each bit at position I in *this with a value determined as follows:

• If I < pos, the new value is zero;
• If I >= pos, the new value is the previous value of the bit at position I - pos.

8 Returns: *this.

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

9 Effects: Replaces each bit at position I in *this with a value determined as follows:

• If pos >= N - I, the new value is zero;
• If pos < N - I, the new value is the previous value of the bit at position I + pos.

10 Returns: *this.

bitset<N>& set();

11 Effects: Sets all bits in *this.

12 Returns: *this.

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

13 Requires: pos is valid

14 Throws: out_of_range if pos does not correspond to a valid bit position.

15 Effects: Stores a new value in the bit at position pos in *this. If val is nonzero, the stored value is one, otherwise it is zero.

16 Returns: *this.

bitset<N>& reset();

17 Effects: Resets all bits in *this.

18 Returns: *this.

bitset<N>& reset(size_t     pos);

19 Requires: pos is valid

20 Throws: out_of_range if pos does not correspond to a valid bit position.

21 Effects: Resets the bit at position pos in *this.

22 Returns: *this.

bitset<N> operator~() const;

23 Effects: Constructs an object x of class bitset<N> and initializes it with *this.

24 Returns: x.flip().

bitset<N>& flip();

25 Effects: Toggles all bits in *this.

26 Returns: *this.

bitset<N>& flip(size_t     pos);

27 Requires: pos is valid

28 Throws: out_of_range if pos does not correspond to a valid bit position.

29 Effects: Toggles the bit at position pos in *this.

30 Returns: *this.

unsigned long to_ulong() const;

31 Throws: overflow_error if the integral value x corresponding to the bits in *this cannot be represented as type unsigned long.

32 Returns: x. template <class charT, class traits, class Allocator> basic_string<charT, traits, Allocator> to_string() const;

33 Effects: Constructs a string object of the appropriate type and initializes it to a string of length N characters. Each character is determined by the value of its corresponding bit position in *this. Character position N - 1 corresponds to bit position zero. Subsequent decreasing character positions correspond to increasing bit positions. Bit value zero becomes the character 0, bit value one becomes the character 1.

34 Returns: The created object. size_t count() const;

35 Returns: A count of the number of bits set in *this. size_t size() const;

36 Returns: N. bool operator==(const bitset<N>& rhs) const;

37 Returns: A nonzero value if the value of each bit in *this equals the value of the corresponding bit in rhs. bool operator!=(const bitset<N>& rhs) const;

38 Returns: A nonzero value if !(*this == rhs). bool test(size_t pos) const;

39 Requires: pos is valid

40 Throws: out_of_range if pos does not correspond to a valid bit position.

41 Returns: true if the bit at position pos in *this has the value one. bool any() const;

42 Returns: true if any bit in *this is one. bool none() const;

43 Returns: true if no bit in *this is one. bitset<N> operator<<(size_t pos) const;

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

45 Returns: bitset<N>(*this) >>= pos.

1 Returns: bitset<N>(lhs) &= rhs. bitset<N> operator|(const bitset<N>& lhs, const bitset<N>& rhs);

2 Returns: bitset<N>(lhs) |= rhs.

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

3 Returns: bitset<N>(lhs) ^= rhs.

template <class charT, class traits, size_t N>
   basic_istream<charT, traits>&
   operator>>(basic_istream<charT, traits>&       is, bitset<N>&   x);

4 A formatted input function (27.6.1.2).

5 Effects: Extracts up to N (single-byte) characters from is. Stores these characters in a temporary object

str  of  type string,  then  evaluates  the  expression x =  bitset<N>(str).  Characters  are

• N characters have been extracted and stored;
• end-of-file occurs on the input sequence;
• the next input character is neither 0 or 1 (in which case the input character is not extracted).

6 If no characters are stored in str, calls is.setstate(ios::failbit) (which may throw ios_base::failure (27.4.4.3).

7 Returns: is.

template <class charT, class traits, size_t N>
   basic_ostream<charT, traits>&
   operator<<(basic_ostream<charT, traits>&       os, const bitset<N>&   x);

8 Returns: os << x.template to_string<charT,traits,allocator<charT> >() (27.6.2.5).