C++


cs1C?HW11 b Unlike list and deque, vector does not have a push_front() funtion. However, vector does have an insert() function that can be used to insert a value at the front ( index [0] ) But remember that before a value can be inserted at the front of a vector, all values must be moved 'down' one to make room for the new value to be inserted at index [0]. This is a very significant processing penalty, O(n) to move all values, just to insert one value at the front. It would seem logical that a list would perform best. When a value is inserted at the front of a list, no values in the list are moved. That is also true with a deque, but deques have additional processing related to keeping track of pointers and periodically creating a new chunk. However, each time a value is inserted at the front of a vector, all array values must be moved. So a vector should perform poorly compared to a list or deque. Write the following program and see the results. Write a program that compares the runtimes of these: - vector insert() - list push_front() - deque push_front() - Using a for loop, insert 300,000 integers into the front of a vector. - Use a timer to measure the time. - Then use a for loop and the push_front() function to push 300,000 integers into a list. - Use a timer to measure the time. - Then use a for loop and the push_front() function to push 300,000 integers into a deque. - Use a timer to measure the time. /* ---- OUTPUT ---------------- list time: XXX seconds. vector time: xxx seconds deque time: xx seconds */
// Comparing runtimes - vector insert() vs list push_front() // vs deque push_front () //(300,000 values ) \#include \#include> \#include \#include \#include \#include using namespace std; int main() \{ clock_t start; clock t end; list ?i? nt > numbers ; vectorvalues; dequeamounts; start = clock (); for (int i=0;i<300000;i++ ) \{ numbers.push_front(i); \} end =clock(); cout ? "list time: " ? (end - start) / CLK_TCK ? " seconds. \n\n"; start =clock(); for (int i=0;i<300000; i++ ) \{ values.insert(values.begin(), i); \} end =clock(); cout ? "vector time: " ? (end - start) / CLK_TCK ? " seconds. ln\n"; start =clock(); for (int i=0;i<300000; i++ ) \{ amounts.push_front(i); \} end =clock(); cout ? "deque time: " ? (end - start) / CLK_TCK ? " seconds. ln\n "; return 0 ; \} 1 * OUTPUT : list time: 0 seconds. vector time: 7 seconds. deque time: 0 seconds. Press any key to continue... . */