Objectives: • Implement more advanced data structure. • Practice using basic C++
ID: 3919299 • Letter: O
Question
Objectives:
• Implement more advanced data structure.
• Practice using basic C++ data structures.
• Practice working with C++ classes.
• Practice working with partially provided code.
Introduction:
There are times when certain simple functionality is best achieved by a data structure that builds on top of other, standard, data structures. Consider this example scenario. In our code, we are dealing with key/value pairs of integers. These are pairs of integers where the first integer is called key, and the second integer is called value. We want to store all key/value pairs such that for each key we know which values and in what order we have inserted. For example, for the following key/value pairs (0, 2),(?1, 3),(3, 7),(0, 5),(3, 2),(3, 5),(?1, 3),(?1, 0) we would like to be able to retrieve sequence (3, 3, 0) for key ?1, sequence (2, 5) for key 0 and (7, 2, 5) for key 3.
Your task is to extend partially implemented, and provided to you, key_value_sequences class, to provide exactly that functionality. So for example, this simple code (that roughly corresponds to the example above):
key_value_sequences A;
A.insert(0, 2);
A.insert(-1, 3);
A.insert(3, 2);
A.insert(0, 5);
A.insert(3, 7);
A.insert(3, 5);
A.insert(-1, 3);
A.insert(-1, 0);
auto p = A.data(3);
for (int i = 0; i < A.size(3); ++i) std::cout << p[i] << " ";
when compiled with properly implemented key_value_sequences should produce: 2 7 5.
As usually, your implementation has to be efficient and you have to work under certain constraints. Specifically, you cannot use any external or standard C++ headers except of , and .
Hints:
The simplest and reasonably efficient approach to this assignment is to use a combination of double-linked list (std::list<>) and vector (std::vector<>). Do not be afraid to make a list of vectors or vector of lists. Do not hesitate to leverage std::list<>::iterator, it is a type as any other C++ type. std::vector<> provides method data() that perfectly meets requirements you will need to implement method data() in key_value_sequences. This is one of many ways in which this problem can be approached.
Instructions:
Implement missing elements in a3.hpp taking into account the following:
(a) a3.hpp is the only file you are allowed to modify. a3.cpp is a simple test program demonstrating functionality that your implementation of key_value_sequences must support. You must use it to perform the most basic initial testing of your code. If your code fails to work with a3.cpp you will not be graded. You are not allowed to make any changes to a3.cpp.
(b) Analyze carefully a3.hpp and a3.cpp to better understand key_value_sequences. This class should implement functionality of multiple sequences, where each sequence stores integers and is “identified” by an integer key.
(c) Missing parts of the code that you are expected to implement are marked with IMPLEMENT ME. In short, you have to implement three critical methods: insert(), size() and data().
(d) Method insert() is the workhorse of the class. Its purpose is to take a key/value pair, i.e. two integers, and push back the second integer (which is a value) into the sequence identified by the first integer (which is a key). This is the only modifying method.
(e) Method data() is the main method to access the stored values. Its purpose is to take one integer (which is a key), and return a pointer to a sequence of all integers inserted with that key. If no element had been inserted with given key it should return nullptr. If a sequence exists for the key, the method should return pointer to the continuous block with that sequence. Elements in the sequence must be in the same order in which they had been inserted (refer to examples above).
(f) Method size() is another access method. Its purpose is to take one integer (which is a key), and return the total number of elements inserted with that key. If no element had been inserted with given key the method should return 0.
(g) You can add, remove or modify code in key_value_sequences without limits as long as it correctly compiles and executes with the provided a3.cpp and the only included headers are , , . To compile a3.cpp with your a3.hpp you should use basic compiler setting, e.g.: g++ -std=c++14 -O2 a3.cpp -o a3. If your code satisfies the most basic requirements for grading, you should see pass printed when executing a3.
(h) You are strongly encouraged to use C++14 containers std::vector and std::list with all their goods to avoid raw pointers.
(i) Your implementation must be efficient. You can expect millions of key/value pairs inserted and your class should be able to handle them in seconds.
(j) You should make no assumptions about the distribution of inserted elements, i.e. keys or values, and the order in which elements will be inserted.
(k) You should be careful with how you utilize memory. If you are too excessive in allocating memory, your code will exhaust available resources and your code will be terminated and not graded.
A3.hpp:
// File: a3.hpp
#ifndef A3_HPP
#define A3_HPP
// MAKE SURE TO UPDATE YOUR INFORMATION IN THE HEADER OF THIS FILE
// IMPLEMENT MISSING FUNCTIONALITY OF key_value_sequences IN THIS FILE
// YOU ARE NOT ALLOWED TO INCLUDE ANY OTHER HEADERS THAN
// , ,
// YOU CAN CHANGE/EDIT ANY CODE IN THIS FILE AS LONG AS SEMANTICS IS UNCHANGED
// AND MATCHES SPECIFICATION PROVIDED IN THE ASSIGNMENT TEXT
#include
#include
#include
class key_value_sequences {
public:
// YOU SHOULD USE C++ CONTAINERS TO AVOID RAW POINTERS
// IF YOU DECIDE TO USE POINTERS, MAKE SURE THAT YOU MANAGE MEMORY PROPERLY
// IMPLEMENT ME: SHOULD RETURN SIZE OF A SEQUENCE FOR GIVEN KEY
// IF NO SEQUENCE EXISTS FOR A GIVEN KEY RETURN 0
int size(int key) const;
// IMPLEMENT ME: SHOULD RETURN POINTER TO A SEQUENCE FOR GIVEN KEY
// IF NO SEQUENCE EXISTS FOR A GIVEN KEY RETURN nullptr
const int* data(int key) const;
// IMPLEMENT ME: INSERT VALUE INTO A SEQUENCE IDENTIFIED BY GIVEN KEY
void insert(int key, int value);
}; // class key_value_sequences
#endif // A3_HPP
A3.cpp:
/***
* File: a3.cpp
*/
// DO NOT EDIT THIS FILE !!!
// YOUR CODE MUST BE CONTAINED IN a3.hpp ONLY
#include
#include "a3.hpp"
int main(int argc, char* argv[]) {
key_value_sequences A;
{
key_value_sequences T;
// k will be our key
for (int k = 0; k < 10; ++k) {
// v is our value
// here we are creating 10 sequences:
// key = 0, sequence = (0)
// key = 1, sequence = (0 1)
// key = 2, sequence = (0 1 2)
// ...
// key = 9, sequence = (0 1 2 3 4 5 6 7 8 9)
for (int v = 0; v < k + 1; ++v) T.insert(k, v);
}
T = T;
key_value_sequences V = T;
A = V;
}
std::vector ref;
if (A.size(-1) != 0) {
std::cout << "fail" << std::endl;
return -1;
}
for (int k = 0; k < 10; ++k) {
if (A.size(k) != k + 1) {
std::cout << "fail";
return -1;
} else {
ref.clear();
for (int v = 0; v < k + 1; ++v) ref.push_back(v);
if (!std::equal(ref.begin(), ref.end(), A.data(k))) {
std::cout << "fail";
return -1;
}
}
}
std::cout << "pass" << std::endl;
return 0;
} // main
Explanation / Answer
here is your program : ----------------->>>>>>>>>>>
#ifndef A3_HPP
#define A3_HPP
// MAKE SURE TO UPDATE YOUR INFORMATION IN THE HEADER OF THIS FILE
// IMPLEMENT MISSING FUNCTIONALITY OF key_value_sequences IN THIS FILE
// YOU ARE NOT ALLOWED TO INCLUDE ANY OTHER HEADERS THAN
// , ,
// YOU CAN CHANGE/EDIT ANY CODE IN THIS FILE AS LONG AS SEMANTICS IS UNCHANGED
// AND MATCHES SPECIFICATION PROVIDED IN THE ASSIGNMENT TEXT
#include<iostream>
#include<vector>
using namespace std;
class key_value_sequences{
private:
vector<int> _key;
vector< vector<int> > _value;
public:
// YOU SHOULD USE C++ CONTAINERS TO AVOID RAW POINTERS
// IF YOU DECIDE TO USE POINTERS, MAKE SURE THAT YOU MANAGE MEMORY PROPERLY
// IMPLEMENT ME: SHOULD RETURN SIZE OF A SEQUENCE FOR GIVEN KEY
// IF NO SEQUENCE EXISTS FOR A GIVEN KEY RETURN 0
key_value_sequences();
int size(int key) const;
// IMPLEMENT ME: SHOULD RETURN POINTER TO A SEQUENCE FOR GIVEN KEY
// IF NO SEQUENCE EXISTS FOR A GIVEN KEY RETURN nullptr
const int* data(int key) const;
// IMPLEMENT ME: INSERT VALUE INTO A SEQUENCE IDENTIFIED BY GIVEN KEY
void insert(int key, int value);
}; // class key_value_sequences
key_value_sequences::key_value_sequences(){
}
int key_value_sequences::size(int key)const{
for(int i = 0;i<_key.size();i++){
if(_key[i] == key){
return _value[i].size();
}
}
return 0;
}
const int* key_value_sequences::data(int key)const{
for(int i = 0;i<_key.size();i++){
if(_key[i] == key){
if(_value[i].size() > 0)
return &_value[i][0];
else
return NULL;
}
}
return NULL;
}
void key_value_sequences::insert(int key,int value){
for(int i = 0;i<_key.size();i++){
if(_key[i] == key){
_value[i].push_back(value);
}
}
_key.push_back(key);
vector<int> v;
v.push_back(value);
_value.push_back(v);
}
#endif // A3_HPP
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.