Professional C__ - Marc Gregoire [300]
typedef Container Requirements
The C++ standard specifies that every STL container must provide the following public typedefs:
TYPE NAME DESCRIPTION
value_type The element type stored in the container
reference A reference to the element type stored in the container
const_reference A reference to a const element type stored in the container
iterator The type for iterating over elements of the container
const_iterator A version of iterator for iterating over const elements of the container
size_type A type that can represent the number of elements in the container; usually just size_t (from difference_type A type that can represent the difference of two iterators for the container; usually just ptrdiff_t (from Here are the definitions in the hashmap class of all these typedefs except iterator and const_iterator. Writing an iterator is covered in detail in a subsequent section. Note that value_type (plus key_type and mapped_type, which are discussed later) was already defined in our previous version of the hashmap: template typename Hash = DefaultHash class hashmap { public: typedef Key key_type; typedef T mapped_type; typedef pair typedef pair typedef const pair typedef size_t size_type; typedef ptrdiff_t difference_type; // Remainder of class definition omitted for brevity }; Code snippet from Hashmap\FinalHashmap\hashmap.h Method Container Requirements In addition to the typedefs, every container must provide the following methods: METHOD DESCRIPTION WORST CASE COMPLEXITY Default Constructor Constructs an empty container Constant Copy constructor Performs a deep copy of the container Linear Move constructor Performs a C++11 move constructing operation Constant Copy Assignment operator Performs a deep copy of the container Linear Move Assignment operator Performs a C++11 move assignment operation Constant Destructor Destroys dynamically allocated memory; calls destructor on all elements left in container Linear iterator begin(); const_iterator begin() const; Returns an iterator referring to the first element in the container Constant iterator end(); const_iterator end() const; Returns an iterator referring to the last+1 element in the container Constant const_iterator cbegin() const; Returns a const iterator referring to the first element in the container Constant const_iterator cend() const; Returns a const iterator referring to the last+1 element in the container Constant operator== operator!= operator< operator> operator<= operator>= Comparison operators that compare two containers, element by element Linear void swap(Container&); Swaps the contents of the container passed to the method with the object on which the method is called Constant size_type size() const; Returns the number of elements in the container Constant size_type max_size() const; Returns the maximum number of elements the container can hold Constant bool empty() const; Specifies whether the container has any elements Constant In this hashmap example, we omit the comparison operators. Implementing them would be a good exercise for the reader. The following code extract shows the declarations of all the remaining methods except for begin(), end(), cbegin() and cend(). Those are covered in the next section. template typename Hash = DefaultHash class hashmap { public: // typedefs omitted for brevity // Constructors explicit hashmap(const Compare& comp = Compare(), const Hash& hash = Hash()) throw(invalid_argument); // destructor, copy constructor, move constructor, // copy assignment operator and move assignment operator ~hashmap(); hashmap(const hashmap hashmap(hashmap hashmap