Overview
Examples
Screenshots
Comparisons
Applications
Download
Documentation
Bazaar
Status & Roadmap
FAQ
Authors & License
Forums
Funding Ultimate++
Search on this site
Language
English













SourceForge.net Logo

U++ Containers Tutorial


1. Vector basics

Let us start with a simple Vector of ints

    Vector<int> v;

You can add elements to the Vector as parameters of the Add method

    v.Add(1);

    v.Add(2);

    v.Add(3);

To iterate Vector you can use indices

    for(int i = 0; i < v.GetCount(); i++)

        LOG(v[i]);

1

2

3

Alternative, U++ also provides iterators

    for(Vector<int>::Iterator q = v.Begin(), e = v.End(); q != e; q++)

        LOG(*q);

1

2

3

however the use of iterators is usually reserved for special opportunities in U++ (like implementing algorithm code) and generally deprecated. We suggest you to use indices unless you have a really good reason to do otherwise.

Note: LOG is diagnostics macro that outputs its argument to the .log file in debug mode. Another similar macros we will use in this tutorial are DUMP (similar to the LOG, but dumps the source expression too) and DUMPC (dumps the content of the container).

 


2. Vector operations

You can Insert or Remove elements at random positions of Vector

    Vector<int> v;

    v.Add(1);

    v.Add(2);

    

    v.Insert(1, 10);

v = { 1, 10, 2 }

    v.Remove(0);

v = { 10, 2 }

At method returns element at specified position ensuring that such a position exists. If there is not enough elements in Vector, required number of elements is added. If second parameter of At is present, newly added elements are initialized to this value. As an example, we will create distribution of RandomValue with unknown maximal value

 

    v.Clear();

    for(int i = 0; i < 10000; i++)

        v.At(RandomValue(), 0)++;

v = { 958, 998, 983, 1012, 1013, 1050, 989, 998, 1007, 992 }

You can apply algorithms on containers, e.g. Sort

    Sort(v);

v = { 958, 983, 989, 992, 998, 998, 1007, 1012, 1013, 1050 }

 


3. Transfer issues

Often you need to pass content of one container to another of the same type. NTL containers always support pick semantics, and, depending on type stored, also might support clone sematics. When transfering the value, you have to explicitly specify which one to use:

    Vector<int> v;

    v.Add(1);

    v.Add(2);

 

    Vector<int> v1 = pick(v);

now source Vector v is destroyed - picked - and you can no longer access its content. This behaviour has many advantages. First, it is consistently fast and in most cases, transfer of value instead of full copy is exactly what you need. Second, NTL containers can store elements that lack copy operation - in that case, pick transfer is the only option anyway.

If you really need to preserve value of source (and elements support deep copy operation), you can use clone

    v = clone(v1);

 


4. Client types

So far we were using int as type of elements. In order to store client defined types into the Vector (and the Vector flavor) the type must satisfy moveable requirement - in short, it must not contain back-pointers nor virtual methods. Type must be marked as moveable in order to define interface contract using

    struct Distribution : Moveable<Distribution> {

        String      text;

        Vector<int> data;

 

        rval_default(Distribution);

        Distribution() {}

    };

Note that rval_default macro is helper to restore default deleted r-value constructor in C++11 and default constructor is also default deleted in C++11.

Now to add Distribution elements you cannot use Add with parameter, because it requires elements to have default deep-copy constructor - and Distribution does not have one, as Vector<int> has default pick-constructor, so Distribution itself has pick-constructor. It would no be a good idea either, because deep-copy would involve  expensive copying of inner Vector.

Instead, Add without parameters has to be used - it default constructs (that is cheap) element in Vector and returns reference to it

    Vector<Distribution> dist;

    for(int n = 5; n <= 10; n++) {

        Distribution& d = dist.Add();

        d.text << "Test " << n;

        for(int i = 0; i < 10000; i++)

            d.data.At(rand() % n, 0)++;

    }

 

Test 5: { 2018, 1992, 2025, 1988, 1977 }

Test 6: { 1670, 1682, 1668, 1658, 1646, 1676 }

Test 7: { 1444, 1406, 1419, 1493, 1370, 1418, 1450 }

Test 8: { 1236, 1199, 1245, 1273, 1279, 1302, 1250, 1216 }

