C++ Perform an experimental analysis on the singly linked list, doubly linked li

Question

C++

Perform an experimental analysis on the singly linked list, doubly linked list, and vector data structure implementations in the C++ standard library. This will give you an opportunity to see how our big-O efficiency claims relate to real-world performance. It will also give you experience in using the standard data structures, which is essential to industrial-grade C++ programming.

Perform this kind of analysis on the following nine data structure operations:

1. Add to front - singly linked list
2. Add to front - doubly linked list
3. Add to front - vector
4. Add to back - singly linked list
5. Add to back - doubly linked list
6. Add to back - vector
7. Clear - singly linked list
8. Clear - doubly linked list
9. Clear - vector

The following program provided does the following:

1. Ask the user for a value nin units of millions.
2. Constructs a singly linked list, doubly linked list, and vector, and fills each with the same collection of nrandom integers.
3. Makes a temporary copy of the singly linked list and adds a new element to the back of the copied list.
4. Repeats the previous step, but using a doubly linked list instead of a singly linked list.

#include "stdafx.h"

#include <cassert>
#include <cstdlib>
#include <iostream>
#include <forward_list>
#include <list>
#include <vector>

using namespace std;

// Use a constant random number seed so behavior is consistent from run to run.
const int RANDOM_SEED = 0xC0DE;

// int value that is different from all randomly-generated ints.
const int DISTINCT_INT = -1; // Random ints are always non-negative.

// std::forward_list does not have a push back function, so we have to write
// our own.
void forward_list_push_back(forward_list<int>& the_list, int n, int element) {
   forward_list<int>::iterator ptr = the_list.begin();
   for (int i = 0; i < (n - 1); ++i)
       ++ptr;
   the_list.insert_after(ptr, element);
}

int main()
{
   // Seed the random number generator.
   srand(RANDOM_SEED);

   // Query user for structure size n.
   int millions;
   for (bool done = false; !done;) {
       cout << "Enter a positive integer n, in units of millions: ";
       cin >> millions;
       if (cin && (millions > 0)) {
           done = true;
       }
       else {
           cout << "Invalid entry, try again." << endl;
       }
   }
   const int n = millions * 1000000;

   // Build a master forward_list, list, and vector, each containing the
   // same collection of elements, that will be reused for each trial.
   // These data structures are declared const to make sure we don't modify
   // them by mistake.
   cout << "Creating data structures with n=" << millions << " million...";
   vector<int> randoms;
   for (int i = 0; i < n; ++i) {
       randoms.push_back(rand());
   }
   const forward_list<int> master_forward_list(randoms.begin(), randoms.end());
   const list<int> master_list(randoms.begin(), randoms.end());
   const vector<int> master_vector(randoms.begin(), randoms.end());
   randoms.clear();
   cout << "done" << endl;

   // Each of the following trials is in its own anonymous scope, between the
   // { } braces. This makes it so that each trial's local temp variable does
   // not interfere with any of the other trials' code.

   {
       cout << "Add to back - singly linked list" << endl;
       forward_list<int> temp = master_forward_list;
       forward_list_push_back(temp, n, DISTINCT_INT);
   }

   {
       cout << "Add to back - doubly linked list" << endl;
       list<int> temp = master_list;
       temp.push_back(DISTINCT_INT);
   }

   return 0;
}

This program can be used to gather experimental results for operations 4 and 5. Expand the program to cover the remaining seven operations. Your code can follow the pattern established by these first two operations.

Explanation / Answer

#include "stdafx.h"
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <forward_list>
#include <list>
#include <vector>
using namespace std;
// Use a constant random number seed so behavior is consistent from run to run.
const int RANDOM_SEED = 0xC0DE;
// int value that is different from all randomly-generated ints.
const int DISTINCT_INT = -1; // Random ints are always non-negative.
// std::forward_list does not have a push back function, so we have to write
// our own.
void forward_list_push_back(forward_list<int>& the_list, int n, int element) {
forward_list<int>::iterator ptr = the_list.begin();
for (int i = 0; i < (n - 1); ++i)
++ptr;
the_list.insert_after(ptr, element);
}
int main()
{
// Seed the random number generator.
srand(RANDOM_SEED);
// Query user for structure size n.
int millions;
for (bool done = false; !done;) {
cout << "Enter a positive integer n, in units of millions: ";
cin >> millions;
if (cin && (millions > 0)) {
done = true;
}
else {
cout << "Invalid entry, try again." << endl;
}
}
const int n = millions * 1000000;
// Build a master forward_list, list, and vector, each containing the
// same collection of elements, that will be reused for each trial.
// These data structures are declared const to make sure we don't modify
// them by mistake.
cout << "Creating data structures with n=" << millions << " million...";
vector<int> randoms;
for (int i = 0; i < n; ++i) {
randoms.push_back(rand());
}
const forward_list<int> master_forward_list(randoms.begin(), randoms.end());
const list<int> master_list(randoms.begin(), randoms.end());
const vector<int> master_vector(randoms.begin(), randoms.end());
randoms.clear();
cout << "done" << endl;
// Each of the following trials is in its own anonymous scope, between the
// { } braces. This makes it so that each trial's local temp variable does
// not interfere with any of the other trials' code.
{
cout << "Add to back - singly linked list" << endl;
forward_list<int> temp = master_forward_list;
forward_list_push_back(temp, n, DISTINCT_INT);
}
{
cout << "Add to back - doubly linked list" << endl;
list<int> temp = master_list;
temp.push_back(DISTINCT_INT);
}
{
cout<<"Add to the back of vector"<<endl;
vector<int> temp=master_vector;
temp.push_back(DISTINCT_INT);
}

{
cout<<"Clear from singly linked list"<e<ndl;
forward_list<int> temp=master_forward_list;
temp.clear();
}

{
cout<<"Clear from doubly linked list"<<endl;
list<int> temp=master_list;
temp.clear();
}

{
cout<<"Clear from vector"<<endl;
vector<int> temp=master_vector;
temp.clear();
}

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.