Container Ideas

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