Difference between revisions of "Container Ideas"

From D Wiki
Jump to: navigation, search
(Methods)
 
(53 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 12: Line 14:
 
{|  
 
{|  
 
| notconst ||bgcolor="Iceberg" | const || bgcolor="Orange" | immutable
 
| notconst ||bgcolor="Iceberg" | const || bgcolor="Orange" | immutable
| bgcolor="Gold" | const or immutable
+
| bgcolor="aqua" | notconst or const
 
|-
 
|-
 
| exists || colspan="3" | means that name or type exists
 
| exists || colspan="3" | means that name or type exists
 
|}
 
|}
  
 +
<!-- Top matter Categories -->
 
{| class="wikitable"
 
{| class="wikitable"
 
| colspan="2" style="border-left: 2px solid;" style="border-right: 2px solid;"|
 
| colspan="2" style="border-left: 2px solid;" style="border-right: 2px solid;"|
Line 23: Line 26:
 
! colspan="3" style="border-left: 2px solid;"|Special Access
 
! colspan="3" style="border-left: 2px solid;"|Special Access
 
|-
 
|-
 +
 +
<!-- Name of tables -->
 +
 
! colspan="2" style="border-left: 2px solid;" style="border-right: 2px solid;"|Container
 
! colspan="2" style="border-left: 2px solid;" style="border-right: 2px solid;"|Container
 
!Double Linked List(T)
 
!Double Linked List(T)
Line 31: Line 37:
 
!Multimap(T,S)
 
!Multimap(T,S)
 
!MapSet(T,S)
 
!MapSet(T,S)
!Set(T)
+
!style="border-right: 2px solid;"|Set(T)
 
!Stack(T)
 
!Stack(T)
 
!Queue(T)
 
!Queue(T)
 
!PriorityQueue(T)
 
!PriorityQueue(T)
 +
|-
  
 +
<!-- Presented 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;"|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
 
|-
 
|-
| rowspan="4"|Types
+
!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;"|RangeType ||exists || exists ||style="border-right: 2px solid;"| exists || exists || exists || exists || 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 || exists || || exists || exists
+
!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
 
|-
 
|-
!align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|ElementType ||T || T ||style="border-right: 2px solid;"| T || S || S || S || T || T || T || T
+
 
 +
 
 +
<!-- Modify methods -->
 +
 
 +
 
 +
| rowspan="18"|Modify
 +
! align="left" style="border-left: 2px solid;" style="border-right: 2px solid;"|insertFront(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;"|KeyType || size_t || size_t ||style="border-right: 2px solid;"| size_t || T || T || T || T || || size_t || size_t
+
! 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"|  
 
|-
 
|-
| rowspan="14"|Modify
+
! 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;"|insertFront(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;"|insertFront(T...)
+
! 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;"|insertBack(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;"|insertBack(T...)
+
! 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;"|insertBefore(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;"|insertBefore(RangeType, T...)
+
! 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;"|insertAfter(RangeType, T) || T
+
! 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;"|insertAfter(RangeType, T...)
+
! 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;"|removeFront(size_t = 1)
+
! 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;"|removeBack(size_t = 1)
+
! 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(KeyType)
+
! 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;"|remove(Range)
+
! 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="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="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
 
|-
 
|-
| rowspan="7"|Access
+
! 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;"|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;"|pop()
 
|-
 
|-
! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"|opIndex(KeyType)
+
 
 +
<!-- Access methods -->
 +
 
 +
 
 +
| rowspan="8"|Access
 +
! 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;"|find(KeyType)
+
! 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;"|opSlice(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;"|opSlice(KeyType, 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;"| in || || || style="border-right: 2px solid;"|
+
! 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;"| 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 95: Line 285:
 
| || ||
 
| || ||
 
|-
 
|-
 +
 +
 +
<!-- Properties -->
 +
 +
 
| 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 102: 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"|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  
 
|bgcolor="Iceberg" align="center"|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
 
|-
 
|-
| rowspan="6"| Capacity
+
 
! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| capacity
+
 
 +
<!-- Storage methods -->
 +
 
 +
 
 +
| rowspan="6"| Storage
 +
! 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" |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
 
|-
 
|-
! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| compact
+
! 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" |exists
 +
| align="center" style="border-right: 2px solid;"|exists|| align="center"|exists|| align="center"|exists
 +
| align="center"|exists
 +
 
 
|-
 
|-
! 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" |size_t
 +
| align="center" style="border-right: 2px solid;"|size_t|| align="center"|size_t|| align="center"|size_t
 +
| align="center"|size_t
 
|-
 
|-
! align="left"style="border-left: 2px solid;" style="border-right: 2px solid;"| max_size
+
! 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" |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
 
|-
 
|-
! 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"|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
 
|-
 
|-
! 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"|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
 +
 
 
|}
 
|}
 +
 +
[[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