Optional Problem 2 - STL Allocator + Memory Pool

OOP Project VIII, 2023 Summer CourseNana.COM

Background

STL Allocator Interface

An allocator is used by standard library containers as a template parameter : CourseNana.COM

    template < class T, class Alloc = allocator<T> > class vector;
    template < class T, class Alloc = allocator<T> > class list;

What does an allocator class have? Typically, it possesses: CourseNana.COM

typedef void _Not_user_specialized;
typedef _Ty value_type;
typedef value_type *pointer;
typedef const value_type *const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef true_type propagate_on_container_move_assignment;
typedef true_type is_always_equal;
pointer address(reference _Val) const _NOEXCEPT
const_pointer address(const_reference _Val) const _NOEXCEPT
void deallocate(pointer _Ptr, size_type _Count)
_DECLSPEC_ALLOCATOR pointer allocate(size_type _Count)
template<class _Uty> void destroy(_Uty *_Ptr)
template<class _Objty, class _Types>
void construct(_Objty *_Ptr, _Types&&... _Args)

The above interface is just shown for illustration, please refer to std::allocator for the latest specification. CourseNana.COM

Memory Pool

STL provides you a default std::allocator, but you can implement your own to replace it. For example, you can design a memory pool to speed up the dynamic allocation of a large number of small blocks (e.g., 8 bytes, 16 bytes, ...), and to reduce memory fragmentation. Figure 1: Mem pool using block based allocation strategy. CourseNana.COM

Project Requirements

Implement your own memory allocator for STL vector. The allocator should optimize the memory allocation speed using memory pool. The allocator should support arbitrary memory size allocation request. CourseNana.COM

How to Test Your Allocator

Basically, you should: CourseNana.COM

1. Create more than ten thousand vectors with different number of elements. 2. Pick up 1000 random vectors and resize the vectors with random sizes.

2. Release all the vectors. Feel free to extend the following code skeleton for your own tests (good test is a bonus): CourseNana.COM

   #include <iostream>
   #include <random>
   #include <vector>
   // include header of your allocator here
   template<class T>
   using MyAllocator = std::allocator<T>; // replace the std::allocator with your
   allocator
   using Point2D = std::pair<int, int>;
   const int TestSize = 10000;
   const int PickSize = 1000;
   int main() {
     std::random_device rd;
     std::mt19937 gen(rd());
     std::uniform_int_distribution<> dis(1, TestSize);
     // vector creation
     using IntVec = std::vector<int, MyAllocator<int>>;
     std::vector<IntVec, MyAllocator<IntVec>> vecints(TestSize);
     for (int i = 0; i < TestSize; i++)
       vecints[i].resize(dis(gen));
     using PointVec = std::vector<Point2D, MyAllocator<Point2D>>;
     std::vector<PointVec, MyAllocator<PointVec>> vecpts(TestSize);
     for (int i = 0; i < TestSize; i++)
       vecpts[i].resize(dis(gen));
     // vector resize
     for (int i = 0; i < PickSize; i++)
     {
       int idx = dis(gen) - 1;
       int size = dis(gen);
       vecints[idx].resize(size);
       vecpts[idx].resize(size);
   }
     // vector element assignment
   {
   
    int val = 10;
   int idx1 = dis(gen) - 1;
   int idx2 = vecints[idx1].size() / 2;
   vecints[idx1][idx2] = val;
   if (vecints[idx1][idx2] == val)
   std::cout << "correct assignment in vecints: " << idx1 << std::endl;
   else
   std::cout << "incorrect assignment in vecints: " << idx1 << std::endl;
   }
   {
   Point2D val(11, 15);
   int idx1 = dis(gen) - 1;
   int idx2 = vecpts[idx1].size() / 2;
   vecpts[idx1][idx2] = val;
   if (vecpts[idx1][idx2] == val)
   std::cout << "correct assignment in vecpts: " << idx1 << std::endl;
   else
   std::cout << "incorrect assignment in vecpts: " << idx1 << std::endl;
   }
   return 0; }

Requirements and Submission Guidelines

Evaluation Standard

1. C++ code quality (clean, compact and reasonable)
2. comments quality

3. correctness and running performance of the allocator CourseNana.COM

   Required Files

   A zip packages and a report in pdf are required. You should submit the following files separatedly on Learning in ZJU. P8_2_321010xxxx_xxx.pdf P8_2_321010xxxx_xxx.zip Note that this is the 2nd problem to choose of Project 8, so don't forget the prefix is P82. Please prepare a zip package including the following items: CourseNana.COM

   1. the source code
4. the test code or test data
5. a shell/batch script that compiles your program explicitly showing the version of C++ you are using For example: g++ -std=c++11 main.cpp -o ./test ./test out.txt Note that this is only an example. You may customize the script and way you run the test if you like.
6. build configuration if necessary, including makefile, visual studio project, or CMakeLists.txt
7. areadme.txtifnecessary

Please name the zip file as Px_p_id_name where x is the project index (8 for this project), p is the id of problem (2 for this problem), id is your student id and name is your name in Pinyin. e.g., P8_2_3210100000_ZhangSan.zip A report in pdf format. The report may include the following contents: CourseNana.COM

1. A description of the requirements of this project;
2. A description of the idea you solve the problem and your thought process in writing the source code; 3. A description of how your program works;
3. Explanation of important parts of your source code;
4. Test results;
5. Discussions. You may customize the content of your report if you like. Please submit the report pdf file and the zip file separately. Do not put the report into the zip package. Please name the pdf file the same way as the first zip file.