Description
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 usual, 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
1
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 or a vector of vectors. 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
1. Create directory A2 where you will place your code.
2. Download A2handout.tar from the piazza resources section.
3. Untar handout, and move a2.hpp and a2.cpp to your A2 directory.
4. Implement missing elements in a2.hpp taking into account the following:
(a) a2.hpp is the only file you are allowed to modify. a2.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 a2.cpp you
will not be graded. You are not allowed to make any changes to a2.cpp.
(b) Analyze carefully a2.hpp and a2.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 a2.cpp and the only included headers
are ,
basic compiler setting, e.g.: g++ -std=c++14 -O2 a2.cpp -o a2. If your code satisfies the
most basic requirements for grading, you should see pass printed when executing a2.
(h) You are strongly encouraged to use C++14 containers std::vector and/or 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.
2
(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.
Submission
1. Remove your binary code and other unrelated files (e.g. your test files).
2. Create a tarball with your A2 folder.
3. Follow to https://autograder.cse.buffalo.edu and submit A2.tar for grading.
4. You can make five submissions, and the last submission will be graded.
5. Any submission after the deadline will have 50% points deducted.
Grading
• 10pt: The test a2.cpp compiles with your a2.hpp, runs and has no memory leaks.
• 90pt: If you pass the initial test, there will be nine benchmark tests. You will get 10pt for each correctly
completed test (i.e. your implementation performs as expected, no memory leaks, and runs in reasonable
time limits).
• If your code is extremely inefficient, autograder will terminate your code and you will receive 0pt.
Remarks
• Make sure that all file and directory names are exactly as instructed. Otherwise the grading system will
miss your submission and you will get 0pt.
• Make sure that you start working on the assignment early! If you wait to the very last moment, you may
expect delays from autograder (overloaded by other students who like you waited with their submission).
• Focus on finding the best performance algorithm and not low-level optimizations – the autograder
architecture is unpredictable 🙂
• If you are having trouble, have a discussion on piazza! Before posting your question, ask yourself: Am
I giving enough information where someone who is not looking at my code can still help? Do not, of
course, share your code.
• Post a private note on piazza titled A2 Bounty with your first and last name for a bounty point. This
opportunity ends on July 23rd at 1:59PM. Please don’t discuss this with your peers so that they also
read to the end of the assignment early.
3
