Container Types and Members in Detail

Container Types and Members in Detail

This post discusses the different STL containers and presents all of the operations that STL containers provide. The types and members are grouped by functionality. For each type and operation this section describes the signature, the behavior, and the container types that provide it. Possible containers are vector, deques, lists, sets, multisets, maps, multimaps, and strings. In the following subsections, container means the container type that provides the member.

Type Definitions

container::value_type

• The type of elements.
  
• For sets and multisets, it is constant.
  
• For maps and multimaps, it is pair <const key-type, value-type>
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::reference

• The type of element references.
  
• Typically: container::value_type&.
  
• For vector<bool>, it is an auxiliary class.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::const_reference

• The type of constant element references.
  
• Typically: const container::value_type&.
  
• For vector<bool>, it is bool.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::iterator

• The type of iterators.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::const_iterator

• The type of constant iterators.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::reverse_iterator

• The type of reverse iterators.
  
• Provided by vectors, deques, lists, sets, multisets, maps, and multimaps.

container::const_reverse_iterator

• The type of constant reverse iterators.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::size_type

• The unsigned integral type for size values.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::difference_type

• The signed integral type for difference values.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::key_type

• The type of the key of the elements for associative containers.
  
• For sets and multisets, it is equivalent to value_type.
  
• Provided by sets, multisets, maps, and multimaps.

container::mapped_type

• The type of the value of the elements of associative containers.
  
• Provided by maps and multimaps.

container::key_compare

• The type of the comparison criterion of associative containers.
  
• Provided by sets, multisets, maps, and multimaps.

container::value_compare

• The type of the comparison criterion for the whole element type.
  
• For sets and multisets, it is equivalent to key_compare.
  
• For maps and multimaps, it is an auxiliary class for a comparison criterion that compares only the key part of two elements.
• Provided by sets, multisets, maps, and multimaps.

container::allocator_type

• The type of the allocator.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Create, Copy, and Destroy Operations

Containers provide the following constructors and destructors. Also, most constructors allow you to pass an allocator as an additional argument.

container::container ()

• The default constructor.
  
• Creates a new empty container.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

explicit container::container (const CompFunc& op)

• Creates a new empty container with op used as the sorting criterion.
  
• The sorting criterion must define a "strict weak ordering".
  
• Provided by sets, multisets, maps, and multimaps.

explicit container::container (const container&, c)

• The copy constructor.
  
• Creates a new container as a copy of the existing container c.
  
• Calls the copy constructor for every element in c.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

explicit container::container (size_type num)

• Creates a container with num elements.
  
• The elements are created with their default constructor.
  
• Provided by vectors, deques, and lists.

container::container (size_type num, const T& value)

• Creates a container with num elements.
  
• The elements are created as copies of value.
  
• T is the type of the container elements.
  
• For strings, value is not passed by reference.
  
• Provided by vectors, deques, lists, and strings.

container::container (InputIterator beg, InputIterator end)

• Creates a container that is initialized by all elements of the range [beg,end).
  
• This function is a member template. Thus, the elements of the source range may have any type that is convertible to the element type of the container.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::container (InputIterator beg, InputIterator end, const CompFunc& op)

• Creates a container that has the sorting criterion op and is initialized by all elements of the range [beg,end).
  
• This function is a member template. Thus, the elements of the source range may have any type that is convertible to the element type of the container.
  
• The sorting criterion must define a "strict weak ordering".
  
• Provided by sets, multisets, maps, and multimaps.

container::^~container ()

• The destructor.
  
• Removes all elements and frees the memory.
  
• Calls the destructor for every element.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Nonmodifying Operations

Size Operations

size_type container::size () const

• Returns the actual number of elements.
  
• To check whether the container is empty (contains no elements), you should use empty() because it may be faster.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

bool container::empty () const

• Returns whether the container is empty (contains no elements).
  
• It is equivalent to container:: size()==0, but it may be faster (especially for lists).
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

size_type container::max_size () const

• Returns the maximum number of elements a container may contain.
  
• This is a technical value that may depend on the memory model of the container. In particular, because vectors usually use one memory segment, this value may be less than for other containers.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Capacity Operations

size_type container::capacity () const

• Returns the number of elements the container may contain without reallocation.
  
