10.1 Containers

The fundamental purpose of a container is to store multiple objects in a single container object. Different kinds of containers have different characteristics, such as speed, size, and ease of use. The choice of container depends on the characteristics and behavior you require.

In C++, the containers are implemented as class templates, so you can store anything in a container. (Well, almost anything. The type must have value semantics, which means it must behave as an ordinary value, such as an int. Values can be copied and assigned freely. An original and its copy must compare as equal. Some containers impose additional restrictions.)

10.1.1 Standard Containers

The standard containers fall into two categories: sequence and associative containers. A sequence container preserves the original order in which items were added to the container. An associative container keeps items in ascending order (you can define the order relation) to speed up searching. The standard containers are:

deque: A deque (double-ended queue) is a sequence container that supports fast insertions and deletions at the beginning and end of the container. Inserting or deleting at any other position is slow, but indexing to any item is fast. Items are not stored contiguously. The header is <deque>.
list: A list is a sequence container that supports rapid insertion or deletion at any position but does not support random access. Items are not stored contiguously. The header is <list>.
map
multimap: A map (or dictionary) is an associative container that stores pairs of keys and associated values. The keys determine the order of items in the container. map requires unique keys. multimap permits duplicate keys. The header for map and multimap is <map>.
set
multiset: A set is an associative container that stores keys in ascending order. set requires unique keys. multiset permits duplicate keys. The header for set and multiset is <set>.
vector: A vector is a sequence container that is like an array, except that it can grow as needed. Items can be rapidly added or removed only at the end. At other positions, inserting and deleting items is slower. Items are stored contiguously. The header is <vector>.

The set and map containers perform insertions, deletions, and searches in logarithmic time, which implies a tree or tree-like implementation. Items must be kept in sorted order, so a hash table implementation is not allowed. Many programmers consider the lack of a standard hash table to be a serious omission. When the C++ standard is revised, a hash table is likely to be added. The STLport project includes hash table-based containers. See Appendix B for information about STLport.

10.1.2 Container Adapters

In addition to the standard containers, the standard library has several container adapters. An adapter is a class template that uses a container for storage and provides a restricted interface when compared with the standard containers. The standard adapters are:

priority_queue: A priority queue is organized so that the largest element is always the first. You can push an item onto the queue, examine the first element, or remove the first element. The header is <queue>.
queue: A queue is a sequence of elements that lets you add elements at one end and remove them at the other end. This organization is commonly known as FIFO (first-in, first-out). The header is <queue>.
stack: A stack is a sequence that lets you add and remove elements only at one end. This organization is commonly known as LIFO (last-in, first-out). The header is <stack>.

10.1.3 Pseudo-Containers

The standard library has a few class templates that are similar to the standard containers but fail one or more of the requirements for a standard container:

bitset: Represents a bitmask of arbitrary size. The size is fixed when the bitset is declared. There are no bitset iterators, so you cannot use a bitset with the standard algorithms. See <bitset> in Chapter 13 for details.
basic_string
string
wstring: Represent character strings. The string class templates meet almost all of the requirements of a sequence container, and you can use their iterators with the standard algorithms. Nonetheless, they fall short of meeting all the requirements of a container, such as lacking front and back member functions. The header is <string>.
valarray: Represents an array of numeric values optimized for computational efficiency. A valarray lacks iterators, and as part of the optimization, the compiler is free to make assumptions that prevent valarray from being used with the standard algorithms. See <valarray> in Chapter 13 for details.
vector<bool>: A specialization of the vector template. Although vector<> usually meets the requirements of a standard container, the vector<bool> specialization does not because you cannot obtain a pointer to an element of a vector<bool> object. See <vector> in Chapter 13 for details.

10.1.4 Container Requirements

This section presents the rules that govern containers. Some rules apply to all the standard containers, and you can rely on the standard behavior for all C++ implementations. Other rules apply only to sequence containers, and some apply only to associative containers. If you write your own container class template, be sure to follow the same conventions and rules that apply to the standard containers.

10.1.4.1 Member types

