|
|
|
10.1 ContainersThe 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 ContainersThe 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:
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 AdaptersIn 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:
10.1.3 Pseudo-ContainersThe 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:
10.1.4 Container RequirementsThis 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
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 functionsMost 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.
A sequence container should have the following additional constructors:
An associative container should have the following additional constructors:
All containers must have a destructor:
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.
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.
A sequence container should define the following member functions. The complexity of each depends on the container type.
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.
10.1.4.3 ExceptionsThe 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 ContainersA 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 requirementsEvery 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 valuesTo 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 valuesTo 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 SearchingThe 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. |
|
|
|