• Provided by vectors and strings.

void container::reserve (size_type num)

• Reserves internal memory for at least num elements.
  
• If num is less than the actual capacity, this call has no effect on vectors and is a nonbinding shrink request for strings.
  
• To shrink the capacity of vectors.
  
• Each reallocation invalidates all references, pointers, and iterators, and takes some time. Thus reserve() can increase speed and keep references, pointers, and iterators valid.
  
• Provided by vectors and strings.

Comparison Operations

bool comparison (const container& c1, const container&, c2)

• Returns the result of the comparison of two containers of same type.
  
• comparison might be any of the following:
  
  operator == operator != operator < operator > operator <= operator >=
  
• Two containers are equal if they have the same number of elements and contain the same elements in the same order (all comparisons of two corresponding elements have to yield true).
  
• To check whether a container is less than another container, the containers are compared lexicographically.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Special Nonmodifying Operations for Associative Containers

The member functions mentioned here are special implementations of corresponding ST. They provide better performance because they rely on the fact that the elements of associative containers are sorted. In fact, they provide logarithmic complexity instead of linear complexity. For example, to search for one of 1,000 elements, no more than ten comparisons on average are needed.

size_type container::count (const T& value) const

• Returns the number of elements that are equal to value.
  
• This is the special version of the count() algorithm.
  
• T is the type of the sorted value:
  
  • For sets and multisets, it is the type of the elements.
    
  • For maps and multimaps, it is the type of the keys.
• Complexity: linear.
  
• Provided by sets, multisets, maps, and multimaps.

iterator container::find (const T& value)
const_iterator container::find (const T& value) const

• Both return the position of the first element that has a value equal to value.
  
• They return end() if no element is found.
  
• These are the special versions of the find() algorithm.
  
• T is the type of the sorted value:
  
  • For sets and multisets, it is the type of the elements.
    
  • For maps and multimaps, it is the type of the keys.
• Complexity: logarithmic.
  
• Provided by sets, multisets, maps, and multimaps.

iterator container::lower_bound (const T& value)
const_iterator container::lower_bound (const T& value) const

• Both return the first position where a copy of value would get inserted according to the sorting criterion.
  
• They return end() if no such element is found.
  
• The return value is the position of the first element that has a value less than or equal to value (which might be end()).
  
• These are the special versions of the lower_bound() algorithm.
  
• T is the type of the sorted value:
  
  • For sets and multisets, it is the type of the elements.
    
  • For maps and multimaps, it is the type of the keys.
• Complexity: logarithmic.
  
• Provided by sets, multisets, maps, and multimaps.

iterator container::upper_bound (const T& value)
const_iterator container::upper_bound (const T& value) const

• Both return the last position where a copy of value would get inserted according to the sorting criterion.
  
• They return end() if no such element is found.
  
• The return value is the position of the first element that has a value greater than value (which might be end()).
  
• These are the special versions of the upper_bound() algorithm.
  
• T is the type of the sorted value:
  
  • For sets and multisets, it is the type of the elements.
    
  • For maps and multimaps, it is the type of the keys.
• Complexity: logarithmic.
  
• Provided by sets, multisets, maps, and multimaps.

pair<iterator,iterator> container::equal_range (const T& value)
pair<const_iterator,const_iterator> container::equal_range (const T& value) const

• Both return a pair with the first and last positions where a copy of value would get inserted according to the sorting criterion.
  
• The return value is the range of elements equal to value.
  
• They are equivalent to:
  

     make_pair (lower_bound(value),upper_bound(value))
         

• These are the special versions of the equal_range() algorithm.
  
• T is the type of the sorted value:
  
  • For sets and multisets, it is the type of the elements.
    
  • For maps and multimaps, it is the type of the keys.
• Complexity: logarithmic.
  
• Provided by sets, multisets, maps, and multimaps.

key_compare container::key_comp ()

• Returns the comparison criterion.
  
• Provided by sets, multisets, maps, and multimaps.

value_compare container::value_comp ()

• Returns the object that is used as the comparison criterion.
  
• For sets and multisets, it is equivalent to key_comp ().
  
• For maps and multimaps, it is an auxiliary class for a comparison criterion that compares only the key part of two elements.
  
