Assignment#

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.

Requirements:

• Make sure your code is portable to all major C compilers (gcc, msvc, clang) and does not produce warnings — use -Wall with 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. astyle or clang-format. Check your code with automatic linter for common errors, e.g. cppcheck.
• 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 valgrind to 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 empty, push_back, pop_back, back, front, swap, size, clear, assignable version of operator[] that behave as usual with STL containers. Note that you will have to implement 2 overloaded variants of operator[] and several other accessor functions — one for accessing constant array elements (that returns a const-reference) and the second for mutable contents.
  • swap that swaps contents of 2 Arrays in O (1)
  • append that adds content from another array to the end, i.e. a.append(b) causes a to contain contents from original a followed by b.
  • reserve that 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 reserve preallocation.
  • resize that changes the number of elements stored in the array. Note the difference between reserve and 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 emplace_back.
• begin, 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 free(ptr) or 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 0 to size()-1) have been initialized and will be deinitialized upon removal.