![]() |
Elm
2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
|
Classes | |
class | GenTree< T, K, C, A > |
class | Set< T, C > |
class | Map< K, T, C, E, A > |
class | Queue< T, C, A > |
class | StrictMapDelegate< C > |
class | EquivManager< T, E, A > |
class | CompareManager< T, C, E, A > |
class | HashManager< K, H, A > |
class | ArrayDelegate< C, I, T > |
class | MapDelegate< C, I, T, D > |
class | Bag< T > |
class | Slice< C > |
class | Array< T > |
class | AllocArray< T > |
class | BiDiList< T, E, A > |
class | BinomialQueue< T, C, A > |
class | FragTable< T, E, A > |
class | HashTable< T, H, A > |
class | HashMap< K, T, H, A, E > |
class | HashSet< T, H, A > |
class | List< T, E, A > |
class | ListQueue< T, M > |
class | class |
class | SortedList< T, C, A > |
class | ListSet< T, C, A > |
class | ListMapManager |
class | ListMap< K, T, C, E, A > |
class | StaticStack< T, N > |
class | Vector< T, E, A > |
class | PreIterator< I, T > |
class | InplacePreIterator< I, T > |
class | PreIter< I, T > |
class | ConstPreIter< I, T > |
class | MutPreIter< I, T > |
Functions | |
template<class A , class C = Comparator<typename A::t>> | |
void | quicksort (A &array, const C &c=Comparator< typename A::t >()) |
template<class C , class P > | |
int | count (const C &c, const P &p) |
template<class C , class P > | |
bool | forall (const C &c, const P &p) |
template<class C , class P > | |
bool | exists (const C &c, const P &p) |
template<class C , class F , class D > | |
void | map (const C &c, const F &f, D &d) |
template<class C , class F > | |
void | iter (const C &c, const F &f) |
template<class C > | |
C::t | sum (const C &c) |
template<class C > | |
C::t | product (const C &c) |
template<class C > | |
void | fill (C &c, int n, const typename C::t v=type_info< typename C::t >::null) |
template<class C1 , class C2 > | |
bool | equals (const C1 &c1, const C2 &c2) |
template<class C1 , class C2 > | |
Pair< typename C1::Iter, typename C2::Iter > | mismatch (const C1 &c1, const C2 &c2) |
template<class C > | |
void | deleteAll (const C &c) |
template<class C1 , class C2 , class P > | |
Pair< typename C1::Iter, typename C2::Iter > | mismatch (const C1 &c1, const C2 &c2, P p) |
template<class T > | |
Array< T > | _array (int n, T t[]) |
template<class I > | |
Range< I > | range (const I &begin, const I &end) |
This sections aims to help a developer to select a data structure fittings his needs. They are sorted according to different criteria: the right data structure to use is the one matching most of them. The criteria includes access type, collection size, etc.
Collection size:
Access type:
Modification type:
Memory footprint:
The array below sum up the complexity of operations for the data structures described above. When 2 complexity are give o1/o2, o1 is the average case and o2 the worst case.
For simple collections, we get:
Data Structure | adding | lookup | insertion | removal |
---|---|---|---|---|
Vector | O(1) | O(n) | O(n) | O(n) |
List | O(1) | O(n) | O(1) | O(1) |
BiDiList | O(1) | O(n) | O(1) | O(1) |
ListBag | O(log(n))/O(n) | O(log(n))/O(n) | O(1) | O(1) |
FragTable | O(1) | O(n) | O(n) | O(n) |
HashTable | O(b) | O(b) | O(1) | O(1) |
HashSet | O(b) | O(b) | O(1) | O(1) |
avl::Tree | O(log(n)) | O(log(n)) | O(1) | O(log(n)) |
avl::Set | O(log(n)) | O(log(n)) | O(1) | O(log(n)) |
Map operations:
Data Structure | lookup | insertion | removal |
---|---|---|---|
HashMap | O(b) | O(b) | O(b) |
avl::Map | O(log(n)) | O(log(n)) | O(log(n)) |
TreeMap | O(log(n))/O(n) | O(log(n))/O(n) | O(log(n))/O(n) |
ListMap | O(n) | O(n) | O(n) |
Random access to array elements:
Data Structure | Indexed Access |
---|---|
Array | O(1) |
FragTable | O(1) |
Vector | O(1) |
List | O(n) |
BiDiList | O(n) |
Stack (LIFO) operations:
Data Structure | push | pop |
---|---|---|
Vector | O(1) | O(1) |
List | O(1) | O(1) |
BiDiList | O(1) | O(1) |
FragTable | O(1) | O(1) |
Queue (FIFO) operations:
Data Structure | put | get |
---|---|---|
Vector | O(n) | O(1) |
List | O(1) | O(n) |
BiDiList | O(1) | O(1) |
FragTable | O(n) | O(1) |
VectorQueue | O(1) | O(1) |
ListQueue | O(1) | O(1) |
BinomialQueue | O(1) | O(log(n)) |
Set operations:
Data Structure | join | meet | difference |
---|---|---|---|
HashSet | O(bn) | O(bn) | O(bn) |
avl::Set | O(n) | O(n) | O(n) |
BitVector | O(n) | O(n) | O(n) |
Priority queues:
Data Structure | put | get |
---|---|---|
BinomialQueue | O(1) | O(log(n)) |
SortedList | O(n) | O(1) |
Basically, the PreIterator function avoids rewriting the large number of operator overloading. In fact, only the constructor and 3 functions need to be written:
Therefore, an iterator must be written as below (with T the type of iterated items):
And the use of such an iterator becomes:
Notices that if T is a pointer, the arrow iterator may be used without a star:
Likely, PreIterator provides automatic conversion to T:
Beside, PreIterator provides also a way to use iterators as in the STL. You have to provide a equals() function to test for equality:
And now the iteration can be written (with begin() the function returning the initial iterator and end() the end iterator):
A very fast and intuitive way to perform iteration on a collection of items proposed by C++ 11 requires a couple of begin()
and end()
functions declared in a collection object coll
:
Notice that i
is of type T, the type of iterated elements. As this is very convenient, all ELM data classes provide begin()
and end()
functions.
The following classes may help to work or to extend the concrete data structures:
<elm/data/quicksort.h>
provides a quicksort implementation for data collections:
Other functions provides very generic processing over the collection. They generically takes as parameter a collection, a class providing some specific computation and comes in two flavors, with or without an additional argument. To use them, one has to include <elm/data/util.h>
:
Other functions provides specialized iterators:
Other functions and classes are provided for easier combination:
Delegate class in ELM allows to get references on value managed by specific class functions to ensure their access or their assignment.
They support the same operations as the C++ references:
The following delegates exists:
Common customization of container classes includes the memory allocation, the element comparison or hashing.
Basically, the customization can be declared static and passed to the container using class templates:
In this case, the memory cost for such a customization is zero.
If the customization requires an instance, the instance has to be passed also to the constructor of the container. In this case, the container inherits from the customization class and this one must support a copy constructor where is passed the instance:
In this case, the container size grows according to the size of the instance customization class.
To support this behavior, delegate classes may help:. For instance, DefaultAllocator class provides access to OS allocation but it is passed by default to container as DefaultAllocatorDelegate that just propagate allocation to the default allocator.
The following delegate classes exist:
|
inline |
|
inline |
#include <include/elm/data/util.h>
Count the number of elements of c that matches the predicate p.
c | Collection to count in (must implement concept::Collection). |
p | Predicate to test element (must implement concept::Predicate). |
References elm::io::p().
Referenced by Tree::count(), JobScheduler::setThreadCount(), and InstanceType::typeFor().
|
inline |
#include <include/elm/data/util.h>
Consider that c is a collection of pointers and call the deletion on each of these pointers.
c | Collection of pointers to delete. |
C | Type of collection. |
|
inline |
#include <include/elm/data/util.h>
Test if two collections are equals.
c1 | First collection. |
c2 | Second collection. |
C1 | Type of first collection. |
C2 | Type of second collection. |
Referenced by VectorQueue< elm::Pair >::contains(), ArrayList< T, E >::contains(), AssocEquiv< K, T, E >::equals(), Vector< elm::dtd::AbstractAttribute * >::equals(), ArrayList< T, E >::find(), Vector< elm::dtd::AbstractAttribute * >::find(), ArrayList< T, E >::indexOf(), EqualsEquiv< T >::isEqual(), HashKey< T * >::isEqual(), HashKey< const T * >::isEqual(), ArrayList< T, E >::lastIndexOf(), and ArrayList< T, E >::remove().
|
inline |
#include <include/elm/data/util.h>
Test if the predicate p is true at least for one element of c.
c | Collection to test (must implement concept::Collection). |
p | Predicate to evaluate (must implement concept::Predicate). |
References elm::io::p().
#include <include/elm/data/util.h>
Add n items of value v to to the collection c.
c | Collection add values to. |
n | Number of values to add. |
v | Value to add (as a default, the null value). |
Referenced by WAHVector::clear(), builder::fix(), builder::pushLite(), WAHVector::set(), and WAHVector::WAHVector().
|
inline |
#include <include/elm/data/util.h>
Test if the predicate p is true for each element of c.
c | Collection to test (must implement concept::Collection). |
p | Predicate to evaluate (must implement concept::Predicate). |
References elm::io::p().
#include <include/elm/data/util.h>
Apply the function f on the element of collection c (ignoring the result).
c | Collection to iterate on (must implement concept::Collection). |
f | Function to apply (must implement concept::Function). |
Referenced by ArrayList< T, E >::addAll(), Tree::addAll(), BiDiList< T, E, A >::contains(), List< Pair< K, T >, CompareEquiv< AssocComparator< K, T, Comparator< K > > >, DefaultAlloc >::contains(), ArrayList< T, E >::containsAll(), Manager::displayHelp(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::find(), MarkerBuilder< K, T, C >::make(), SegmentBuilder< K, T, C >::make(), ArrayList< T, E >::removeAll(), Tree::removeAll(), CollectionSerializer< Vector< T >, T >::serialize(), DataSerializer< Vector< T, M >, T >::serialize(), and CollecAC< Coll, T >::serialize().
|
inline |
#include <include/elm/data/util.h>
Map the elements of a collection to element of another collection using the function f.
c | Original collection (must implement concept::Collection). |
f | Transforming function (must implement concept::Function). |
d | Filled collection (must implement concept::MutableCollection). |
Referenced by Map< Pair< K, K >, T, segment_comparator_t >::copy(), Map< Pair< K, K >, T, segment_comparator_t >::equals(), Map< Pair< K, K >, T, segment_comparator_t >::operator!=(), Map< Pair< K, K >, T, segment_comparator_t >::operator=(), and Map< Pair< K, K >, T, segment_comparator_t >::operator==().
Pair< typename C1::Iter, typename C2::Iter > mismatch | ( | const C1 & | c1, |
const C2 & | c2 | ||
) |
#include <include/elm/data/util.h>
Find the point of difference of two collection. Starting from the first element of the two collections, progress until either finding the end of a collection, or until the first different element of the collections.
c1 | First collection. |
c2 | Second collection. |
C1 | Type of first collection. |
C2 | Type of second collection. |
References elm::pair().
Pair< typename C1::Iter, typename C2::Iter > mismatch | ( | const C1 & | c1, |
const C2 & | c2, | ||
P | p | ||
) |
#include <include/elm/data/util.h>
Find the point of difference of two collection. Starting from the first element of the two collections, progress until either finding the end of a collection, or until the first different element of the collections. To test if two elements matches or not, the function p is used.
c1 | First collection. |
c2 | Second collection. |
p | Match predicate to decide if two elements are different. Must support the call p(element1, element2). |
C1 | Type of first collection. |
C2 | Type of second collection. |
P | Type of predicate. |
References elm::io::p(), and elm::pair().
|
inline |
#include <include/elm/data/util.h>
Perform the product of the items of collection c. An implementation of operator '*' must exist for these items.
c | Collection to multiply together. |
References elm::fold(), and elm::io::p().
void quicksort | ( | A & | array, |
const C & | c = Comparator<typename A::t>() |
||
) |
#include <include/elm/data/quicksort.h>
s
Sort the given array using quicksort algorithm (average complexity O(N log(N)) ).
array | Array containing the values to sort. |
c | Comparator to use (rely on ELM default comparator if not provided). |
T | Type of values. |
A | Type of array (must implement Array concept). |
C | Type of comparator (must implement Comparator or Compare concept). |
References elm::max(), and elm::swap().
Range< I > range | ( | const I & | begin, |
const I & | end | ||
) |
#include <include/elm/data/Range.h>
Creates a range from the iterator b to iterator e.
b | First position of the range (inclusive). |
e | One position after the last position of the range (exclusive). |
Fast way to build a range.
begin | Iterator on the first element of the collection. |
end | End iterator past the last element of the collection (may be ended). |
Referenced by Plugger::available(), and elm::select().
|
inline |
#include <include/elm/data/util.h>
Perform the sum of the items of collection c. An implementation of operator '+' must exist for these items.
c | Collection to sum up. |
References elm::fold().