• Provided by sets, multisets, maps, and multimaps.

Assignments

container& container::operator= (const container& c)

• Assigns all elements of c; that is, it replaces all existing elements with copies of the elements of c.
• The operator may call the assignment operator for elements that have been overwritten, the copy constructor for appended elements, and the destructor of the element type for removed elements.
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

void container::assign (size_type num, const T& value)

• Assigns num occurrences of value; that is, it replaces all existing elements by num copies of value.
  
• T has to be the element type.
  
• Provided by vectors, deques, lists, and strings.

void container::assign (InputIterator beg, Inputlterator end)

• Assigns all elements of the range [beg,end); that is, it replaces all existing elements with copies of the elements of [beg,end).
  
• This function is a member template. Thus, the elements of the source range may have any type that is convertible to the element type of the container.
  
• Provided by vectors, deques, lists, and strings.

void container::swap (container& c)

• Swaps the contents with c.
  
• Both containers swap
  
  • their elements and
    
  • their sorting criterion if any.
• This function has a constant complexity. You should always prefer it over an assignment when you no longer need the assigned object.
  
• For associative containers, the function may only throw if copying or assigning the comparison criterion may throw. For all other containers, the function does not throw.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

void swap (container& c1, container&, c2)

• It is equivalent to c1. swap(c2) (see the previous description).
  
• For associative containers, the function may only throw if copying or assigning the comparison criterion may throw. For all other containers, the function does not throw.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Direct Element Access

reference container::at (size_type idx)
const_reference container::at (size_type idx) const

• Both return the element with the index idx (the first element has index 0).
  
• Passing an invalid index (less than 0 or equal to size() or greater than size()) throws an out_of _range exception.
  
• Note that the returned reference may get invalidated due to later modifications or reallocations.
  
• If you are sure that the index is valid, you can use operator [ ], which is faster.
  
• Provided by vectors, deques, and strings.

reference container::operator [ ] (size_type idx)
const_reference container::operator [ ] (size_type idx) const

• Both return the element with the index idx (the first element has index 0).
  
• Passing an invalid index (less than 0 or equal to size() or greater than size()) results in undefined behavior. Thus, the caller must ensure that the index is valid; otherwise, at() should be used.
  
• The reference returned for the nonconstant string may get invalidated due to string modifications or reallocations (see page 487 for details).
  
• Provided by vectors, deques, and strings.

T& map::operator [] (const key_type& key)

• Operator [ ] for associative arrays.
  
• Returns the corresponding value to key in a map.
  
• Note: If no element with a key equal to key exists, this operation creates a new element automatically with a value that is initialized by the default constructor of the value type. Thus, you can't have an invalid index (only wrong behavior). For example:
  
  map<int,string> coll; coll [77] = "hello"; <i>// insert key</i> 77 <i>with value</i> "hello" cout << coll [42]; <i>// Oops, inserts key</i> 42 <i>with value</i> "" <i>and prints the value</i>
  
• T is the type of the element value.
  
• It is equivalent to:
  

         
       (*((insert(make_pair(x,T()))).first)).second
  
        

• Provided by maps.

reference container::front ()
const_reference container::front () const

• Both return the first element (the element with index 0).
  
• The caller must ensure that the container contains an element (size ()>0); otherwise, the behavior is undefined.
  
• Provided by vectors, deques, and lists.

reference container::back ()
const_reference container::back () const

• Both return the last element (the element with index size()-l).
  
• The caller must ensure that the container contains an element (size()>0); otherwise, the behavior is undefined.
  
• Provided by vectors, deques, and lists.

Operations to Generate Iterators

The following member functions return iterators to iterate over the elements of the containers. Table below lists the iterator category according to the different container types.

Table :- Iterator Categories According to Container Types

Container	Iterator Category
Vector	Random access
Deque	Random access
List	Bidirectional
Set	Bidirectional, element is constant
Multiset	Bidirectional, element is constant
Map	Bidirectional, key is constant
Multimap	Bidirectional, key is constant
String	Random access

iterator container::begin ()
const_iterator container:: begin () const

• Both return an iterator for the beginning of the container (the position of the first element).
  
• If the container is empty, the calls are equivalent to container::end().
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

