C++


cs1C?HW11a All three STL sequence containers, vector, list and deque can hold values, and all three have a push_back() function. However, each is implemented differently. - A vector uses a dynamically-allocated array. When the array is full and an item is pushed, a new larger array is created on the heap. The existing values are copied to the new array and the old array is deleted. When there are few values, the processing penalty of copying the values to a larger aray is not significant. But when there are a large number of values, a vector may not perform as well as a list or deque - A deque uses a series of "chunks", each chunk being a small array. The chunks are linked together by pointers. When a chunk is full and an item is pushed, a new chunk is created on the heap. The existing chunks are not deleted. The new chunk is linked to the existing chunks. When there are few values in a deque, the processing penalty of using pointers to keep track of chunks can be significant, compared to vector or list. However, when there is a large number of values, a deque can process more quickly that a vector because there is no copying of values to a new array as there is with a vector. - A list is implemented a doubly linked list. Unlike a vector or deque, the list is never full (other than running out of memory). Therefore, there is no processing penalty of copying values, like with a vector. Although a list uses pointers, the processing penalty is significantly less than that of a deque. It would seem logical that a list would be the quickest of the three. With 150 million integers being pushed, you might think that a deque would perform better than a vector. Write the following program and see the results. Write a program that pushes 150 million int values into a vector. - Use the push_back() function in a for loop. - Use a timer to measure the time. - (The timer code is given below) Change the program so that 150 million int values into a deque. - Use the push_back() function in a for loop. - Use a timer to measure the time. Change the program again so that 150 million int values into a list. - Use the push_back() function in a for loop. - Use a timer to measure the time.
/* ---- OUTPUT ---------------- list time: XXX seconds. vector time: xXX seconds deque time: xx seconds Here is code for the timer: // Include other headers \#include int main() \{ clock_t start; clock_t end; // declare a vector object of int type start =clock(); for (int i=0;i<150000000;i++ ) \{ // Use the push_back() function to push i into the vector \} end =clock(); cout ? "list time: " (end - start) / CLK_TCK ? " seconds. \ n \ n"; \}