const_iterator: The iterator type for const values.
const_reference: A const lvalue type for the items stored in the container. This is typically the same as the allocator's const_reference type.
difference_type: A signed integral type denoting the difference between two iterators.
iterator: The iterator type.
reference: An lvalue type for the items stored in the container. This is typically the same as the allocator's reference type.
size_type: An unsigned integral type that can hold any nonnegative difference_type value.
value_type: The type of item stored in the container. This is typically the same as the first template parameter.

A container that supports bidirectional iterators should also define the reverse_iterator and const_reverse_iterator types.

An associative container should define key_type as the key type, compare_type as the key compare function or functor, and value_compare as a function or functor that compares two value_type objects.

Optionally, a container can declare pointer and const_pointer as synonyms of the allocator's types of the same name, and allocator_type for the allocator, which is typically the last template parameter.

10.1.4.2 Member functions

Most of the standard member functions have a complexity that is constant or linear in the number of elements in the container. Some of the member functions for associative members are logarithmic in the number of elements in the container. Each of the descriptions in this section notes the complexity of the function.

A container template should have the following constructors. You do not need to write separate constructors in all cases; sometimes you can use default arguments instead of overloading. If an allocator object is supplied, it is copied to the container; otherwise, a default allocator is constructed. In each of the following descriptions, container is the name of the container class template.

container( )
container(allocator_type): Initializes the container to be empty. Complexity is constant.
container(const container& that): Initializes the container with a copy of all the items and the allocator from that. Complexity is linear.

A sequence container should have the following additional constructors:

container(size_type n, const value_type& x)

container(size_type n, const value_type& x, allocator_type)

Initializes the container with n copies of x. Complexity is linear with respect to n.

template<InIter> container(InIter first, InIter last)

template<InIter>

container(InIter first, InIter last, allocator_type)

Initializes the container with copies of the items in the range [first, last). Complexity is linear with respect to last - first.

If InIter is an integral type, the container is initialized with first copies of last (converted to value_type). Complexity is linear with respect to first.

An associative container should have the following additional constructors:

container(key_compare compare)
container(key_compare compare, allocator_type): Initializes an empty container that uses compare to compare keys. Complexity is constant.
template<InIter> container(InIter first , InIter last, key_compare compare)
template<InIter> container(InIter first, InIter last, key_compare compare, allocator_type): Initializes the container with copies of the items in the range [first, last), comparing keys with compare. Complexity is linear.

All containers must have a destructor:

~container( ): Calls the destructor for every object in the container, perhaps by calling clear. Complexity is linear.

Many member functions are the same for all the container templates, and when you write your own container template, you should implement the same member functions with the same behaviors. Some are specific to sequence containers, and some to associative containers. Each container template can define additional members.

iterator begin ( )

const_iterator begin ( ) const

Returns an iterator that points to the first item of the container. Complexity is constant.

void clear ( )

Erases all the items in the container. Complexity is linear.

bool empty ( )

Returns true if the container is empty (size( ) == 0). Complexity is constant.

iterator end ( )

const_iterator end ( ) const

Returns an iterator that points to one past the last item of the container. Complexity is constant. (See Section 10.2 later in this chapter for a discussion of what "one past the last item" means.)

erase (iterator p)

Erases the item that p points to. For a sequence container, erase returns an iterator that points to the item that comes immediately after the deleted item or end( ). Complexity depends on the container.

For an associative container, erase does not return a value. Complexity is constant (amortized over many calls).

erase (iterator first, last)

Erases all the items in the range [first, last). For a sequence container, erase returns an iterator that points to the item that comes immediately after the last deleted item or end( ). Complexity depends on the container.

For an associative container, erase does not return a value. Complexity is logarithmic, plus last - first.

size_type max_size ( )

Returns the largest number of items the container can possibly hold. Although many containers are not constrained, except by available memory and the limits of size_type, other container types, such as an array type, might have a fixed maximum size. Complexity is usually constant.

container& operator= (const container& that)

Erases all items in this container and copies all the items from that. Complexity is linear in size( ) + that.size( ).

size_type size ( )

Returns the number of items in the container. Complexity is usually constant.

void swap (const container& that)