Test 9: { 1115, 1111, 1100, 1122, 1192, 1102, 1089, 1064, 1105 }

Test 10: { 969, 956, 1002, 1023, 1006, 994, 1066, 1022, 929, 1033 }

Another possibility is to use AddPick method, which uses pick-constructor instead of deep-copy constructor. E.g. Distribution elements might be generated by some function

    Distribution CreateDist(int n);

and code for adding such elements to Vector then looks like

    for(n = 5; n <= 10; n++)

        dist.AddPick(CreateDist(n));

alternatively, you can use default-constructed variant too

        dist.Add() = CreateDist(); // alternative

 


5. Array flavor

If elements do not satisfy requirements for Vector flavor, they can still be stored in Array flavor. Another reason for using Array is need for referencing elements - Array flavor never invalidates references or pointers to them.

Example of elements that cannot be stored in Vector flavor are STL containers (STL does not specify the NTL flavor for obvious reasons):

    Array< std::list<int> > al;

    for(int i = 0; i < 4; i++) {

        std::list<int>& l = al.Add();

        for(int q = 0; q < i; q++)

            l.push_back(q);

    }

 


6. Polymorphic Array

Array can even be used for storing polymorphic elements

struct Number {

    virtual double Get() const = 0;

 

    String ToString() const { return AsString(Get()); }

    

    virtual ~Number() {}

};

 

struct Integer : public Number {

    int n;

    virtual double Get() const { return n; }

 

    Integer() {}

};

 

struct Double : public Number {

    double n;

    virtual double Get() const { return n; }

 

    Double() {}

};

 

bool operator<(const Number& a, const Number& b)

{

    return a.Get() < b.Get();

}

 

In this case, elements are added using Add with pointer to base element type parameter. Do not be confused by new and pointer, Array takes ownership of passed object and  behaves like container of base type elements

    Array<Number> num;

    num.Create<Double>().n = 15.5;

    num.Create<Integer>().n = 3;

num = { 15.5, 3 }

Thanks to well defined algorithm requirements, you can e.g. directly apply Sort on such Array

    bool operator<(const Number& a, const Number& b)

    {

        return a.Get() < b.Get();

    }

 

.......

 

    Sort(num);

num = { 3, 15.5 }


7. Bidirectional containers

Vector and Array containers allow fast adding and removing elements at the end of sequence. Sometimes, same is needed at begin of sequence too (usually to support FIFO like operations). In such case, BiVector and BiArray should be used

    BiVector<int> n;

    n.AddHead(1);

    n.AddTail(2);

    n.AddHead(3);

    n.AddTail(4);

n = { 3, 1, 2, 4 }

    n.DropHead();

n = { 1, 2, 4 }

    n.DropTail();

n = { 1, 2 }

    BiArray<Number> num;

    num.CreateHead<Integer>().n = 3;

    num.CreateTail<Double>().n = 15.5;

    num.CreateHead<Double>().n = 2.23;

    num.CreateTail<Integer>().n = 2;

num = { 2.23, 3, 15.5, 2 }


8. Index

Index is a container very similar to the plain Vector (it is random access array of elements with fast addition at the end) with one unique feature - it is able to fast retrieve position of element with required value using Find method

    Index<String> ndx;

    ndx.Add("alfa");

    ndx.Add("beta");

    ndx.Add("gamma");

    ndx.Add("delta");

    ndx.Add("kappa");

ndx = { alfa, beta, gamma, delta, kappa }

    DUMP(ndx.Find("beta"));

ndx.Find("beta") = 1

If element is not present in Index, Find returns a negative value

    DUMP(ndx.Find("something"));

ndx.Find("something") = -1

Any element can be replaced using Set method

    ndx.Set(0, "delta");

ndx = { delta, beta, gamma, delta, kappa }

If there are more elements with the same value, they can be iterated using FindNext method

    int fi = ndx.Find("delta");

    while(fi >= 0) {

        DUMP(fi);

        fi = ndx.FindNext(fi);

    }

    cout << 'n';

0 3    

FindAdd method retrieves position of element like Find, but if element is not present in Index, it is added

    DUMP(ndx.FindAdd("one"));

    DUMP(ndx.FindAdd("two"));

    DUMP(ndx.FindAdd("three"));

    DUMP(ndx.FindAdd("two"));

    DUMP(ndx.FindAdd("three"));

    DUMP(ndx.FindAdd("one"));

 