iterator container::end ()
const_iterator container::end () const

• Both return an iterator for the end of the container (the position after the last element).
  
• If the container is empty, the calls are equivalent to container: : begin().
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

reverse_iterator container::rbegin ()
const_reverse_iterator container::rbegin () const

• Both return a reverse iterator for the beginning of a reverse iteration over the elements of the container (the position of the last element).
  
• If the container is empty, the calls are equivalent to container:: rend().
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

reverse_iterator container::rend ()
const_reverse_iterator container::rend () const

• Both return a reverse iterator for the end of a reverse iteration over the elements of the container (the position before the first element).
  
• If the container is empty, the calls are equivalent to container:: rbegin().
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Inserting and Removing Elements

iterator container::insert (const T& value)
pair<iterator,bool> container::insert (const T& value)

• Both insert a copy of value into an associative container.
  
• Containers that allow duplicates (multisets and multimaps) have the first signature. They return the position of the new element.
  
• Containers that do not allow duplicates (sets and maps) have the second signature. If they can't insert the value because an element with an equal value or key exists, they return the position of the existing element and false. If they can insert the value, they return the position of the new element and true.
  
• T is the type of the container elements. Thus, for maps and multimaps it is a key/value pair.
  
• The functions either succeed or have no effect.
  
• Provided by sets, multisets, maps, and multimaps.

iterator container::insert (iterator pos, const T& value)

• Inserts a copy of value at the position of iterator pos.
  
• Returns the position of the new element.
  
• For associative containers (sets, multisets, maps, and multimaps), the position is only used as hint, pointing to where the insert should start to search. If value is inserted right behind pos the function has amortized constant complexity; otherwise, it has logarithmic complexity.
  
• If the container is a set or a map that already contains an element equal to (the key of) value, then the call has no effect and the return value is the position of the existing element.
  
• For vectors and deques, this operation might invalidate iterators and references to other elements.
  
• T is the type of the container elements. Thus, for maps and multimaps it is a key/value pair.
  
• For strings, value is not passed by reference.
  
• For vectors and deques, if the copy operations (copy constructor and assignment operator) of the elements don't throw, the function either succeeds or has no effect. For all other standard containers, the function either succeeds or has no effect.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

void container::insert (iterator pos, size_type num, const T& value)

• Inserts num copies of value at the position of iterator pos.
  
• For vectors and deques, this operation might invalidate iterators and references to other elements.
  
• T is the type of the container elements. Thus, for maps and multimaps it is a key/value pair.
  
• For strings, value is not passed by reference.
  
• For vectors and deques, if the copy operations (copy constructor and assignment operator) of the elements don't throw, the function either succeeds or has no effect. For lists, the function either succeeds or has no effect.
  
• Provided by vectors, deques, lists, and strings.

void container::insert (InputIterator beg, InputIterator end)

• Inserts copies of all elements of the range [beg,end) into the associative container.
  
• This function is a member template. Thus, the elements of the source range may have any type that is convertible to the element type of the container.
  
• Provided by sets, multisets, maps, and multimaps.

void container::insert (iterator pos, InputIterator beg, InputIterator end)

• Inserts copies of all elements of the range [beg,end) at the position of iterator pos.
  
• This function is a member template. Thus, the elements of the source range may have any type that is convertible to the element type of the container.
  
• For vectors and deques, this operation might invalidate iterators and references to other elements.
  
• For lists, the function either succeeds or has no effect.
  
• Provided by vectors, deques, lists, and strings.

void container::push_front (const T& value)

• Inserts a copy of value as the new first element.
  
• T is the type of the container elements.
  
• It is equivalent to insert(begin(), value).
  
• For deques, this operation invalidates iterators to other elements. References to other elements stay valid.
  
• This function either succeeds or has no effect.
  
• Provided by deques and lists.

void container::push_back (const T& value)

• Appends a copy of value as the new last element.
  
• T is the type of the container elements.
  
• It is equivalent to insert(end() ,value).
  
• For vectors, this operation invalidates iterators and references to other elements when reallocation takes place.
  
• For deques, this operation invalidates iterators to other elements. References to other elements stay valid.
  
• This function either succeeds or has no effect.
  
• Provided by vectors, deques, lists, and strings.

