Marigold

Details

  • Type: Data-Structure
  • Duration: 2 Weeks
  • Language: C++
  • Date: 2024

Description

Marigold is a contiguous allocator-aware container that is equivalent to the Standard Vector. It provides the exact same functionality of the Standard Vector up until C++23, and is fully compatible with the STL. It uses a custom memory allocator and performs slightly better than the Standard Vector, especially when it comes to storing large amount of objects. 

Container
Container
Non-Member Functions/Operators
Non-Member Functions/Operators
Custom Allocator Functions
Custom Allocator Functions
Insertion Operations
Insertion Operations
Capacity Operations
Capacity Operations
Memory Operations
Memory Operations
Emplace
Emplace

Marigold


Custom Allocator, Performance, Compatibility

Performance


The performance gains seem to be due to reallocations. As the count of elements inserted increased, the performance gap between the standard vector and Margiold increased steadily. In conclusion, Marigold is more suited for containing large amounts of elements. 


The Standard Vector performs a lot more checks and operations to guarantee allocations in certain situations which plays a factor in the difference in performance. It is also noteworthy that it contains a lot of code that is primarily for legacy support which I suspect plays a part in it as well. There are many instances in Marigold as well where a more optimized approach was discarded for the sake of keeping operations order consistent between it and the Standard Vector for the sake of user assumptions and compatibility.

Custom Allocator


Marigold uses a custom memory allocator built using AllocatorTraits and provides a simple to use API for memory allocation/deallocation and object construction/destruction. It also does book-keeping when it comes to these operations and provides the user with statistics that are helpful for debugging purposes.


The custom allocator is also compatible with the STL and can be used in different relevant operations in the STL. Propagation semantics are also defined and are carefully applied following the Standard Vector specification in the special member functions of the container.

Compatibility


While making Marigold, the specification of the Standard Vector was referenced heavily to make sure Marigold performs operations in the same order and manner as the Standard Vector to avoid compatibility issues. This allowed Marigold to be fully compatible with the STL which means that it is possible to use it with the different libraries of the STL. This includes libraries such as Algorithm which contains many use operations that can be performed on containers. Exceptions are also handled in Marigold in a similar fashion to the Standard Vector to keep it familiar for the users. Marigold contains all the special member functions of the Standard Vector, and has the same semantics for Move and Copy.