Swaps the elements of this container with that. An associative container also swaps the comparison function or functions. Complexity is usually constant.

Each container should have all of its equality and relational operators defined, either as member functions or, preferably, as functions at the namespace level. Namespace-level functions offer more flexibility than member functions. For example, the compiler can use implicit type conversions on the lefthand operand but only if the function is not a member function.

A container that supports bidirectional iterators should define rbegin and rend member functions to return reverse iterators.

The following functions are optional. The standard containers provide only those functions that have constant complexity.

reference at (size_type n)
const_reference at (size_type n) const: Returns the item at index n, or throws out_of_range if n >= size( ).
reference back ( )
const_reference back ( ) const: Returns the last item in the container. Behavior is undefined if the container is empty.
reference front ( )
const_reference front ( ) const: Returns the first item in the container. Behavior is undefined if the container is empty.
reference operator[] (size_type n)
const_reference operator[] (size_type n): Returns the item at index n. Behavior is undefined if n >= size( ).
void pop_back ( ): Erases the last item in the container. Behavior is undefined if the container is empty.
void pop_front ( ): Erases the first item in the container. Behavior is undefined if the container is empty.
void push_back (const value_type& x): Inserts x as the new last item in the container.
void push_front (const value_type& x): Inserts x as the new first item in the container.

A sequence container should define the following member functions. The complexity of each depends on the container type.

iterator insert (iterator p, const value_type& x): Inserts x immediately before p and returns an iterator that points to x.
void insert (iterator p, size_type n,
const value_type& x): Inserts n copies of x before p.
template<InIter>
void insert (iterator p, InIter first, InIter last): Copies the values from [first, last) and inserts them before p.

An associative container should define the following member functions. In the descriptions of the complexity, N refers to the number of elements in the container, M refers to the number of elements in the argument range (e.g., last - first), and count is the value that the function returns. Some of these member functions seem to duplicate standard algorithms (as discussed in Section 10.3 later in this chapter), but the associative containers can implement them with better performance than the generic algorithms.

size_type count(const key_type& k) const: Returns the number of items equivalent to k. Complexity is log N + count.
pair<const_iterator,const_iterator>
equal_range(const key_type& k) const
pair<iterator,iterator> equal_range(const key_type& k): Returns the equivalent of make_pair(lower_bound(k), upper_bound(k)). Complexity is log N.
size_type erase(const key_type& k): Erases all the items equivalent to k. Returns the number of items erased. Complexity is log N + count.
const_iterator find(const key_type& k) const
iterator find(const key_type& k): Finds an item equivalent to k and returns an iterator that points to one such item, or end( ) if not found. Complexity is log N.
insert(const value_type& x): Inserts x. If the container permits duplicate keys, insert returns an iterator that points to the newly inserted item. If the container requires unique keys, insert returns pair<iterator,bool>, in which the first element of the pair is an iterator that points to an item equivalent to x, and the second element is true if x was inserted or false if x was already present in the container. Complexity is log N.
iterator insert(iterator p, const value_type& x): Inserts x and returns an iterator that points to x. The iterator p hints to where x might belong. Complexity is log N in general, but is constant (amortized over many calls) if the hint is correct, that is, if x is inserted immediately after p.
template<InIter>
void insert(InIter first, InIter last): Copies the items from [first, last) and inserts each item in the container. Complexity is M log(N + M), but is linear if the range is already sorted.
key_compare key_comp( ) const: Returns the key compare function or functor. Complexity is constant.
const_iterator lower_bound(const key_type& k) const
iterator lower_bound(const key_type& k): Returns an iterator that points to the first item in the container that does not come before k. That is, if k is in the container, the iterator points to the position of its first occurrence; otherwise, the iterator points to the first position where k should be inserted. Complexity is log N.
value_compare value_comp( ) const: Returns the value compare function or functor. Complexity is constant.
const_iterator upper_bound(const key_type& k) const
iterator upper_bound(const key_type& k): Returns an iterator that points to the first item in the container that comes after all occurrences of k. Complexity is log N.

10.1.4.3 Exceptions