void list::remove (const T& value)
void list::remove_if (UnaryPredicate op)

• remove() removes all elements with value value.
  
• remove_if() removes all elements for which the unary predicate
  

         
     op(elem)
        

  yields true.
  
• Note that op should not change its state during a function call.
  
• Both call the destructors of the removed elements.
  
• The order of the remaining arguments remains stable.
  
• This is the special version of the remove() algorithm.
  
• T is the type of the container elements.
  
• For further details and examples,
  
• The functions may only throw if the comparison of the elements may throw.
  
• Provided by lists.

size_type container::erase (const T& value)

• Removes all elements equal to value from an associative container.
  
• Returns the number of removed elements.
  
• Calls the destructors of the removed elements.
  
• T is the type of the sorted value:
  
  • For sets and multisets, it is the type of the elements.
    
  • For maps and multimaps, it is the type of the keys.
• The function does not throw.
  
• Provided by sets, multisets, maps, and multimaps.

void container::erase (iterator pos)
iterator container::erase (iterator pos)

• Both remove the element at the position of iterator pos.
  
• Sequence containers (vectors, deques, lists, and strings) have the second signature. They return the position of the following element (or end()).
  
• Associative containers (sets, multisets, maps, and multimaps) have the first signature. They return nothing.
  
• Both call the destructors of the removed elements.
  
• Note that the caller must ensure that the iterator pos is valid. For example:
  
  coll. erase (coll. end()); <i>// ERROR</i> ? <i>undefined behavior</i>
  
• For vectors and deques, this operation might invalidate iterators and references to other elements.
  
• For vectors and deques, the function may only throw if the copy constructor or assignment operator of the elements may throw. For all other containers, the function does not throw.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

void container::erase (iterator beg, iterator end)
iterator container::erase (iterator beg, iterator end)

• Both remove the elements of the range [beg,end).
  
• Sequence containers (vectors, deques, lists, and strings) have the second signature. They return the position of the element that was behind the last removed element on entry (or end()).
  
• Associative containers (sets, multisets, maps, and multimaps) have the first signature. They return nothing.
  
• As always for ranges, all elements including beg but excluding end are removed.
  
• Both call the destructors of the removed elements.
  
• Note that the caller must ensure that beg and end define a valid range that is part of the container.
  
• For vectors and deques, this operation might invalidate iterators and references to other elements.
  
• For vectors and deques, the function may only throw if the copy constructor or the assignment operator of the elements may throw. For all other containers, the function does not throw.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

void container::pop_front ()

• Removes the first element of the container.
  
• It is equivalent to container. erase (container.begin()).
  
• Note: If the container is empty, the behavior is undefined. Thus, the caller must ensure that the container contains at least one element (size () >0).
  
• The function does not throw.
  
• Provided by deques and lists.

void container::pop_back ()

• Removes the last element of the container.
  
• It is equivalent to container.erase(--container.end()), provided this expression is valid, which might not be the case for vectors.
  
• Note: If the container is empty, the behavior is undefined. Thus, the caller must ensure that the container contains at least one element (size()>0).
  
• The function does not throw.
  
• Provided by vectors, deques, and lists.

void container::resize (size_type num)
void container::resize (size_type num, T value)

• Both change the number of elements to num.
  
• If size() is num on entry, they have no effect.
  
• If num is greater than size() on entry, additional elements are created and appended to the end of the container. The first form creates the new elements by calling their default constructor; the second form creates the new elements as copies of value.
  
• If num is less than size() on entry, elements are removed at the end to get the new size. In this case, they call the destructor of the removed elements.
  
• For vectors and deques, these functions might invalidate iterators and references to other elements.
  
• For vectors and deques, these functions either succeed or have no effect, provided the copy constructor or the assignment operator of the elements don't throw. For lists, the functions either succeed or have no effect.
  
• Provided by vectors, deques, lists, and strings.

void container::clear ()

• Removes all elements (makes the container empty).
  
• Calls the destructors of the removed elements.
  
• Invalidates all iterators and references to the container.
  
• For vectors and deques, the function may only throw if the copy constructor or the assignment operator of the elements may throw. For all other containers, the function does not throw.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Special Member Functions for Lists

