#include <iostream>
#include <list>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <chrono>
#include <string>
#include "BSTree.h"
//<todo> include file for BST here <todo>
using namespace std;
class Student {
public:
int id;
string name;
// Constructor
Student(int _id, const string& _name) : id(_id), name(_name) {}
// Override equality operator for search
bool operator==(const Student& other) const {
return id == other.id && name == other.name;
}
bool operator>(const Student& other) const {
return id > other.id;
}
bool operator<(const Student& other) const {
return id < other.id;
}
};
vector<Student> arrayData;
list<Student> linkedListData;
unordered_map<int, Student> hashTableData;
BinarySearchTree<Student> bstData;
//<todo> declare bstData here
void generateRandomData(int numRecords) {
for (int i = 0; i < numRecords; ++i) {
Student student(i, "Student" + to_string(i));
arrayData.push_back(student);
linkedListData.push_back(student);
hashTableData.emplace(i, student);
bstData.insert(student);
//<todo> add studtent to bstData
}
}
list<Student>::iterator searchInList(list<Student>& studentList, const Student& target) {
return find(studentList.begin(), studentList.end(), target);
}
void benchmarkSearch(const Student& target) {
// Benchmark array search
auto arrayStart = chrono::high_resolution_clock::now();
auto arrayResult = find(arrayData.begin(), arrayData.end(), target);
auto arrayEnd = chrono::high_resolution_clock::now();
cout << "Array Search Time: " << chrono::duration_cast<chrono::microseconds>(arrayEnd - arrayStart).count() << " microseconds" << endl;
// Benchmark linked list search
auto listStart = chrono::high_resolution_clock::now();
auto listResult = searchInList(linkedListData, target);
auto listEnd = chrono::high_resolution_clock::now();
cout << "Linked List Search Time: " << chrono::duration_cast<chrono::microseconds>(listEnd - listStart).count() << " microseconds" << endl;
// Benchmark hash table search
auto hashTableStart = chrono::high_resolution_clock::now();
auto hashTableResult = hashTableData.find(target.id);
auto hashTableEnd = chrono::high_resolution_clock::now();
cout << "Hash Table Search Time: " << chrono::duration_cast<chrono::microseconds>(hashTableEnd - hashTableStart).count() << " microseconds" << endl;
// Benchmark BST search
auto bstStart = chrono::high_resolution_clock::now();
auto bstResult = bstData.search(target);
auto bstEnd = chrono::high_resolution_clock::now();
cout << "Binary search tree time is: " << chrono::duration_cast<chrono::microseconds>(bstEnd - bstStart).count() << " microseconds" << endl;
//<todo> add code to Benchmark BST here
}
int main() {
//<todo> change the size of numRecords in order to be able to fill in
//the provided excel Table. Run and documents output after each change.
const int numRecords = 100000;
generateRandomData(numRecords);
// Example target record
//<q1> Will the numbers change in any meaningful way if we change the below line to:
//Student target(10, "Student10");
//Think before you asnwer this question and then validate what you think will happnen by actually running
//the code with several input sizes.
//Explain the reason for the change or the lack of change depending on your findings.
Student target(100000, "Student100000");
// Benchmark search operation
benchmarkSearch(target);
return 0;
}
Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}