The standard containers are designed to be robust in the face of exceptions. The exceptions that the containers themselves can throw are well-defined (for example, at might throw out_of_range), and most member functions do not throw any exceptions of their own.

If a single value is being added to a container (by calling insert, push_front, or push_back), and an exception is thrown, the container remains in a valid state without adding the value to the container.

When inserting more than one value, different containers have different behaviors. A list, for example, ensures that all items are inserted or none, that is, if an exception is thrown, the list is unchanged. A map or set, however, ensures only that each individual item is inserted successfully. If an exception is thrown after inserting some of the items from a range, the destination container retains the elements that had been inserted successfully.

The erase, pop_back, and pop_front functions never throw exceptions.

The swap function throws an exception only if an associative container's Compare object's copy constructor or assignment operator throws an exception.

Example 10-1 shows an slist container, which implements a singly-linked list. A singly-linked list requires slightly less memory than a doubly-linked list but offers, at best, a forward iterator, not a bidirectional iterator.

Example 10-1. Implementing a custom container: a singly-linked list

// Simple container for singly-linked lists.

template<typename T, typename Alloc = std::allocator<T> >

class slist {

  // Private type for a link (node) in the list.

  template<typename U>

  struct link {

    link* next;

    U value;

  };

  typedef link<T> link_type;



public:

  typedef typename Alloc::reference reference;

  typedef typename Alloc::const_reference const_reference;

  typedef typename Alloc::pointer pointer;

  typedef typename Alloc::const_pointer const_pointer;

  typedef Alloc allocator_type;

  typedef T value_type;

  typedef size_t size_type;

  typedef ptrdiff_t difference_type;



  class iterator;       // See Section 10.2 later in this chapter for 

  class const_iterator; // the iterators.



  slist(const slist& that);

  slist(const Alloc& alloc = Alloc(  ));

  slist(size_type n, const T& x, const Alloc& alloc=Alloc(  ));

  template<typename InputIter>

  slist(InputIter first, InputIter last,

        const Alloc& alloc = Alloc(  ));

  ~slist(  )                             { clear(  ); }



  slist& operator=(const slist& that);

  allocator_type get_allocator(  ) const { return alloc_; }



  iterator begin(  )           { return iterator(0, head_); }

  const_iterator begin(  ) const

    { return const_iterator(0, head_); }

  iterator end(  )             { return iterator(0, 0); }

  const_iterator end(  ) const { return const_iterator(0, 0); }



  void pop_front(  )                  { erase(begin(  )); }

  void push_front(const T& x)         { insert(begin(  ), x); }

  T front(  )                   const { return head_->value; }

  T& front(  )                        { return head_->value; }



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

  void insert(iterator p, size_type n, const T& x);

  template<typename InputIter>

  void insert(iterator p, InputIter first, InputIter last);



  iterator erase(iterator p);

  iterator erase(iterator first, iterator last);



  void clear(  )               { erase(begin(  ), end(  )); }

  bool empty(  )         const { return size(  ) == 0; }

  size_type max_size(  ) const

    { return std::numeric_limits<difference_type>::max(  ); }

  void resize(size_type sz, const T& x = T(  ));

  size_type size(  )     const { return count_; }

  void swap(slist& that);



private:

  typedef typename

    allocator_type::template rebind<link_type>::other

    link_allocator_type;



  link_type* newitem(const T& x, link_type* next = 0);

  void delitem(link_type* item);



  template<typename InputIter>

  void construct(InputIter first, InputIter last,

                 is_integer_tag);



  template<typename InputIter>

  void construct(InputIter first, InputIter last,

                 is_not_integer_tag);



  link_type* head_;

  link_type* tail_;

  size_t count_;

  allocator_type alloc_;

  link_allocator_type linkalloc_;

};



// Constructor. If InputIter is an integral type, the standard requires the

// constructor to interpret first and last as a count and value, and perform the

// slist(size_type, T) constructor. Use the is_integer trait to dispatch to the

// appropriate construct function, which does the real work.

template<typename T, typename A>

template<typename InputIter>

slist<T,A>::slist(InputIter first, InputIter last,

                  const A& alloc)

