Difference between revisions of "Container Ideas"
(→Methods) |
|||
(31 intermediate revisions by one other user not shown) | |||
Line 7: | Line 7: | ||
== Benchmarking == | == Benchmarking == | ||
Having different implementation for the same container raises the question when to use which. The answer to this is as complex as the usage of the container. Therefor I suggest an extensive benchmark suite that tests every method for with different payload sizes for different number of elements. | Having different implementation for the same container raises the question when to use which. The answer to this is as complex as the usage of the container. Therefor I suggest an extensive benchmark suite that tests every method for with different payload sizes for different number of elements. | ||
+ | |||
+ | |||
== Methods == | == Methods == | ||
Line 45: | Line 47: | ||
| rowspan="5"|Types | | rowspan="5"|Types | ||
− | !align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|RangeType ||exists || exists ||style="border-right: 2px solid;"| exists || exists || exists || exists ||style="border-right: 2px solid;"| exists || || exists || exists | + | !align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|RangeType ||exists || exists ||style="border-right: 2px solid;"| exists || exists || exists || exists ||style="border-right: 2px solid;"| exists || || exists || exists |
|- | |- | ||
− | !align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|cRangeType ||exists || exists ||style="border-right: 2px solid;"| exists || exists || exists || exists ||style="border-right: 2px solid;"| exists || || exists || exists | + | !align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|cRangeType ||exists || exists ||style="border-right: 2px solid;"| exists || exists || exists || exists ||style="border-right: 2px solid;"| exists || || exists || exists |
|- | |- | ||
− | !align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|ElementType ||T || T ||style="border-right: 2px solid;"| T || S || S || S ||style="border-right: 2px solid;"| T || T || T || T | + | !align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|ElementType ||T || T ||style="border-right: 2px solid;"| T || S || S || S ||style="border-right: 2px solid;"| T || T || T || T |
|- | |- | ||
− | !align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| | + | !align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"| ConstElementType || const(T) || const(T) ||style="border-right: 2px solid;"| const(T) || const(S) || const(S) || const(S) ||style="border-right: 2px solid;"| const(T) || const(T) || const(T) || const(T) |
|- | |- | ||
− | !align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|KeyType || | + | !align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|KeyType || || ||style="border-right: 2px solid;"| size_t || T || T || T ||style="border-right: 2px solid;"| T || || size_t || size_t |
|- | |- | ||
Line 60: | Line 62: | ||
− | | rowspan=" | + | | rowspan="18"|Modify |
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|insertFront(T) | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|insertFront(T) |
− | || void || void || | + | | align="center"| void |
+ | | align="center"| void | ||
+ | | align="center" style="border-right: 2px solid;"| void | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| | ||
+ | | align="center"| | ||
+ | | align="center" style="border-right: 2px solid;"| | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| void | ||
+ | | align="center"| | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|insertFront( | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|insertFront(K...) |
+ | | align="center"| size_t | ||
+ | | align="center"| size_t | ||
+ | | align="center" style="border-right: 2px solid;"| size_t | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| | ||
+ | | align="center"| | ||
+ | | align="center" style="border-right: 2px solid;"| | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| size_t | ||
+ | | align="center"| | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|insertBack(T) | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|insertBack(T) |
+ | | align="center"| void | ||
+ | | align="center"| void | ||
+ | | align="center" style="border-right: 2px solid;"| void | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| | ||
+ | | align="center"| | ||
+ | | align="center" style="border-right: 2px solid;"| | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| void | ||
+ | | align="center"| | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|insertBack( | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|insertBack(K...) |
+ | | align="center"| size_t | ||
+ | | align="center"| size_t | ||
+ | | align="center" style="border-right: 2px solid;"| size_t | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| | ||
+ | | align="center"| | ||
+ | | align="center" style="border-right: 2px solid;"| | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| size_t | ||
+ | | align="center"| | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|insertBefore(RangeType, T) | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|insertBefore(RangeType, T) |
+ | | align="center"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center" style="border-right: 2px solid;"| RangeType | ||
+ | | align="center" style="border-left: 2px solid;"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center" style="border-right: 2px solid;"| RangeType | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| RangeType | ||
+ | | align="center"| | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|insertBefore(RangeType, | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|insertBefore(RangeType, K...) |
+ | | align="center"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center" style="border-right: 2px solid;"| RangeType | ||
+ | | align="center" style="border-left: 2px solid;"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center" style="border-right: 2px solid;"| RangeType | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| RangeType | ||
+ | | align="center"| | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|insertAfter(RangeType, T) || | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|insertAfter(RangeType, T) |
+ | | align="center"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center" style="border-right: 2px solid;"| RangeType | ||
+ | | align="center" style="border-left: 2px solid;"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center" style="border-right: 2px solid;"| RangeType | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| RangeType | ||
+ | | align="center"| | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|insertAfter(RangeType, | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|insertAfter(RangeType, K...) |
+ | | align="center"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center" style="border-right: 2px solid;"| RangeType | ||
+ | | align="center" style="border-left: 2px solid;"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center" style="border-right: 2px solid;"| RangeType | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| RangeType | ||
+ | | align="center"| | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|insert(KeyType, T) |
+ | | align="center"| | ||
+ | | align="center"| | ||
+ | | align="center" style="border-right: 2px solid;"| RangeType | ||
+ | | align="center" style="border-left: 2px solid;"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center" style="border-right: 2px solid;"| RangeType | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| RangeType | ||
+ | | align="center"| | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|insert(KeyType, K...) |
+ | | align="center"| | ||
+ | | align="center"| | ||
+ | | align="center" style="border-right: 2px solid;"| RangeType | ||
+ | | align="center" style="border-left: 2px solid;"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center"| RangeType | ||
+ | | align="center" style="border-right: 2px solid;"| RangeType | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| RangeType | ||
+ | | align="center"| | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|removeFront(size_t = 1) |
+ | | align="center"| void | ||
+ | | align="center"| void | ||
+ | | align="center" style="border-right: 2px solid;"| void | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| | ||
+ | | align="center"| | ||
+ | | align="center" style="border-right: 2px solid;"| | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| void | ||
+ | | align="center"| void | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|removeBack(size_t = 1) |
+ | | align="center"| void | ||
+ | | align="center"| void | ||
+ | | align="center" style="border-right: 2px solid;"| void | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| | ||
+ | | align="center"| | ||
+ | | align="center" style="border-right: 2px solid;"| | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| void | ||
+ | | align="center"| void | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|remove( | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|remove(KeyType) |
+ | | align="center"| void | ||
+ | | align="center"| void | ||
+ | | align="center" style="border-right: 2px solid;"| void | ||
+ | | align="center" style="border-left: 2px solid;"| void | ||
+ | | align="center"| void | ||
+ | | align="center"| void | ||
+ | | align="center" style="border-right: 2px solid;"| void | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| void | ||
+ | | align="center"| void | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|clear() | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|remove(Range) |
+ | | align="center"| void | ||
+ | | align="center"| void | ||
+ | | align="center" style="border-right: 2px solid;"| void | ||
+ | | align="center" style="border-left: 2px solid;"| void | ||
+ | | align="center"| void | ||
+ | | align="center"| void | ||
+ | | align="center" style="border-right: 2px solid;"| void | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| void | ||
+ | | align="center"| void | ||
+ | |- | ||
+ | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|remove(ElementType) | ||
+ | | align="center"| | ||
+ | | align="center"| | ||
+ | | align="center" style="border-right: 2px solid;"| | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| | ||
+ | | align="center"| | ||
+ | | align="center" style="border-right: 2px solid;"| void | ||
+ | | align="center" style="border-left: 2px solid;"| | ||
+ | | align="center"| | ||
+ | | align="center"| | ||
+ | |- | ||
+ | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|clear() | ||
+ | | align="center"| void | ||
+ | | align="center"| void | ||
+ | | align="center" style="border-right: 2px solid;"| void | ||
+ | | align="center" style="border-left: 2px solid;"| void | ||
+ | | align="center"| void | ||
+ | | align="center"| void | ||
+ | | align="center" style="border-right: 2px solid;"| void | ||
+ | | align="center" style="border-left: 2px solid;"| void | ||
+ | | align="center"| void | ||
+ | | align="center"| void | ||
+ | |- | ||
+ | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|push(ElementType) | ||
+ | |- | ||
+ | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|pop() | ||
|- | |- | ||
− | |||
<!-- Access methods --> | <!-- Access methods --> | ||
− | | rowspan=" | + | | rowspan="8"|Access |
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|front() | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|top() |
+ | |- | ||
+ | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|front() | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|back() | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|back() |
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|opIndex(const KeyType) | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|opIndex(const KeyType) |
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|find(const KeyType) | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|find(const KeyType) |
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|opSlice(const KeyType) | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|opSlice(const KeyType) |
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|opSlice(const KeyType, const KeyType) | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|opSlice(const KeyType, const KeyType) |
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| in || || || style="border-right: 2px solid;"| | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"| in || || || style="border-right: 2px solid;"| |
|bgcolor="Iceberg" align="center"|bool | |bgcolor="Iceberg" align="center"|bool | ||
|bgcolor="Iceberg" align="center"|bool | |bgcolor="Iceberg" align="center"|bool | ||
Line 121: | Line 291: | ||
| rowspan="2"| Properties | | rowspan="2"| Properties | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| length | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"| length |
|bgcolor="Iceberg" align="center"|size_t ||bgcolor="Iceberg" align="center"|size_t ||bgcolor="Iceberg" align="center" style="border-right: 2px solid;"|size_t | |bgcolor="Iceberg" align="center"|size_t ||bgcolor="Iceberg" align="center"|size_t ||bgcolor="Iceberg" align="center" style="border-right: 2px solid;"|size_t | ||
|bgcolor="Iceberg" align="center"|size_t||bgcolor="Iceberg" align="center"|size_t||bgcolor="Iceberg" align="center" |size_t | |bgcolor="Iceberg" align="center"|size_t||bgcolor="Iceberg" align="center"|size_t||bgcolor="Iceberg" align="center" |size_t | ||
Line 127: | Line 297: | ||
|bgcolor="Iceberg" align="center"|size_t | |bgcolor="Iceberg" align="center"|size_t | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| empty | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"| empty |
|bgcolor="Iceberg" align="center"|bool ||bgcolor="Iceberg" align="center"|bool ||bgcolor="Iceberg" align="center" style="border-right: 2px solid;"|bool | |bgcolor="Iceberg" align="center"|bool ||bgcolor="Iceberg" align="center"|bool ||bgcolor="Iceberg" align="center" style="border-right: 2px solid;"|bool | ||
|bgcolor="Iceberg" align="center"|bool||bgcolor="Iceberg" align="center"|bool||bgcolor="Iceberg" align="center"|bool | |bgcolor="Iceberg" align="center"|bool||bgcolor="Iceberg" align="center"|bool||bgcolor="Iceberg" align="center"|bool | ||
Line 139: | Line 309: | ||
| rowspan="6"| Storage | | rowspan="6"| Storage | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| capacity | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"| capacity |
|bgcolor="Iceberg" align="center"|size_t ||bgcolor="Iceberg" align="center"|size_t ||bgcolor="Iceberg" align="center" style="border-right: 2px solid;"|size_t | |bgcolor="Iceberg" align="center"|size_t ||bgcolor="Iceberg" align="center"|size_t ||bgcolor="Iceberg" align="center" style="border-right: 2px solid;"|size_t | ||
|bgcolor="Iceberg" align="center"|size_t||bgcolor="Iceberg" align="center"|size_t||bgcolor="Iceberg" align="center" |size_t | |bgcolor="Iceberg" align="center"|size_t||bgcolor="Iceberg" align="center"|size_t||bgcolor="Iceberg" align="center" |size_t | ||
Line 145: | Line 315: | ||
|bgcolor="Iceberg" align="center"|size_t | |bgcolor="Iceberg" align="center"|size_t | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| minimize | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"| minimize |
| align="center"|exists || align="center"|exists || align="center" style="border-right: 2px solid;"|exists | | align="center"|exists || align="center"|exists || align="center" style="border-right: 2px solid;"|exists | ||
| align="center"|exists|| align="center"|exists|| align="center" |exists | | align="center"|exists|| align="center"|exists|| align="center" |exists | ||
Line 152: | Line 322: | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| reserve | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"| reserve |
| align="center"|size_t || align="center"|size_t || align="center" style="border-right: 2px solid;"|size_t | | align="center"|size_t || align="center"|size_t || align="center" style="border-right: 2px solid;"|size_t | ||
| align="center"|size_t|| align="center"|size_t|| align="center" |size_t | | align="center"|size_t|| align="center"|size_t|| align="center" |size_t | ||
Line 158: | Line 328: | ||
| align="center"|size_t | | align="center"|size_t | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| maxSize | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"| maxSize |
|bgcolor="Orange" align="center"|size_t ||bgcolor="Orange" align="center"|size_t ||bgcolor="Orange" align="center" style="border-right: 2px solid;"|size_t | |bgcolor="Orange" align="center"|size_t ||bgcolor="Orange" align="center"|size_t ||bgcolor="Orange" align="center" style="border-right: 2px solid;"|size_t | ||
|bgcolor="Orange" align="center"|size_t||bgcolor="Orange" align="center"|size_t||bgcolor="Orange" align="center" |size_t | |bgcolor="Orange" align="center"|size_t||bgcolor="Orange" align="center"|size_t||bgcolor="Orange" align="center" |size_t | ||
Line 164: | Line 334: | ||
|bgcolor="Orange" align="center"|size_t | |bgcolor="Orange" align="center"|size_t | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| growable | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"| growable |
|bgcolor="Orange" align="center"|bool ||bgcolor="Orange" align="center"|bool ||bgcolor="Orange" align="center" style="border-right: 2px solid;"|bool | |bgcolor="Orange" align="center"|bool ||bgcolor="Orange" align="center"|bool ||bgcolor="Orange" align="center" style="border-right: 2px solid;"|bool | ||
|bgcolor="Orange" align="center"|bool||bgcolor="Orange" align="center"|bool||bgcolor="Orange" align="center"|bool | |bgcolor="Orange" align="center"|bool||bgcolor="Orange" align="center"|bool||bgcolor="Orange" align="center"|bool | ||
Line 170: | Line 340: | ||
|bgcolor="Orange" align="center"|bool | |bgcolor="Orange" align="center"|bool | ||
|- | |- | ||
− | ! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| packed | + | ! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"| packed |
|bgcolor="Orange" align="center"|bool ||bgcolor="Orange" align="center"|bool ||bgcolor="Orange" align="center" style="border-right: 2px solid;"|bool | |bgcolor="Orange" align="center"|bool ||bgcolor="Orange" align="center"|bool ||bgcolor="Orange" align="center" style="border-right: 2px solid;"|bool | ||
|bgcolor="Orange" align="center"|bool||bgcolor="Orange" align="center"|bool||bgcolor="Orange" align="center"|bool | |bgcolor="Orange" align="center"|bool||bgcolor="Orange" align="center"|bool||bgcolor="Orange" align="center"|bool | ||
Line 177: | Line 347: | ||
|} | |} | ||
+ | |||
+ | [[Category:Proposals]] |
Latest revision as of 12:02, 21 September 2018
Variable Implementation
As the discussion on the mailing-list (Deque impl.) has shown the ideas about how the internals of the container should work differ. Not only for the general case but also for specific cases like small (<64) vectors. Another application for this are the mapping container. For some tasks a hashtable might be best suited for other a binary-tree. Sometimes even, the user might supply a even more used implementation for the given task.
Therefor I suggest a design that lets the user switch out the underlying implementation. To supply the implementation I see two possibilities. The first is to supply it as a template. The second is to supply it as an argument. The first possibility has the disadvantage that different underlying implementation introduce new types. On the plus side the compile can remove the delegation as it is static. The second possibility does not introduce a new type, this is at the cost of a vtable lookup for every operation. It also forces the range types to work for all implementations. This might lead to making ranges abstract class or interfaces. Therefor I prefer the template approach.
Benchmarking
Having different implementation for the same container raises the question when to use which. The answer to this is as complex as the usage of the container. Therefor I suggest an extensive benchmark suite that tests every method for with different payload sizes for different number of elements.
Methods
notconst | const | immutable | notconst or const |
exists | means that name or type exists |
Sequence | Associative | Special Access | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Container | Double Linked List(T) | Single Linked List(T) | Random Access(T) | Map(T,S) | Multimap(T,S) | MapSet(T,S) | Set(T) | Stack(T) | Queue(T) | PriorityQueue(T) | |
Types | RangeType | exists | exists | exists | exists | exists | exists | exists | exists | exists | |
cRangeType | exists | exists | exists | exists | exists | exists | exists | exists | exists | ||
ElementType | T | T | T | S | S | S | T | T | T | T | |
ConstElementType | const(T) | const(T) | const(T) | const(S) | const(S) | const(S) | const(T) | const(T) | const(T) | const(T) | |
KeyType | size_t | T | T | T | T | size_t | size_t | ||||
Modify | insertFront(T) | void | void | void | void | ||||||
insertFront(K...) | size_t | size_t | size_t | size_t | |||||||
insertBack(T) | void | void | void | void | |||||||
insertBack(K...) | size_t | size_t | size_t | size_t | |||||||
insertBefore(RangeType, T) | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | |||
insertBefore(RangeType, K...) | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | |||
insertAfter(RangeType, T) | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | |||
insertAfter(RangeType, K...) | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | |||
insert(KeyType, T) | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | |||||
insert(KeyType, K...) | RangeType | RangeType | RangeType | RangeType | RangeType | RangeType | |||||
removeFront(size_t = 1) | void | void | void | void | void | ||||||
removeBack(size_t = 1) | void | void | void | void | void | ||||||
remove(KeyType) | void | void | void | void | void | void | void | void | void | ||
remove(Range) | void | void | void | void | void | void | void | void | void | ||
remove(ElementType) | void | ||||||||||
clear() | void | void | void | void | void | void | void | void | void | void | |
push(ElementType) | |||||||||||
pop() | |||||||||||
Access | top() | ||||||||||
front() | |||||||||||
back() | |||||||||||
opIndex(const KeyType) | |||||||||||
find(const KeyType) | |||||||||||
opSlice(const KeyType) | |||||||||||
opSlice(const KeyType, const KeyType) | |||||||||||
in | bool | bool | bool | bool | |||||||
Properties | length | size_t | size_t | size_t | size_t | size_t | size_t | size_t | size_t | size_t | size_t |
empty | bool | bool | bool | bool | bool | bool | bool | bool | bool | bool | |
Storage | capacity | size_t | size_t | size_t | size_t | size_t | size_t | size_t | size_t | size_t | size_t |
minimize | exists | exists | exists | exists | exists | exists | exists | exists | exists | exists | |
reserve | size_t | size_t | size_t | size_t | size_t | size_t | size_t | size_t | size_t | size_t | |
maxSize | size_t | size_t | size_t | size_t | size_t | size_t | size_t | size_t | size_t | size_t | |
growable | bool | bool | bool | bool | bool | bool | bool | bool | bool | bool | |
packed | bool | bool | bool | bool | bool | bool | bool | bool | bool | bool |