void list:: unique ()
void list::unique (BinaryPredicate op)

• Both remove subsequent duplicates of list elements so that each element contains a different value than the following element.
  
• The first form removes all elements for which the previous values are equal.
  
• The second form removes all elements that follow an element e and for which the binary predicate
  

         
     op(elem,e)
        

  yields true. In other words, the predicate is not used to compare an element with its predecessor; the element is compared with the previous element that was not removed.

• Note that op should not change its state during a function call.
  
• Both call the destructors of the removed elements.
  
• These are the special versions of the unique() algorithms.
  
• The functions do not throw if the comparisons of the elements do not throw.

void list::splice (iterator pos, list& source)

• Moves all elements of source into *this and inserts them at the position of iterator pos.
  
• source is empty after the call.
  
• If source and *this are identical, the behavior is undefined. Thus, the caller must ensure that source is a different list. To move elements inside the same list you must use the following form of splice().
  
• The caller must ensure that pos is a valid position of *this; otherwise, the behavior is undefined.
  
• This function does not throw.

void list::splice (iterator pos, list& source, iterator sourcePos)

• Moves the element at the position sourcePos of the list source into *this and inserts it at the position of iterator pos.
  
• source and *this may be identical. In this case, the element is moved inside the list.
  
• If source is a different list, it contains one element less after the operation.
  
• The caller must ensure that pos is a valid position of *this, sourcePos is a valid iterator of source, and sourcePos is not source. end(); otherwise, the behavior is undefined.
  
• This function does not throw.

void list::splice (iterator pos, list& source, iterator sourceBeg, iterator sourceEnd)

• Moves the elements of the range [sourceBeg,sourceEnd) of the list source to *this and inserts it at the position of iterator pos.
  
• source and *this may be identical. In this case, pos must not be part of the moved range, and the elements are moved inside the list.
  
• If source is a different list, it contains less elements after the operation.
  
• The caller must ensure that pos is a valid position of *this, and that sourceBeg and sourceEnd define a valid range that is part of source; otherwise, the behavior is undefined.
  
• This function does not throw.

void list::sort ()
void list::sort (CompFunc op)

• Both sort the elements in the list.
  
• The first form sorts all elements in the list with operator <.
  
• The second form sorts all elements in the list by calling op to compare two elements:
  

  op(elem1,elem2)
  
        

• The order of elements that have an equal value remains stable (unless an exception is thrown).
  
• These are the special versions of the sort() and stable_sort() algorithms, 

void list::merge (list& source)
void list::merge (list& source, CompFunc op)

• Both merge all elements of the list source into *this.
  
• source is empty after the call.
  
• If *this and source are sorted on entry according to the sorting criterion < or op, the resulting list is also sorted. Strictly speaking, the standard requires that both lists be sorted on entry. In practice, however, merging is also possible for unsorted lists. However, you should check this before you rely on it.
  
• The first form uses operator < as the sorting criterion.
  
• The second form uses op as the optional sorting criterion and is used to compare two elements^[36] :
  

         
  op (elem, sourceElem)
  
        

• This is the special version of the merge() algorithm.
  
• If the comparisons of the elements do not throw, the functions either succeed or have no effect.

void list::reverse ()

• Reverses the order of the elements in a list.
  
• This is the special version of the reverse() algorithm.
  
• This function does not throw.

Allocator Support

All STL containers can be used with a special memory model that is defined by an allocator object. This subsection describes the members for allocator support.

Standard containers require that all instances of an allocator type are interchangeable. Thus, storage allocated from one container can be deallocated via another that has the same type. Therefore, it is no problem when elements (and their storage) are moved between containers of the same type.

Fundamental Allocator Members

container::allocator_type

• The type of the allocator.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

allocator_type container::get_allocator () const

• Returns the memory model of the container.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Constructors with Optional Allocator Parameters

explicit container container (const Allocator& alloc)

• Creates a new empty container that uses the memory model alloc.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::container (const CompFunc& op, const Allocator& alloc)

• Creates a new empty container with op used as the sorting criterion that uses the memory model alloc.
  
• The sorting criterion must define a "strict weak ordering" (see page 176).
  
• Provided by sets, multisets, maps, and multimaps.