: alloc_(alloc), linkalloc_(link_allocator_type(  )),

  head_(0), tail_(0), count_(0)

{

  construct(first, last, is_integer<InputIter>::tag(  ));

}



template<typename T, typename A>

template<typename InputIter>

void slist<T,A>::construct(InputIter first, InputIter last,

                           is_integer_tag)

{

  insert(begin(  ), static_cast<size_type>(first),

         static_cast<T>(last));

}



template<typename T, typename A>

template<typename InputIter>

void slist<T,A>::construct(InputIter first, InputIter last,

                           is_not_integer_tag)

{

  insert(begin(  ), first, last);

}



// Private function to allocate a new link node.

template<typename T, typename A>

typename slist<T,A>::link_type*

   slist<T,A>::newitem(const T& x, link_type* next)

{

  link_type* item = linkalloc_.allocate(1);

  item->next = next;

  alloc_.construct(&item->value, x);

  return item;

}



// Private function to release a link node.

template<typename T, typename A>

void slist<T,A>::delitem(link_type* item)

{

  alloc_.destroy(&item->value);

  linkalloc_.deallocate(item, 1);

}



// Basic insertion function. All insertions eventually find their way here.

// Inserting at the head of the list (p == begin(  )) must set the head_ member.

// Inserting at the end of the list (p == end(  )) means appending to the list,

// which updates the tail_'s next member, and then sets tail_. Anywhere else in

// the list requires updating p.prev_->next. Note that inserting into an empty

// list looks like inserting at end(  ). Return an iterator that points to the

// newly inserted node.

template<typename T, typename A>

typename slist<T,A>::iterator

  slist<T,A>::insert(iterator p, const T& x)

{

  // Allocate the new link before changing any pointers. If newitem throws an

  // exception, the list is not affected.

  link_type* item = newitem(x, p.node_);

  if (p.node_ == 0) {

    p.prev_ = tail_;

    // At end

    if (tail_ == 0)

      head_ = tail_ = item; // Empty list

    else {

      tail_->next = item;

      tail_ = item;

    }

  }

  else if (p.prev_ == 0)

    head_ = item;          // New head of list

  else

    p.prev_->next = item;

  p.node_ = item;

  ++count_;

  return p;

}



// Erase the item at p. All erasures come here eventually. If erasing begin(  ),

// update head_. If erasing the last item in the list, update tail_. Update the

// iterator to point to the node after the one being deleted.

template<typename T, typename A>

typename slist<T,A>::iterator slist<T,A>::erase(iterator p)

{

  link_type* item = p.node_;

  p.node_ = item->next;

  if (p.prev_ == 0)

    head_ = item->next;

  else

    p.prev_->next = item->next;

  if (item->next == 0)

    tail_ = p.prev_;

  --count_;

  delitem(item);

  return p;

}



// Comparison functions are straightforward.

template<typename T>

bool operator==(const slist<T>& a, const slist<T>& b)

{

  return a.size(  ) == b.size(  ) &&

         std::equal(a.begin(), a.end(  ), b.begin(  ));

}

10.1.5 Using Containers

A container holds stuff. Naturally, you need to know how to add stuff to a container, remove stuff from a container, find stuff in a container, and so on.

10.1.5.1 Value type requirements

Every container stores values and imposes certain restrictions on the values' types. Most important, the value must be copyable and assignable. The result of the copy constructor or assignment operator must be an exact copy of the original. (Note that you cannot store auto_ptr<> objects in a container because copies are not exact duplicates.)

In a sequence container, operator== is used to compare objects when searching. If you compare entire containers with any relational operators, the value types must also support operator<. All the relational operators are defined in terms of operator== and operator<.

In an associative container, values are stored in ascending order according to a comparison function or functor that you supply. The default is std::less<>, which uses operator<. Two objects A and B are considered to be equal (more precisely, equivalent) when A < B is false and B < A is false, so there is no need for operator==.

10.1.5.2 Inserting values

To add an item to a container, call an insert member function. Sequence containers might also have push_front or push_back to insert an item at the beginning or end of the sequence. The push_front and push_back members exist only if they can be implemented in constant time. (Thus, for example, vector does not have push_front.)