ndx.FindAdd("one") = 5

ndx.FindAdd("two") = 6

ndx.FindAdd("three") = 7

ndx.FindAdd("two") = 6

ndx.FindAdd("three") = 7

ndx.FindAdd("one") = 5

Removing elements from random access sequence is always expensive, that is why rather than remove, Index supports Unlink and UnlinkKey operations, which leave element in Index but make it invisible for Find operation

    ndx.Unlink(2);

    ndx.UnlinkKey("kappa");

 

    DUMP(ndx.Find(ndx[2]));

    DUMP(ndx.Find("kappa"));

 

ndx.Find(ndx[2]) = -1

ndx.Find("kappa") = -1

You can test whether element at given position is unlinked using IsUnlinked method

    DUMP(ndx.IsUnlinked(1));

    DUMP(ndx.IsUnlinked(2));

 

ndx.IsUnlinked(1) = 0

ndx.IsUnlinked(2) = 1

Unlinked positions can be reused by Put method

    ndx.Put("foo");

ndx = { delta, beta, foo, delta, kappa, one, two, three }

    DUMP(ndx.Find("foo"));

ndx.Find("foo") = 2

You can also remove all unlinked elements from Index using Sweep method

    ndx.Sweep();

ndx = { delta, beta, foo, delta, one, two, three }

As we said, operations directly removing or inserting elements of Index are very expensive, but sometimes this might not matter, so they are available too

    ndx.Remove(1);

ndx = { delta, foo, delta, one, two, three }

    ndx.RemoveKey("two");

ndx = { delta, foo, delta, one, three }

    ndx.Insert(0, "insert");

ndx = { insert, delta, foo, delta, one, three }

Finally, PickKeys operation allows you to obtain Vector of elements of Index in low constant time operation (while destroying source Index)

    Vector<String> d = ndx.PickKeys();

    Sort(d);

d = { delta, delta, foo, insert, one, three }


9. Index and client types

In order to store elements to Index, they must be moveable (you can use ArrayIndex for types that are not) and they must have defined the operator== and a function to compute hash value. Notice usage THE of CombineHash to combine hash values of types already known to U++ into final result

 

struct Person : Moveable<Person> {

    String name;

    String surname;

 

    unsigned GetHashValue() const          { return CombineHash(name, surname); }

    bool operator==(const Person& b) const { return name == b.name && surname == b.surname; }

 

    Person(String name, String surname) : name(name), surname(surname) {}

    Person() {}

};

 

.......

 

    Index<Person> p;

    p.Add(Person("John", "Smith"));

    p.Add(Person("Paul", "Carpenter"));

    p.Add(Person("Carl", "Engles"));

          

    DUMP(p.Find(Person("Paul", "Carpenter")));

p.Find(Person("Paul", "Carpenter")) = 1


10. VectorMap, ArrayMap

VectorMap is nothing more than a simple composition of Index and Vector. You can use Add methods to put elements into the VectorMap

    VectorMap<String, Person> m;

    

    m.Add("1", Person("John", "Smith"));

    m.Add("2", Person("Carl", "Engles"));

 

    Person& p = m.Add("3");

    p.name = "Paul";

    p.surname = "Carpenter";

VectorMap provides constant access to its underlying Index and Vector

    DUMP(m.GetKeys());

    DUMP(m.GetValues());

 

m.GetKeys() = { 1, 2, 3 }

m.GetValues() = { John Smith, Carl Engles, Paul Carpenter }

 

You can use indices to iterate map contents

    for(int i = 0; i < m.GetCount(); i++)

        LOG(m.GetKey(i) << ": " << m[i]);

 

1: John Smith

2: Carl Engles

3: Paul Carpenter

 

You can use Find method to retrieve position of element with required key

    DUMP(m.Find("2"));

m.Find("2") = 1

or Get method to retrieve corresponding value

    DUMP(m.Get("2"));

m.Get("2") = Carl Engles

Passing key not present in VectorMap as Get parameter is a logic error, but there exists two parameter version that returns second parameter if key is not in VectorMap

    DUMP(m.Get("33", Person("unknown", "person")));

m.Get("33", Person("unknown", "person")) = unknown person

As with Index, you can use Unlink to make elements invisible for Find operations

    m.Unlink(1);

    DUMP(m.Find("2"));

