Difference between revisions of "Container Ideas"
(→Variable Implementation) |
(→Variable Implementation) |
||
| Line 1: | Line 1: | ||
== Variable Implementation == | == 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. | |
| − | 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. | ||
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 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. | ||
Revision as of 23:28, 13 February 2013
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.
Methods
| Sequence | Associative | Special Access | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Container | Double Linked List | Single Linked List | Random Access | Map | Multimap | MapSet | Set | Stack | Queue | PriorityQueue | |
| Types | Type | ||||||||||
| RangeType | |||||||||||
| cRangeType | |||||||||||
| ElementType | |||||||||||
| KeyType | |||||||||||
| Modify | insertFront(T) | ||||||||||
| insertFront(T...) | |||||||||||
| insertBack(T) | |||||||||||
| insertBack(T...) | |||||||||||
| insertBefore(RangeType, T) | |||||||||||
| insertBefore(RangeType, T...) | |||||||||||
| insertAfter(RangeType, T) | |||||||||||
| insertAfter(RangeType, T...) | |||||||||||
| removeFront(size_t = 1) | |||||||||||
| removeBack(size_t = 1) | |||||||||||
| remove(KeyType) | |||||||||||
| remove(Range) | |||||||||||
| remove(ElementType) | |||||||||||
| clear() | |||||||||||
| Access | front() | ||||||||||
| back() | |||||||||||
| opIndex(KeyType) | |||||||||||
| find(KeyType) | |||||||||||
| opSlice(KeyType) | |||||||||||
| opSlice(KeyType, KeyType) | |||||||||||
| in | |||||||||||
| Properties | length | ||||||||||
| empty | |||||||||||
| Capacity | capacity | ||||||||||
| compact | |||||||||||
| reserve | |||||||||||
| max_size | |||||||||||