Every container has an insert(iter, item) function, in which iter is an iterator and item is the item to insert. A sequence container inserts the item before the indicated position. Associative containers treat the iterator as a hint: if the item belongs immediately after the iterator's position, performance is constant instead of logarithmic.

Sequence containers have additional insert functions: for inserting many copies of an item at a position and for copying a range to a given position. Associative containers have additional insert functions for inserting an item (with no positional hint) and for copying a range into the container.

10.1.5.3 Erasing values

To remove an item from a container, call an erase member function. All containers have at least two erase functions: one that takes a single iterator to delete the item that the iterator points to, and another two iterators to delete every item in the range. Associative containers also have an erase function that takes a value as an argument to erase all matching items.

The standard containers are designed to be used with the standard iterators (see Section 10.2 later in this chapter) and standard algorithms (see Section 10.3 later in this chapter). The standard algorithms offer much more functionality than the containers' member functions, but they also have limitations. In particular, the standard algorithms cannot insert or erase items. For example, among the standard algorithms are remove and remove_if. Their names are suggestive but misleading. They do not remove anything from the container. Instead, they rearrange the elements of the container so that the items to retain are at the beginning. They return an iterator that points to the first item to be erased. Call erase with this iterator as the first argument and end( ) as the second to erase the items from the container. This two-step process is needed because an iterator cannot erase anything. The only way to erase an item from a container is to call a member function of the container, and the standard algorithms do not have access to the containers, only to iterators. Example 10-2 shows how to implement a generic erase function that calls remove and then the erase member function.

Example 10-2. Removing matching items from a sequence container

// Erase all items from container c that are equal to item.

template<typename C>

void erase(C& c, const typename C::value_type& item)

{

  c.erase(std::remove(c.begin(), c.end(  ), item), c.end(  ));

}



template<typename C, typename Pred>

void erase_if(C& c, Pred pred)

{

  c.erase(std::remove_if(c.begin(), c.end(  ), pred), c.end(  ));

}



int main(  )

{

  std::list<int> lst;

  ...

  // Erase all items == 20.

  erase(lst, 20);

  ...

  // Erase all items < 20.

  erase_if(lst, std::bind2nd(std::less<int>(  ), 20));

  ...

}

10.1.5.4 Searching

The standard algorithms provide several ways to search for items in a container: adjacent_find, find, find_end, first_first_of, find_if, search, and search_n. These algorithms essentially perform a linear search of a range. If you know exactly which item you want, you can search an associative container much faster by calling the find member function. For example, suppose you want to write a generic function, contains, that tells you whether a container contains at least one instance of an item. Example 10-3 shows one way, which relies on find, to implement this function.

Example 10-3. Determining whether a container contains an item

// Need a type trait to tell us which containers are associative and which are

// not (see Chapter 8).

struct associative_container_tag {};

struct sequence_container_tag {};



template<typename C>

struct is_associative

{};



template<typename T, typename A>

struct is_associative<std::list<T,A> >

{

  typedef sequence_container_tag tag;

};

// Ditto for vector and deque



template<typename T, typename C, typename A>

struct is_associative<std::set<T,C,A> >

{

  typedef associative_container_tag tag;

};

// Ditto for multiset, map, and multimap



template<typename C, typename T>

inline bool do_contains(const C& c, const T& item,

                        associative_container_tag)

{

  return c.end(  ) != c.find(item);

}



template<typename C, typename T>

inline bool do_contains(const C& c, const T& item,

                        sequence_container_tag)

{

  return c.end() != std::find(c.begin(  ), c.end(  ), item);

}



// Here is the actual contains function. It dispatches to do_contains, picking

// the appropriate overloaded function depending on the type of the container c.

template<typename C, typename T>

bool contains(const C& c, const T& item)

{

  return do_contains(c, item, is_associative<C>::tag(  ));

}

As you can see, iterators are important for using containers. You need them to insert at a specific position, identify an item for erasure, or specify ranges for algorithms. The next section discusses iterators in more depth.