STL Allocator InterfaceC程序辅导讲解、讲解C程序题目、辅导C试题 辅导留学生Prolog|讲解数据库SQL
- 首页 >> 其他 STL Allocator Interface
An allocator is used by standard library containers as a template parameter :
template < class T, class Alloc = allocator > class vector;
template < class T, class Alloc = allocator > class list;
What does an allocator class have? Typically, it possesses:
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 void destroy(_Uty *_Ptr)
template
void construct(_Objty *_Ptr, _Types&&... _Args)
The above interface is just shown for illustration, please refer to std::allocator for the latest specification.
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.
Requirements
? Two people as a group to finish this project (don't forget to write down the group member names, anyone of the two can submit the final package on PTA).
? 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.
How to test your allocator
Basically, you should:
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.
3. Release all the vectors.
4. Feel free to extend the following code skeleton for your own tests:
5. #include
6. #include
7. #include
8.
9. // include header of your allocator here
10. template
11. using MyAllocator = std::allocator; // replace the std::allocator with your allocator
12. using Point2D = std::pair;
13.
14. const int TestSize = 10000;
15. const int PickSize = 1000;
16.
17. int main()
18. {
19. std::random_device rd;
20. std::mt19937 gen(rd());
21. std::uniform_int_distribution<> dis(1, TestSize);
22.
23. // vector creation
24. using IntVec = std::vector>;
25. std::vector> vecints(TestSize);
26. for (int i = 0; i < TestSize; i++)
27. vecints[i].resize(dis(gen));
28.
29. using PointVec = std::vector>;
30. std::vector> vecpts(TestSize);
31. for (int i = 0; i < TestSize; i++)
32. vecpts[i].resize(dis(gen));
33.
34. // vector resize
35. for (int i = 0; i < PickSize; i++)
36. {
37. int idx = dis(gen) - 1;
38. int size = dis(gen);
39. vecints[idx].resize(size);
40. vecpts[idx].resize(size);
41. }
42.
43. // vector element assignment
44. {
45. int val = 10;
46. int idx1 = dis(gen) - 1;
47. int idx2 = vecints[idx1].size() / 2;
48. vecints[idx1][idx2] = val;
49. if (vecints[idx1][idx2] == val)
50. std::cout << "correct assignment in vecints: " << idx1 << std::endl;
51. else
52. std::cout << "incorrect assignment in vecints: " << idx1 << std::endl;
53. }
54. {
55. Point2D val(11, 15);
56. int idx1 = dis(gen) - 1;
57. int idx2 = vecpts[idx1].size() / 2;
58. vecpts[idx1][idx2] = val;
59. if (vecpts[idx1][idx2] == val)
60. std::cout << "correct assignment in vecpts: " << idx1 << std::endl;
61. else
62. std::cout << "incorrect assignment in vecpts: " << idx1 << std::endl;
63. }
64.
65. return 0;
66. }
67. Evaluation standard
1. c++ code quality (clean, compact and reasonable)
2. comments quality
3. running performance of the allocator
Files to submit
Please prepare a .zip package including the following items：
1. the source code (including the testing code)
2. makefile (for Mac or Linux users) or .exes (for Windows users, with necessary .dlls if you use MinGW) or CMakeLists.txt
An allocator is used by standard library containers as a template parameter :
template < class T, class Alloc = allocator
template < class T, class Alloc = allocator
What does an allocator class have? Typically, it possesses:
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
template
void construct(_Objty *_Ptr, _Types&&... _Args)
The above interface is just shown for illustration, please refer to std::allocator for the latest specification.
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.
Requirements
? Two people as a group to finish this project (don't forget to write down the group member names, anyone of the two can submit the final package on PTA).
? 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.
How to test your allocator
Basically, you should:
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.
3. Release all the vectors.
4. Feel free to extend the following code skeleton for your own tests:
5. #include
6. #include
7. #include
8.
9. // include header of your allocator here
10. template
11. using MyAllocator = std::allocator
12. using Point2D = std::pair
13.
14. const int TestSize = 10000;
15. const int PickSize = 1000;
16.
17. int main()
18. {
19. std::random_device rd;
20. std::mt19937 gen(rd());
21. std::uniform_int_distribution<> dis(1, TestSize);
22.
23. // vector creation
24. using IntVec = std::vector
25. std::vector
26. for (int i = 0; i < TestSize; i++)
27. vecints[i].resize(dis(gen));
28.
29. using PointVec = std::vector
30. std::vector
31. for (int i = 0; i < TestSize; i++)
32. vecpts[i].resize(dis(gen));
33.
34. // vector resize
35. for (int i = 0; i < PickSize; i++)
36. {
37. int idx = dis(gen) - 1;
38. int size = dis(gen);
39. vecints[idx].resize(size);
40. vecpts[idx].resize(size);
41. }
42.
43. // vector element assignment
44. {
45. int val = 10;
46. int idx1 = dis(gen) - 1;
47. int idx2 = vecints[idx1].size() / 2;
48. vecints[idx1][idx2] = val;
49. if (vecints[idx1][idx2] == val)
50. std::cout << "correct assignment in vecints: " << idx1 << std::endl;
51. else
52. std::cout << "incorrect assignment in vecints: " << idx1 << std::endl;
53. }
54. {
55. Point2D val(11, 15);
56. int idx1 = dis(gen) - 1;
57. int idx2 = vecpts[idx1].size() / 2;
58. vecpts[idx1][idx2] = val;
59. if (vecpts[idx1][idx2] == val)
60. std::cout << "correct assignment in vecpts: " << idx1 << std::endl;
61. else
62. std::cout << "incorrect assignment in vecpts: " << idx1 << std::endl;
63. }
64.
65. return 0;
66. }
67. Evaluation standard
1. c++ code quality (clean, compact and reasonable)
2. comments quality
3. running performance of the allocator
Files to submit
Please prepare a .zip package including the following items：
1. the source code (including the testing code)
2. makefile (for Mac or Linux users) or .exes (for Windows users, with necessary .dlls if you use MinGW) or CMakeLists.txt