The results are available individually — to see the results, comments and final score, please append your 8-digit UK student number (a.k.a. SIS ID, a.k.a. UKČO) to this URL in your browser’s address bar, together with .html extension.
For example, my SIS ID is 27221206, my solution is therefore available at: ..../27221206.html
Score distribution among students:
1x 0pts 1x 2pts 1x 3pts 3x 4pts 2x 5pts 1x 6pts 1x 7pts 3x 8pts 1x 10pts 1x 11pts 3x 13pts 3x 14pts 19x 15pts
Scores will be filled to SIS after some grace period for feedback and possible corrections (~1 week). Mail me in case of any questions.
Deadline: November 23rd.
We have learned to use the constructors and destructors so that a class can behave like a normal variable, but safely keep an associated resource (e.g. allocated memory, open file, or so.)
Apply this to implement a variable-length array type, called
Array. Your implementation should be a work-alike of the
std::vector, only reasonably simpler.
- Make sure your code is portable to all major C++ compilers (gcc, msvc, clang) and does not produce warnings — use
-Wallwith gcc and clang. (Notice: clang installation in the computer lab is somehow slightly broken; generally if your code passes through gcc -Wall without warnings, you can assume you won’t have any problems with clang.)
- Do not use STL, your solution should be based on “raw” programming with low-level memory primitives.
- Produce a reasonably short, neat, well-formatted and commented code. Use an automatic code formatter, i.e.
clang-format. Check your code with automatic linter for common errors, e.g.
- Code should never crash, UNLESS subjected to usage that is documented as an invalid action that causes undefined behavior (i.e. out-of-bounds access by library user)
- Code should not leak memory. You can use
valgrindto check for memory leaks automatically.
- The implementation should be as efficient as possible — Do not allocate memory unnecessarily (esp. not on construction of empty container), use correct
const-antness, references, etc.
- Required functionality:
- Support for any contained type, using a template.
- Safe default constructor, copy constructor, copy assignment operator and destructor.
- implementations of
clear, assignable version of
operatorthat behave as usual with STL containers. Note that you will have to implement 2 overloaded variants of
operatorand several other accessor functions — one for accessing constant array elements (that returns a const-reference) and the second for mutable contents.
swapthat swaps contents of 2 Arrays in O(1)
appendthat adds content from another array to the end, i.e.
ato contain contents from original
reservethat pre-allocates memory for contents, so that successive pushing to the back of the array doesn’t need to reallocate the array frequently. Note that any other action than adding elements (eg. copying the array, popping elements, downsizing) is free to remove the effect of
resizethat changes the number of elements stored in the array. Note the difference between
resize— resize should construct the objects, reseve should never construct anything; just prepare the memory.
Remember that you need to call constructors and destructors of the objects contained in your array, so that they are correctly initialized and destroyed after use!
You can implement following bonus features to patch up other inefficiencies in the code:
- Move semantics, i.e. the “rule of five”, optionally with
end, and associated iterators, to make the container compatible with the usual range-based for loops.
Place your resulting solution to file
cpparray.hpp and upload it to the correct field in the study group interface in SIS.
As a test, you can use this file which should work correctly with your implementation of
Array. (Note that there’s a possibility to use
std::vector instead of Array for the test — this can serve as a guideline if you are not sure about exact functionality of something.) The default test is small and may not crash even if your implementation contains errors; try increasing S to a larger value (say, 100) to increase the failure probability.
NOTES: It is important to understand the semantic difference between “raw allocated memory” (which is the result of
reserve() operation) and “allocated memory with constructors ran on it” (which is the result of
resize()) — if the user only reserves the space for objects, none should be actually initialized (imagine the objects hold some large resource or lock something; the user would not like to consume these resources before he places the actual objects into the container). You can allocate raw memory using either
malloc(size) or using
operator new(size). Memory can be deallocated without calling a destructor using either
operator delete(ptr). The constructors can be ran manually on raw memory using the “placement new” syntax —
new(ptr) Type(constructor_args); destructors are ran using the “pointer destruct” syntax —
ptr->~Type(). Compare with
ptr=new Type() and
delete ptr, which combine both memory allocation and object initialization/destruction. This difference is something that is vital for understanding the RAII model of C++ and drawing a bold line between memory allocation (which is one resource) and object lifetime (which is a completely different resource that only requires the space provided by the previous one). Anyway, this gets philosophical very easily; for that reason you will not be penalized if your implementation does not do this completely right. The only thing you need to ensure is that all objects in the valid array size (indexes
size()-1) have been initialized and will be deinitialized upon removal.