Using MAUtil Vector

The MAUtil::Vector class provides a generic, dynamically resizeable container similar to std::vector in the STL, Java's Vector or a .NET List. It provides many of the same familiar operations. 

Starting with Vectors

A Vector can be used as a generic collection, allowing you to grow the set whilst maintain the order in which items were added.  Vectors add items as their value type.  When you add or insert an item on the list, it adds the value or object to that list.  If you have a Vector of a complex object type, it will add that object to the list, and not a pointer to it, unless you explicitly request it.

For example

Vector<UserDetail> mUserDetails;

Will create a Vector of UserDetail objects, and not a Vector of UserDetail*.  Not all collections in MoSync behave in this manner.  To create a Vector of pointers to UserDetails objects, use

Vector<UserDetail*> mUserDetails;

Vectors are generic collections, so you define the type of object you want to store when you define the Vector.  The snippet below demonstrate creating Vector of int on the stack.

Vector<int> mInts;

Vectors store their items in contiguous memory.  Internally, there is an array which is used for storage with the Vector class maintaining the order.  Collections, including Vector, can cause you to run into memory allocation (malloc) errors if there isn't enough free contiguous memory left.  Broadly speaking, if you are storing a complex object type like the UserDetail object in the example above, you are always better off storing pointers than the values.  If you are using primitive types (int, byte), then store the values.

Adding items to a Vector

There are two ways you can add new items into a Vector, the add() and the insert().  The method add() appends the new item at the end of the list.

mInts.add(5);

You can also insert an item into the Vector at a requested position using the method insert().

mInts.insert(2, 100);

Where the first parameter is the index number you wish to insert the number (on a zero-based index) and the second is the value you wish to store.  All subsequent entries are moved along.  This has the potential to be very slow on large collections, so try to sort items before you enter them into the Vector. 

As the Vector is based on an array, you can still access the items using the [] operators.  You can use the index number to change the value of an item in an array.  This won't cause objects to be deleted, so if you are storing pointers to objects, then you will need to delete the item to prevent a memory leak.

UserDetails* mNewUser;
Vector<UserDetails*> mUserDetails;
...
// Overwrite the first entry.
UserDetails* temp = mUserDetails[0];
mUserDetails[0] = mNewUser;
delete temp; // Delete the old entry

Removing Items from a Vector

You can remove an item from a Vector using the remove() method.  There are two ways this can be called.  Firstly, you can request for a specific index number to be removed, but you can also remove with an iterator.  There is more about iterators below.

mUserDetails.remove(0);

Again, removing items from the Vector won't delete them from memory if they are pointers to objects.  You need to delete them explicitly or you will have a memory leak.

UserDetails* temp = mUserDetails[0];
mUserDetails.remove(0);
delete temp;

Removing items from the end of the list is very quick, but if you remove from the middle (or the start) of the list, then the other items need to be reordered, which can be slow.

Iterating through Vectors

You can work you're way through all the items in a Vector in two different ways.  As the Vector is based on an array, you can iterate through the items by index number 

Vector<int> numbers;
.... 
 // iterate through the vector using the 
// [] operator, printing each element.
for(int i = 0; i < numbers.size(); i++) {
    printf("numbers[i]: %d", numbers[i]);
}

A second method is to use the iterator.  Iterators are pointers to the items in the Vector, but are of a type

Vector<T>::iterator

Note that with Vectors the iterator has a low-case 'i' whilst in other collections (Set for example) the iterator has an upper-case 'I'.

Vector<int> numbers;
for(Vector<int>::iterator i = numbers.begin(); i < numbers.end(); i++)
{
  printf("%d", *i);
}

You can use the iterator to step through items in the Vector using the iterators returned by the methods begin() and end().  Also note that the iterator is a pointer to the value, so you will have to dereference it with an *.

Finally, there is a macro to make iteration more readable.  You can use the macro Vector_each to iterate the Vector. 

Vector_each(int, i, numbers)
{
    // The iterator needs to be dereferenced.
    printf("numbers[i]: %d", *i);
}

Vector_each takes three arguments; the type stored by the Vector, the variable name you want to refer to the iterator and finally the Vector itself.

Size and Capacity

There's an important distinction between the size and capacity of a Vector. Vectors grow dynamically to accomodate additional elements that are added to them. When an element is added, exceeding the current capacity, the capacity is doubled. However, the size only increases by one. This snippet demonstrates the behaviour:

for(int i = 0; i < 10; i++)
{
    numbers.add(i);
    printf("Size: %d  Capacity: %d", numbers.size(), numbers.capacity());
}

The output looks like this:

  Size: 1 Capacity: 4
  Size: 2 Capacity: 4
  Size: 3 Capacity: 4
  Size: 4 Capacity: 8
  Size: 5 Capacity: 8 
  Size: 6 Capacity: 8
  Size: 7 Capacity: 8
  Size: 8 Capacity: 16
  Size: 9 Capacity: 16
  Size: 10 Capacity: 16

In this case, the memory used to store the Vector elements is reallocated twice, each time requiring all the elements to be copied to the newly allocated memory location.

It is possible to reserve() a certain capacity, which is useful in cases when the number of elements to add is known beforehand (but not at compile time) in order to avoid superfluous reallocations:

numbers.reserve(11);
for(int i = 0; i < 10; i++)
{
    numbers.add(i);
    printf("Size: %d  Capacity: %d", numbers.size(), numbers.capacity());
}

The output looks like this:

  Size: 1 Capacity: 11
  Size: 2 Capacity: 11
  Size: 3 Capacity: 11
  Size: 4 Capacity: 11
  Size: 5 Capacity: 11 
  Size: 6 Capacity: 11
  Size: 7 Capacity: 11
  Size: 8 Capacity: 11
  Size: 9 Capacity: 11
  Size: 10 Capacity: 11

Note
Most functions that somehow manipulate the size of the vector do not affect the capacity if the new size is smaller than the previous. Do not assume that resize(0) will free up memory if the Vector previously contained thousands of elements.

Internal Storage