## 10. Other containers

### 10.1. Queues

```
Queue();
void insert(T n);
T remove();
void empty();
int length() const;
```

Queue<T> is a template to construct a queue of elements of type T. T can be any type--numerical, pointer or class.

The default constructor constructs an empty queue. The empty operation empties an existing queue. The length operation returns the number of elements currently stored in the queue.

The insert operation adds an element to the tail of the queue, whereas remove removes an element from the head. The head and tail operations return the elements stored at the head and tail.

### 10.2. Priority queues

```
PriorityQueue(int(*comp)(const T&, constT&));
void insert(T n);
T remove();
void empty();
int length() const;
```
PriorityQueue<T> is a template to construct a queue of elements of type T. T can be any type--numerical, pointer or class.

To construct a priority queue, a comparison function comp must be specified. Like all comparison functions in this library, it returns zero if the elements to be compared are undistinguishable, a negative integer if the first argument comes before the second, and a positive integer otherwise.

The length operation returns the number of elements currently stored in the queue.

The insert operation adds an element to the queue. remove removes the smallest element from the priority queue. head returns a copy of the smallest element stored in the priority queue.

### 10.3. Maps

```      Map(int (*hash)(const K&), int (*comp)(const K&, const K&));
void set(const K& key, const V& value);
Bool find(const K& key) const;
Bool find(const K& key, V& value) const;
V get(const K& key) const;
V operator[](const K& key) const;
V& operator[](const K& key);
void empty();
```

Map<K,V> is a map storing (key, value) pairs. For each key in K there is at most one map value in V. The add operation adds a (key, value) pair, removing any previous value that may have been associated with key. The find operation checks whether a value has been associated with key. If so, it returns TRUE. The second version of find sets value to that value. If not, both operations return FALSE and leave value unchanged. The get operation and the overloaded [] operator retrieve a value. Using a nonexistent key with [] is an error. The empty operation removes all entries from the map object.

To construct a map, two functions must be specified: a hash function for the key values, and a comparison function. The comparison function must return 0 if the keys are to be considered identical and a nonzero value otherwise. This is not very intuitive but it is the same protocol used for sort functions. The hash function must return some integer, which should be somewhat randomly distributed, for each key. Don't reduce the hash value by a modulus; the map will take care of that. Of course, keys that compare to be identical must have identical hash values.

```
Map<String, double> m(String::hash, String::compare);
```