CS代写 CE221 Part 8

Programming in C++ Part 8
The list and deque classes,
Container Adapters, Associative Containers
18/11/2019 CE221 Part 8

Copyright By PowCoder代写 加微信 powcoder

The list Class 1
The list container is a sequence container that stores the sequence as dynamically-allocated cells each containing a pointer to a data item and pointers to the previous and next in the list. This means that no shifting is necessary when adding items to the beginning or middle or deleting them. However accessing items non-sequentially is not efficient so no subscripting or at functions are provided.
The space overheads may be significant if the items in the list do not use much memory – a linked list of numbers will occupy about twice as much memory as a vector of the same capacity.
Iterators for list objects are bidirectional – they support ++ and –, but not + and +=.
18/11/2019 CE221 Part 8

The list Class 2
The no-argument list constructor initialises the list to be empty. There is also a two-argument constructor – the first argument is a repetition count and the second a value: list l(3, 4) will initialise l to hold 3 copies of the value 4. (The second argument may be omitted in which case the value 0, or equivalent, will be used).
The first or last item of a list may be accessed using front or back and removed using pop_front or pop_back. Note that the effect of these functions when a list is empty is unpredictable. There is no member function to remove items at other specified locations; to do this we need to use the iterator erase function.
18/11/2019 CE221 Part 8

The list Class 3
In addition to push_back the list class has a push_front
member function for insertion at the front.
There are insert methods that takes an iterator as the first argument; additional arguments are supplied in the same way as the methods from the vector class.
#include list l;
l.push_back(3);
l.push_front(4); l.insert(++l.begin(), 44);
for (int i:l) // assuming C++ 11
cout << i << " " cout << endl; // output will be 4 44 3 18/11/2019 CE221 Part 8 The list Class 4 All occurrences of a particular value may be removed using the remove function list l(4, 5); // 5 5 5 5 l.insert(++l.begin(), 7); // 5 7 5 5 5 list::iterator pos = find(l.begin(),
l.insert(pos, 8); l.push_front(7); l.remove(7); cout << l.back(); l.pop_front(); l.end(), 7); // 587 5 55 // 758 7 555 // 585 5 5 // 5 will be output // 855 5 18/11/2019 CE221 Part 8 The list Class 5 There is also a remove_if function that removes all values that satisfy a condition; the argument is a pointer to a function that takes a data item as its argument and returns a boolean value indicating whether that item satisfies the condition. To remove all upper-case letters from a list l1 of type list we could use l1.remove_if(isupper).
The following code will remove all negative values from the list l2 of type list.
bool isneg(int i) { return i<0; l2.remove_if(isneg); 18/11/2019 CE221 Part 8 The list Class 6 We cannot use the sort algorithm to sort lists, since they do not support random-access iterators. Hence there are two sort member functions to sort a list into ascending order; a no- argument version that sorts using < and a version with one argument similar to the last argument of the three-argument sort algorithm. The function unique will remove from the list all but one of any sequence of adjacent equal items. If we want to eliminate all duplicate items from a list we need to sort it first so that equal items are adjacent. (Items are tested for equality using == so if the items in the list are objects of a class that class must have an == operator.) 18/11/2019 CE221 Part 8 The list Class 7 The splice function can be used to move all of the elements of one list into another. l1.splice(pos, l2) moves all of the elements of l2 into l1 immediately in front of the element referenced by the iterator pos. After this l2 will be empty. Note that no copying of elements takes place – only the pointers in the list cells are changed. The function can take extra arguments to allow part of l2 to be moved. The merge function can be used to move all of the elements of a sorted list into another, with the result being sorted. s1.merge(s2) moves all of the elements of s2 into s1 in appropriate positions to maintain correct ordering. If either of the lists is not sorted the order of elements is unpredictable. The functions can take an extra comparator argument (as described on slides 30-31 of part 7) to specify the ordering. 18/11/2019 CE221 Part 8 The deque Class The deque container (pronounced as "deck" and being an abbreviation of double-ended queue) is similar to vector but supports efficient addition and removal at both ends. In order to achieve this it is not possible for subscripting to be as efficient as for vectors, but it is still relatively efficient. The deque class provides all of the functionality of vector and additionally push_front, pop_front, front and back functions. Programs that use this container need to include the header file .
18/11/2019 CE221 Part 8

The stack and queue Adaptors
The stack and queue container adaptors provide wrappers around sequence containers to allow them to be used as stacks and queues. A stack is a first-in-last-out sequence; items can be added to and removed from the top only and the only item that can be accessed directly is the top item. On the other hand a queue is a first-in-first-out sequence; items are added at the back but removed from the front and the1 only items that can be accesseddirectlyarethefrontandback items.
A program that uses one of these adaptors requires the use of #include or #include .
1 In data structures courses it is normally assumed that the only item that can be accessed directly is the front one, but the C++ adaptor also allows access to the back one.
18/11/2019 CE221 Part 8

The stack Class 1
The stack class by default is implemented using a deque, but we may if we wish obtain a stack that is implemented using a vector or a list:
stack s1; // uses deque stack> s2; // uses vector
We may initialise a stack to contain the contents of an existing sequence object of the same type as the class being used to implement the stack; the first item in the sequence will be at the bottom of the stack:
list l;
stack> s3(l);
18/11/2019 CE221 Part 8

The stack Class 2
The main member functions of the stack class are push, pop and top. These are implemented using the functions push_back, pop_back, and back. pop and top have undefined behaviour if the stack is empty. In addition member functions empty and size (as described in part 6) are provided.
#include
stack st;
st.push(5);
st.push(4);
while (!st.empty())
{ cout << st.top() << endl; st.pop(); } 18/11/2019 CE221 Part 8 The queue Class 1 The queue class by default also uses a deque, but we may if we wish obtain a queue that is implemented using a list (but not a vector since the vector class does not support pop_front): #include
queue q1; // uses deque
queue> q2; // uses list
As with stacks we may initialise a queue to contain of the contents of an existing sequence object of the appropriate type; the first item in the sequence will be at the front of the queue.
18/11/2019 CE221 Part 8

The queue Class 2
The main member functions of the queue class are push, pop, front and back. The last three have undefined behaviour if the queue is empty. The push function adds to the back and the pop function removes the front element. Once again member functions empty and size are provided.
queue q; q.push(‘x’); q.push(‘y’);
cout << "back is " << q.back() << endl; // y while (!q.empty()) { cout << q.front() << endl; } // x will be output, then y 18/11/2019 CE221 Part 8 The priority_queue Class 1 A priority queue is like a queue but items have priorities and when an item is added to the back it will advance ahead of any items with lower priority. The order in which items with equal priority will reach the head of the queue not defined. The precise state of the queue at any stage is also not defined, but it is always guaranteed that the head item will not have a lower priority than any other items in the queue. The implementation of a priority queue normally uses a data structure called a heap; this may be efficiently implemented using any sequence with random-access iterators. The priority_queue class by default uses a vector, but we may obtain a queue that is implemented using a deque. 18/11/2019 CE221 Part 8 The priority_queue Class 2 Programs that use the priority_queue adaptor need to use #include .
Priorities are by default compared using the < operator; in most applications the items in the queue will be class objects with the priority being a member of the class; we would need to write an operator< function for the class such that a, MyComp> pq;
18/11/2019 CE221 Part 8