Spec Tight Dependent StringSet
Very space efficient Dependent StringSet implementation.

Extends DependentStringSet
All Extended DependentStringSet, StringSet
All Impl'd AssignableConcept, ContainerConcept, DestructibleConcept, ForwardContainerConcept, RandomAccessContainerConcept, ReversibleContainerConcept, SegmentableConcept, StringConcept, TextConcept
Defined in <seqan/sequence.h>
Signature template <typename TString> class StringSet<TString, Depedent<Tight> >;

Template Parameters

TString The type of the string to store in the string set.

Member Function Overview

Member Functions Inherited From AssignableConcept

Member Functions Inherited From RandomAccessContainerConcept

Interface Function Overview

Interface Functions Inherited From StringSet

Interface Functions Inherited From AssignableConcept

Interface Functions Inherited From ContainerConcept

Interface Functions Inherited From RandomAccessContainerConcept

Interface Functions Inherited From SegmentableConcept

Interface Functions Inherited From StringConcept

Interface Functions Inherited From TextConcept

Interface Metafunction Overview

Interface Metafunctions Inherited From StringSet

Interface Metafunctions Inherited From ContainerConcept

Interface Metafunctions Inherited From SegmentableConcept

Interface Metafunctions Inherited From TextConcept

Detailed Description

The Tight Dependent StringSet stores pointers to a source set, enabling the user to perform deletions and additions to the set without changing the original source set (See DependentStringSet for further details).

Run time and Memory

When a value is removed from the Tight Dependent StringSet, the array of pointers is resized accordingly. Therefore, in order to call sequences by id or position, the stringset keeps a id-to-position map, which affects the run time complexity of the following functions:

- value() or operator []: O(1)

- getValueById(): O(log(n))

- removeValueById(): O(log(n))

The memory consumption is linear to the number of pointers.

See GenerousDependentStringSet for a Dependent StringSet implementation that allows for more efficient access to strings in the container via ids at the cost of higher memory usage.

Accessing non-existing entries results in undefined behaviour

Because the Tight Dependent StringSet keeps every array "tight", every entry that is being removed, is actually deleted (in contrast to Generous) and accessing it will result in undefined behaviour.