m.Find("2") = -1

You can use SetKey method to change the key of the element

    m.SetKey(1, "33");

    DUMP(m.Get("33", Person("unknown", "person")));

m.Get("33", Person("unknown", "person")) = Carl Engles

If there are more elements with the same key in VectorMap, you can iterate them using FindNext method

    m.Add("33", Person("Peter", "Pan"));

 

m.GetKeys() = { 1, 33, 3, 33 }

m.GetValues() = { John Smith, Carl Engles, Paul Carpenter, Peter Pan }

 

    int q = m.Find("33");

    while(q >= 0) {

        cout << m[q] << 'n';

        q = m.FindNext(q);

    }

    

Carl Engles

Peter Pan

 

You can reuse unlinked positions using Put method

    m.UnlinkKey("33");

    m.Put("22", Person("Ali", "Baba"));

    m.Put("44", Person("Ivan", "Wilks"));

 

m.GetKeys() = { 1, 22, 3, 44 }

m.GetValues() = { John Smith, Ali Baba, Paul Carpenter, Ivan Wilks }

 

GetSortOrder algorithm returns order of elements as Vector<int> container. You can use it to order content of VectorMap without actually moving its elements

    bool operator<(const Person& a, const Person& b)

    {

        return a.surname == b.surname ? a.name < b.name

                                  : a.surname < b.surname;

    }

 

.......

 

    Vector<int> order = GetSortOrder(m.GetValues());

order = { 1, 2, 0, 3 }

    for(int i = 0; i < order.GetCount(); i++)

        cout << m.GetKey(order[i]) << ": " << m[order[i]] << 'n';

 

22: Ali Baba

3: Paul Carpenter

1: John Smith

44: Ivan Wilks

 

You can get Vector of values or keys using PickValues resp. PickKeys methods in low constant time, while destroying content of source VectorMap

    Vector<Person> ps = m.PickValues();

ps = { John Smith, Ali Baba, Paul Carpenter, Ivan Wilks }

If type of values does not satisfy requirements for Vector elements or if references to elements are needed, you can use ArrayMap instead

    ArrayMap<String, Number> am;

    am.Create<Integer>("A").n = 11;

    am.Create<Double>("B").n = 2.1;

 

am.GetKeys() = { A, B }

am.GetValues() = { 11, 2.1 }

 

    DUMP(am.Get("A"));

    DUMP(am.Find("B"));

 

am.Get("A") = 11

am.Find("B") = 1

 


11. One

One is a container that can store none or one element of T or derived from T. It functionally quite similiar to std::unique_ptr, but has some more convenient features (like Create method).

struct Base {

    virtual String Get() = 0;

    virtual ~Base() {}

};

 

struct Derived1 : Base {

    virtual String Get() { return "Derived1"; }

};

 

struct Derived2 : Base {

    virtual String Get() { return "Derived2"; }

};

 

void MakeDerived1(One<Base>& t)

{

    t.Create<Derived1>();

}

 

void MakeDerived2(One<Base>& t)

{

    t.Create<Derived2>();

}

 

.......

    One<Base> s;

Operator bool of one returns true if it contains an element:

    DUMP((bool)s);

 

(bool)s = false

 

    

    s.Create<Derived1>();

    DUMP((bool)s);

    DUMP(s->Get());

 

(bool)s = true

s->Get() = Derived1

 

Clear method removes the element from One:

    s.Clear();

    DUMP((bool)s);

 

(bool)s = false

 

 

One represents a convenient and recommended method how to deal with class factories in U++: Define then as function with reference to One parameter, e.g.:

void MakeDerived1(One<Base>& t)

{

    t.Create<Derived1>();

}

 

void MakeDerived2(One<Base>& t)

{

    t.Create<Derived2>();

}

 

VectorMap<int, void (*)(One<Base>&)> factories;

 

INITBLOCK {

    factories.Add(0, MakeDerived1);

    factories.Add(1, MakeDerived2);

};

 

void Create(One<Base>& t, int what)

{

    (*factories.Get(what))(t);

}

 


12. Any

Any is a container that can contain none or one element of any type, the only requirement is that the type has default constructor. Impotant thing to remember is that Is method matches exact type ignoring class hierarchies (FileIn is derived from Stream, but if Any contains FileIn, Is<Stream>() returns false).

