Spec
Tight Dependent StringSetVery 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
assignValue
assignValueById
clear
concat
getValueById
idToPosition
lengthSum
positionToId
removeValueById
reserve
strSplit
valueById
Interface Functions Inherited From AssignableConcept
Interface Functions Inherited From ContainerConcept
directionIterator
getObjectId
moveValue
append
appendValue
shrinkToFit
begin
end
length
empty
swap
writeValue
write
Interface Functions Inherited From RandomAccessContainerConcept
Interface Functions Inherited From SegmentableConcept
Interface Functions Inherited From StringConcept
capacity
computeGenerousCapacity
insert
insertValue
replace
iter
append
appendValue
front
back
resize
clear
erase
eraseFront
eraseBack
Interface Functions Inherited From TextConcept
Interface Metafunction Overview
Interface Metafunctions Inherited From StringSet
Interface Metafunctions Inherited From ContainerConcept
DefaultGetIteratorSpec
DefaultIteratorSpec
Difference
DirectionIterator
GetValue
Iterator
Position
Reference
Size
Value
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.