STL Benchmark vs. ADT & DS C++ API

In order to reliably test API against STL and make everything transparent, another GIT project was created for that purpose alone. To install that project and run tests yourselves, go to its homepage and follow steps described there.

In benchmark results below, following methodology was used:

different tests were ran for long and char* data types to show how different results can be
for maximum reliability, each benchmark for each data structure implementation was ran in ten rows.
results were done by compiling average results of those ten rows above
each line in below results is an API class followed by its STL peer
tests were ran an Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz CPU & 8GB RAM running on Ubuntu 18

Despite different programming behind, memory usage is dictated by data structure and remains the same between STL and CDS, so the only thing that varies is speed.

Lists

Test case:

checking duration of a million rows insertion on list's tail
checking duration of iterating all list from head to tail
checking duration of getting all list element values by offset from head to tail
removing all list elements based on offset from tail to head (for dynamic arrays) and head to tail (for [doubly-]linked lists)

Benchmark results for long data type:

Implementation	Insertion (ms)	Iteration (ms)	Selection (ms)	Deletion (ms)
ArrayList¹	4	3	1	2
std::vector¹	3	0	0	1
LinkedList	22	4	3	7
std::forward_list²	20	3		6
DoublyLinkedList	21	4	3	8
std::list²	21	2		6

Benchmark results for char* data type:

Implementation	Insertion (ms)	Iteration (ms)	Selection (ms)	Deletion (ms)
ArrayList¹	3	3	1	1
std::vector¹	3	0	0	1
LinkedList	21	3	3	7
std::forward_list²	19	3		6
DoublyLinkedList	21	4	3	8
std::list²	20	3		6

Several notes:
1. tests for dynamic array implementations use reserved size of one million plus one. The reason is that each implementation has its own growth point (A grows at point V, while B grows at point Z>V: if we stop insertion between V and Z, A will appear slower because it has done one more reallocation)
2. std::list & std::forward_list do not support getting element by offset

Conclusion: STL wins by a 1-2ms margin, except on iterating Dynamic Array, where ArrayList has to encapsulate whereas std::vector can use pointer arithmetics and thus be faster by 3ms.

Maps

Test case:

checking duration of a million rows insertion
checking duration of iterating all map
checking duration of getting all map entry values by key
removing all map entries based on key

Benchmark results for long key & value types:

Implementation	Insertion (ms)	Iteration (ms)	Selection (ms)	Deletion (ms)
TreeMap	184	17	103	89
std::map	193	19	117	92
HashMap¹ ²	44	6	9	17
std::unordered_map¹ ²	55	2	7	17

Benchmark results for char* key & value types:

Implementation	Insertion (ms)	Iteration (ms)	Selection (ms)	Deletion (ms)
TreeMap	190	19	129	104
std::map	198	14	125	143
HashMap¹ ²	55	9	20	26
std::unordered_map¹ ²	117	19	28	48

Several notes:
1. tests for hash table implementations use reserved size of one million plus one. The reason is that each implementation has its own growth point (A grows at point V, while B grows at point Z>V: if we stop insertion between V and Z, A will appear slower because it has done one more reallocation)
2. same hashing function per type was used for both std::unordered_map and HashMap to make results comparable. Default hash function for char* used by std::unordered_map is much slower.

Conclusion: API wins on all counts (5% advantage on TreeMap vs. std::map, 25%-100% advantage on HashMap vs. std::unordered_map).

Sets

Test case:

checking duration of a million rows insertion
checking duration of iterating all set
removing all set entries based on value

Benchmark results for long data type:

Implementation	Insertion (ms)	Iteration (ms)	Deletion (ms)
TreeSet	178	19	77
std::set	160	16	78
HashSet¹ ²	28	6	16
std::unordered_set¹ ²	37	3	13

Benchmark results for char* data type:

Implementation	Insertion (ms)	Iteration (ms)	Deletion (ms)
TreeSet	185	14	109
std::set	187	12	139
HashSet¹ ²	34	8	21
std::unordered_set¹ ²	45	7	31

Several notes:
1. tests for hash table implementations use reserved size of one million plus one. The reason is that each implementation has its own growth point (A grows at point V, while B grows at point Z>V: if we stop insertion between V and Z, A will appear slower because it has done one more reallocation)
2. same hashing function per type was used for both std::unordered_set and HashSet to make results comparable. Default hash function for char* used by std::unordered_set is much slower.

Conclusion: on Red Black Tree implementations (TreeSet and std::set) results are a draw, wheres in Hash Table implementations (HashSet and std::unordered_set) API is a very strong winner (32% advantage on HashSet vs. std::unordered_set).

Conclusions

Test results demonstrate that by ergonomics and speed, API outperforms STL. Even in areas where it is in slight disadvantage, it brings forward an orderly structure that is easy and consistent to work with:

in List implementations, STL is slightly faster by some 2-3ms simply by virtue of not having to encapsulate information. If those ms count, you never plan to switch data structures used and you like memorizing unintuitive method names then STL is a winner.
in Map and Set implementations, classes that rely on Red Black Tree show roughly equivalent results (TreeSet vs. std::set or TreeMap vs. std::map) between API and STL.
in Map and Set implementations, classes that rely on Hash Table show that API is significantly more efficient than STL (HashSet vs. std::unordered_set or HashMap vs. std::unordered_map) with an overall 25% speed advantage.