void Do(Any& x)

{

    if(x.Is<String>())

        LOG("String: " << x.Get<String>());

    if(x.Is<FileIn>()) {

        LOG("--- File: ");

        LOG(LoadStream(x.Get<FileIn>()));

        LOG("----------");

    }

    if(x.IsEmpty())

        LOG("empty");

}

 

.....

 

    Any x;

    x.Create<String>() = "Hello!";

    Do(x);

    x.Create<FileIn>().Open(GetDataFile("Ntl12.cpp"));

    Do(x);

    x.Clear();

    Do(x);

 


13. InVector, InArray

InVector and InArray are vector types quite similar to Vector/Array, but they trade the speed of operator[] with the ability to insert or remove elements at any position quickly. You can expect operator[] to be about 10 times slower than in Vector (but that is still very fast), while Insert at any position scales well up to hunderds of megabytes of data (e.g. InVector containing 100M of String elements is handled without problems).

    InVector<int> v;

    for(int i = 0; i < 1000000; i++)

        v.Add(i);

    v.Insert(0, -1); // This is fast

    DUMP(v[0]);

    DUMP(v[1]);

 

While the interface of InVector/InArray is almost identical to Vector/Array, InVector/InArray in addition implements FindLowerBound/FindUpperBound functions - while normal random access algorithms work, it is possible to provide InVector specific optimization that basically matches the performace of Find*Bound on somple Vector.

 

    DUMP(v.FindLowerBound(55));

 


14. SortedIndex, SortedVectorMap, SortedArrayMap

SortedIndex is similar to regular Index, but keeps its elements in sorted order (sorting predicate is a template parameter, defaults to StdLess). Implementation is using InVector, so it works fine even with very large number of elements (performace is similar to tree based std::set). Unlike Index, SortedIndex provides lower/upper bounds searches, so it allow range search.

    SortedIndex<int> x;

    x.Add(5);

    x.Add(3);

    x.Add(7);

    x.Add(1);

    

    DUMPC(x);

    DUMP(x.Find(3));

    DUMP(x.Find(3));

    DUMP(x.FindLowerBound(3));

    DUMP(x.FindUpperBound(6));

 

SortedVectorMap and SortedArrayMap are then SortedIndex based equivalents to VectorMap/ArrayMap - maps that keep keys sorted:

    SortedVectorMap<String, int> m;

    m.Add("zulu", 11);

    m.Add("frank", 12);

    m.Add("alfa", 13);

    

    DUMPM(m);

    DUMP(m.Get("zulu"));

 


15. Tuples

U++ has template classes Tuple2, Tuple3 and Tuple4 for combining 2-4 values with different types. These are quite similiar to std::tuple class, with some advantages.

To create a Tuple value, you can use the Tuple function. If correct types canot be deduced from parameters, you can specify them explicitly:

    Tuple3<int, String, String> x = Tuple<int, String, String>(12, "hello", "world");

 

Individual values are accessible as members a .. d:

 

    DUMP(x.a);

    DUMP(x.b);

    DUMP(x.c);

    

As long as all individual types have conversion to String (AsString), the tuple also has such conversion and thus can e.g. be easily logged:

 

    DUMP(x);

 

Also, as long as individual types have defined GetHashValue, so does Tuple:

 

    DUMP(GetHashValue(x));

 

As long as individual types have defined operator==, Tuple has defined operator== and operator!=

 

    Tuple3<int, String, String> y = x;

    DUMP(x != y);

 

Finally, as long as all individual types have defined SgnCompare (most U++ types have), Tuple has SgnCompare, Compare method and operators <, <=, >, >=:

 

    DUMP(x.Compare(y));

    

    y.b = "a";

    

    DUMP(SgnCompare(x, y));

    DUMP(x < y);

    

 

U++ Tuples are strictly designed as POD type, which allows POD arrays to be intialized with classic C style:

    static Tuple2<int, const char *> map[] = {

        { 1, "one" },

        { 2, "one" },

        { 3, "one" },

    };

    

Simple FindTuple template function is provided to search for tuple based on the first value:

 

    Tuple2<int, const char *> *f = FindTuple(map, __countof(map), 2);

    if(f)

        DUMP(f->b);

 

Last edit by cxl on 11/13/2014. Do you want to contribute?. T++