container::container (size.type num, const T& value, const Allocator& alloc)

• Creates a container with num elements that uses the memory model alloc.
  
• The elements are created as copies of value.
  
• T is the type of the container elements. Note that for strings, value is passed by value.
  
• Provided by vectors, deques, lists, and strings.

container::container (InputIterator beg, InputIterator end, const Allocator& alloc)

• Creates a container that is initialized by all elements of the range [beg,end) and uses the memory model alloc.
  
• This function is a member template. Thus, the elements of the source range may have any type that is convertible to the element type of the container.
  
• Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::container (InputIterator beg, InputIterator end, const CompFunc& op, const Allocator& alloc)

• Creates a container that has the sorting criterion op, is initialized by all elements of the range [beg,end), and uses the memory model alloc.
  
• This function is a member template (see page 11). Thus, the elements of the source range may have any type that is convertible to the element type of the container.
  
• The sorting criterion must define a "strict weak ordering".
  
• Provided by sets, multisets, maps, and multimaps.

Overview of Exception Handling in STL Containers

As mentioned in earlier post containers provide different guarantees in the face of exceptions. In general, the C++ standard library will not leak resources or violate container invariants in the face of exceptions. However, some operations give stronger guarantees (provided the arguments meet some requirements): They may guarantee commit-or-rollback behavior, or they may even guarantee that they will never throw at all. Table below lists all operations that give these stronger guarantees.

For vectors, deques, and lists, you also have guarantees for resize(). It is defined as having the effect of either calling erase() or calling insert() or doing nothing:

void <i>container::</i>resize (size_type num, T value = T()) { if (num > size()) { insert (end(), num-size(), value); } else if (num < size()) { erase (begin()+num, end()); } }
Thus, its guarantees are a combination of the guarantees of erase() and insert().

Table . Container operations with Special Guarantees in Face of Exceptions

Operation		Guarantee
vector::push_back()		Either succeeds or has no effect
vector::insert()		Either succeeds or has no effect if copying/assigning elements doesn't throw
vector::pop_back()		Doesn't throw
vector::erase()		Doesn't throw if copying/assigning elements doesn't throw
vector::clear()		Doesn't throw if copying/assigning elements doesn't throw
vector::swap()		Doesn't throw
deque::push_back()		Either succeeds or has no effect
deque::push_front()		Either succeeds or has no effect
deque::insert()		Either succeeds or has no effect if copying/assigning elements doesn't throw
deque::pop_back()		Doesn't throw
deque::pop_front()		Doesn't throw
deque::erase()		Doesn't throw if copying/assigning elements doesn't throw
deque::clear()		Doesn't throw if copying/assigning elements doesn't throw
deque::swap()		Doesn't throw
list::push_back()		Either succeeds or has no effect
list::push_front()		Either succeeds or has no effect
list::insert()		Either succeeds or has no effect
list::pop_back()		Doesn't throw
list::pop_front()		Doesn't throw
list::erase()		Doesn't throw
list:: clear()		Doesn't throw
list:: remove()		Doesn't throw if comparing the elements doesn't throw
list::remove_if()		Doesn't throw if the predicate doesn't throw
list::unique()		Doesn't throw if comparing the elements doesn't throw
list::splice()		Doesn't throw
list::merge()		Either succeeds or has no effect if comparing the elements doesn't throw
list::reverse()		Doesn't throw
list::swap()		Doesn't throw
[multi]set::insert()		For single elements either succeeds or has no effect
[multi]set::erase()		Doesn't throw
[multi]set::clear()		Doesn't throw
[multi]set::swap()		Doesn't throw if copying/assigning the comparison criterion doesn't throw
[multi]map::insert()		For single elements either succeeds or has no effect
[multi]map::erase()		Doesn't throw
[multi]map::clear()		Doesn't throw
[multi]map::swap()		Doesn't throw if copying/assigning the comparison criterion doesn't throw

-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------

• Complete Tutorial of C++ Template's
• Standard Template Library Tutorial
• Inter Process Communication Tutorial
• Advance Programming in C & C++

-----------------------------------------------------------------

The Art of Learning with Innovation,
eLearning Courses for C and C++ Programming Language - The Most appreciated course !!!

Copyright © ccplusplus.com