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 follow default pick semantics, that means that source container is destroyed
Vector<int> v;
v.Add(1);
v.Add(2);
Vector<int> v1 = v;
now source Vector v is destroyed - picked - and you can no longer access its content. This admittedly strange 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 optional deep copy operator or constructor
v <<= v1;
Now both containers have the same content. Constructor form of same operation is distinguished by an additional int parameter
Vector<int> v2(v, 0);
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;
};
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()); }
};
struct Integer : public Number {
int n;
virtual double Get() const { return n; }
Integer(int n) : n(n) {}
};
struct Double : public Number {
double n;
virtual double Get() const { return n; }
Double(double n) : n(n) {}
};
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.Add(new Integer(3));
num.Add(new Double(15.5));
num.Add(new Double(2.23));
num.Add(new Integer(2));
num.Add(new Integer(20));
num.Add(new Double(-2.333));
num = { 3, 15.5, 2.23, 2, 20, -2.333 }
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 = { -2.333, 2, 2.23, 3, 15.5, 20 }
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.AddHead(new Integer(3));
num.AddTail(new Double(15.5));
num.AddHead(new Double(2.23));
num.AddTail(new Integer(2));
num.AddHead(new Integer(20));
num.AddTail(new Double(-2.333));
num = { 20, 2.23, 3, 15.5, 2, -2.333 }
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 of CombineHash to combine hash values of types already known to U++ into final result
struct Person : Moveable<Person> {
String name;
String surname;
Person(String name, String surname)
: name(name), surname(surname) {}
Person() {}
};
unsigned GetHashValue(const Person& p)
{
return CombineHash(p.name, p.surname);
}
bool operator==(const Person& a, const Person& b)
{
return a.name == b.name && a.surname == b.surname;
}
.......
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
If type cannot be stored in Index or if references to elements are required, ArrayIndex can be used
unsigned GetHashValue(const Number& n)
{
return GetHashValue(n.Get());
}
bool operator==(const Number& a, const Number& b)
{
return a.Get() == b.Get();
}
.......
ArrayIndex<Number> n;
n.Add(new Integer(100));
n.Add(new Double(10.5));
n.Add(new Integer(200));
n.Add(new Double(20.5));
n = { 100, 10.5, 200, 20.5 }
DUMP(n.Find(Double(10.5)));
n.Find(Double(10.5)) = 1
10. VectorMap
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.Add("A", new Integer(1));
am.Add("B", new Double(2.0));
am.GetKeys() = { A, B }
am.GetValues() = { 1, 2 }
DUMP(am.Get("A"));
DUMP(am.Find("B"));
am.Get("A") = 1
am.Find("B") = 1
|
