C++ Programming: data structures This one will be based on an array, but will pr
ID: 3782494 • Letter: C
Question
C++ Programming: data structures
This one will be based on an array, but will provide more features than a plain old array. You will implement the following as part of your class, which we will call 'FancyList':
* a private pointer to an array of integers called 'arrayPtr'
* a private int called size, and an accessor and mutator for size -- size will start at 0 and increase every time a new item is added
* a private int called maxSize that will be used to initialize your array. maxSize will default to 10
* a constructor and overloaded constructor. the overloaded version supplies a new value for maxSize to choose how big the array should be
* a public method addItem that uses the current size to figure out where to put the new item in the array pointed to by 'arrayPtr' (our list). If the size == maxSize, then maxSize will be increased by double, and the array will be copied to a larger array and the old array will be deleted, and the new array will be pointed to by arrayPtr
* overloaded operators: >>, == (insertion and equality). The == operator will return true if all items are the same and in the same order. The >> operator will be used to display the contents of the list.
* a destructor that will delete the arrayPtr to avoid memory leaks
* a public method that will return the array as a std::vector
* instead of hard coding an array of integers, use templates to allow other types
* implement the addition + operator so two lists can be merged into one larger list
In your application file, make sure to create an instance of FancyList with the default and then the overloaded constructor. Demonstrate all methods in use.
Explanation / Answer
#include <iostream>
#include <vector>
#include <cstdint>
#include <cstdlib>
using namespace std;
const int SIZE = 1000000;
uint64_t g_val[SIZE];
static __inline__ unsigned long long rdtsc(void)
{
unsigned hi, lo;
__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}
int func1(int x)
{
int v[x];
int vmax = 0;
int vmin = x;
for(int i = 0; i < x; i++)
{
v[i] = rand() % x;
if (v[i] > vmax)
vmax = v[i];
if (v[i] < vmin)
vmin = v[i];
}
int avg = (vmax + vmin) / 2;
int count = 0;
for(int i = 0; i < x; i++)
{
if (v[i] > avg)
{
count++;
}
}
return count;
}
int func2(int x)
{
vector<int> v;
v.resize(x);
int vmax = 0;
int vmin = x;
for(int i = 0; i < x; i++)
{
v[i] = rand() % x;
if (v[i] > vmax)
vmax = v[i];
if (v[i] < vmin)
vmin = v[i];
}
int avg = (vmax + vmin) / 2;
int count = 0;
for(int i = 0; i < x; i++)
{
if (v[i] > avg)
{
count++;
}
}
return count;
}
int func3(int x)
{
vector<int> v;
int vmax = 0;
int vmin = x;
for(int i = 0; i < x; i++)
{
v.push_back(rand() % x);
if (v[i] > vmax)
vmax = v[i];
if (v[i] < vmin)
vmin = v[i];
}
int avg = (vmax + vmin) / 2;
int count = 0;
for(int i = 0; i < x; i++)
{
if (v[i] > avg)
{
count++;
}
}
return count;
}
void runbench(int (*f)(int), const char *name)
{
srand(41711211);
uint64_t long t = rdtsc();
int count = 0;
for(int i = 20; i < 200; i++)
{
count += f(i);
}
t = rdtsc() - t;
cout << "count = " << count << endl;
cout << name << " time in clocks per iteration " << dec << t << endl;
}
struct function
{
int (*func)(int);
const char *name;
};
#define FUNC(f) { f, #f }
function funcs[] =
{
FUNC(func1),
FUNC(func2),
FUNC(func3),
};
int main()
{
for(size_t i = 0; i < sizeof(funcs)/sizeof(funcs[0]); i++)
{
runbench(funcs[i].func, funcs[i].name);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.