The MoSync SDK provides several different collection objects, suitable for different occasions. Collections let you deal with sets of object collectively, but the way you access the collection varies.
Typically, collections will be created on the stack rather than the heap. This will mean that if you have a collection of object pointers (the objects themselves will be in the heap), and the collection goes out of scope, you may loose the pointers to the objects in the heap and you won't be able to access them. The objects will still exist though, and you've got a memory leak. Keep close track of collections, and ensure that they are in a suitable scope. Object scope is very commonly used.
class MyClass
{
public:
MyClass();
virtual ~MyClass();
private:
Vector<MyObject*> myVector;
};In the above example, the Vector of MyObject pointers will be created when the object is created, and destroyed when the object is destroyed. The objects the pointer point to will not be destroyed unless you specifically destroy them. You can do this in the class destructor if you do not wish to refer to those objects again.
MyClass::~MyClass()
{
//Destroy the objects in my Vector
Vector_each(MyObject*, itr, myVector) {
delete *itr; //Delete the object
}
}Always be aware of the lifespan of objects in collections, and delete the objects as necessary.
In most collections, there are ways to iterate through the contents. These are specific to the collection type, and methods for iteration are described with each collection type. They are not consistent, so don't assume that because you can use one method for iterating one type of collection it will be exactly the same for another.
In C++ there isn't an iteration interface, nor is there a keyword for iteration. For example, in C# there is the IEnumerable interface and the foreach keyword which lets you iterate through any collection:
foreach(String in myStringCollection)
{
}This isn't supported in C++, so iteration is slightly more verbose.
Arrays and Vectors are the simplest collections in MoSync. They provide easy access to stored objects and data, and can be returned by functions and methods.
The simplest collection type is an array. This is supported in C and C++ rather than being a collection supported in MoSync specifically. It provides random access (that is, you can access any item in the collection), but it stores its contents sequentially in memory. This can cause problems if you are storing a lot of large objects, as the contiguous memory may not be available.
You can create an array by using the [] operators. Arrays can be of any object or primitive type. You must specify the size of the array when you create it and arrays cannot be easily resized, nor can items be easily inserted into them. They are small, require no additional overhead and are fast. This code will create an array of twenty chars.
char myCharArray[20];
Any item in the array can be accessed by its zero-based index number.
char thirdChar = myCharArray[2]; // Zero-based
Values can be written as well
myCharArray[2] = 'c';
When you have finished with an array, you will need to use the delete [] instruction, and not delete.
delete [] myCharArray;
Which will then delete every item in the array.
Typically in arrays (and most collections), you'll store a primitive value (char, int, byte et cetera), or an object pointer. You can store objects in the array directly, but enough contiguous memory must be available.
To iterate through an array, you access the array with the [] operator sequentially. You do need to know the size of the array before you start, but you need to know that to create it. For example
for(int i = 0; i < 20; i++)
{
printf("%c", myCharArray[i]);
}Vectors are part of the MAUtil namespace. To use them, you will need to include MAUtil/Vector.h.
#include <MAUtil/Vector.h> using namespace MAUtil;
A vector is an object wrapper around an array. All the storage will be done in the array, but the vector will let you iterate through the collection, insert items into the collection and resize the collection.
Vectors are similar to C# and Java List<> collections. MoSync List<> collections are not. See below for details of MoSync List<>.
You don't need to specify a size when you create a vector.
Vector<MyObject*> myVector;
What you do need to specify is the type of data you are going to store, by adding the type name between the angle brackets. Once you specify this, you can only add items of that type. In the above instance, these are MyObject pointers. You can only add MyObject pointers to this vector, and not MyObjects themselves or pointers of a different class.
You can add items into the vector using the .add() method.
myVector.add(new MyObject());
You can also insert items at a specific point.
myVector.insert(2, new MyObject());
Existing items will be moved down the underlying array. This is a comparitvely expensive operation, so only do it if the order is important.
Vectors maintain the order in which you add items. If you iterate through the vector, you will find objects in the same order you added or inserted them.
Individual items can be removed from vectors using the remove() method. There are three different ways you can remove items from a vector.
myVector.remove(MyObject**);
This is a pointer to a MyObject pointer. We'll look at iterators shortly, but MyObject** will probably be an iterator.
myVector.remove(1);
Removes the second item from the zero-based index.
myVector.remove(1, 3);
To completely empty a vector, you can use the clear() method.
Removes the second, third and fourth items from the vector. Remember, this does not delete any objects if your vector contains pointers. It only removes the pointers. If you want to delete the object you must still use delete.
The vector starts with a small array of the type you've specified. By default it will create an array of the type containing four items. If you add a fifth, then the a new array is created, and all the items are copied across. The new array will be twice the size of the old array. If you exceed the reserved space, then the array will be recreated and the data carried across again. The obviously adds overhead. If you know that you want 20 items, then create it with space for 20 items. You can do this in three ways.
Firstly, you can set the size in the constructor. As Vectors are normally created on the stack, then there is no opportunity to use the new instruction. Instead, in C++ you can specify it when your object is created. In your header file (.h) you can have something like this:
class MyClass
{
public:
MyClass();
virtual ~MyClass();
private:
Vector<MyObject*> myVector;
};And in the code file (.cpp) you can specify the size of the vector in the constructor.
#include "MyClass.h"
MyClass::MyClass() : myVector(20)
{
}This will initialise the vector with a size of 20. There are also two methods for sizing the vector, resize() and reserve(). Both will set the size of the underlying array, but resize() will move the current cursor to the end of the array. This means that if you resize(20) and then .add(new MyObject()) then the vector will have 21 items in it and have a capacity of 40. In general, use reserve() when you want to allocate memory. You cannot resize() or reserve() to a size smaller than you are currently using.
You can get the current usage by using the size() and capacity() methods. If you want to know how many items are in a vector, use size(). To find out how many it can take, use capacity(). To easily find if the vector is empty, use the empty() method.
if(myVector.empty())
{
// Do something.
}Vectors, like arrays, are random access. You can access any item in the vector using [].
MyObject* myObject = myVector[3];
You can also get direct access to the array using the pointer() method.
To iterate a vector, you use a vector iterator. These are pointers to each item in the vector, and are of the type Vector<Type>::iterator. For example
Vector<MyObject*>::iterator
You can get iterators to the first object, and to the point beyond the last object using the begin() and end() methods. Because the underlying array is in contiguous memory, then the iterators are sequential. The iterator is really a pointer to the type of the object (or value) stored. In our example, the iterator will be of a type MyObject**. It is a pointer to a MyObject pointer.
We can use the iterators from begin() and end() to test our iteration.
for(Vector<MyObject*>::iterator itr = myVector.begin();
itr != myVector.end();
itr++)
{
// Do something.
}This will then give us a MyObject** for each loop, called itr. You can use the object stored as normal if you dereference it.
MyObject* currentObject;
for(Vector<MyObject*>::iterator itr = myVector.begin();
itr != myVector.end();
itr++)
{
currentObject = *itr; // Dereference it.
currentObject->method();
}There is also a macro you can use a short cut for iterating vectors. Vectors are now the only collection to have such a macro.
Vector_each(Type, iterator variable, vector);
For instance, instead of the long for statement earlier, we can have the more readable
Vector_each(MyObject*, itr, myVector)
{
// Do something.
}If you change the vector during an iterative process, the iterator may become invalid, with undefined consequences. Don't add or remove items from a vector whilst you are iterating through it.
Lists are part of the MAUtil namespace. To use them, you will need to include MAUtil/List.h.
#include <MAUtil/List.h> using namespace MAUtil;
If you come from a Java or C# background, List will not behave as you expect. The MoSync equivalent of a Java/C# List is Vector<>. In MoSync Lists are doubly-linked lists.
MoSync lists allow you to create a collection of items, where each item knows which is the item before it and after it in the list. This has a big impact on how you iterate through a list.
As there isn't an underlying array, then you don't need to specify the size of your collection, nor is there an impact on performance for inserting an item in the list. Each object or value you store will be wrapped in a very light object, so there is a very small memory overhead, but its flexibility is superb.
The downside of this is that there isn't any method of random access. You have to navigate the list serially, although you can go backwards and forwards through the list.
You create the list in a similar way to the vector.
List<MyObject*> myList;
You can then add items very easily to either the beginning or the end of the list by using addFirst() and addLast() respectively.
You can only add items into the middle of the list, or remove items from the if you've got an iterator.
You can get an iterator in the same way as you can with a vector, using the begin() and end() methods. You can then access the objects and values stored using the prev() and next() methods. You can test to see if you are at the start or end of a list using the hasPrev() and hasNext() methods.
The iterators for lists are of the type List<type>::ListIterator and List<type>::ConstListIterator. Note the capitalisation of Iterator for this iterator.
List<MyObject*>::ListIterator itr = myList.begin();
MyObject* currentObject;
while(itr.hasNext())
{
currentObject = itr.next();
}Note that you don't increment the iterator like you do with vectors. The next() and prev() methods return the value stored and increment the iterator.
You can insert items into list without much of a perform hit as there is no array to reallocate. You do have to do this from an iterator though.
itr = myList.begin();
while(itr.hasNext())
{
if(itr.next() == 1)
{
// Add the value 2 after this item.
myList.insert(itr, 2);
}
}Equally, remove is done through the iterator. When you add an item using insert it is placed after current iterator. When you remove() an item, it removes the item from the current position. ListIterators are not corrupted if you alter the collection, unlike vectors. Remember, if you remove a pointer to an object, you are not destroying the object itself. You still need to call delete.
The code below shows creating and altering a List<int>.
#include <MAUtil/Moblet.h>
#include <conprint.h>
#include <MAUtil/List.h>
using namespace MAUtil;
class MyMoblet : public Moblet
{
public:
List<int> myList;
MyMoblet()
{
// Create a list with an item missing.
myList.addFirst(0);
myList.addLast(1);
myList.addLast(3);
// Show the original list
showList();
// Now add 2 into the list
List<int>::ListIterator itr = myList.begin();
itr = myList.begin();
while(itr.hasNext())
{
if(itr.next() == 1)
{
// Add the value 2 after this item
myList.insert(itr, 2);
lprintfln("Added 2");
}
}
// Now show the list again
showList();
// Now remove 1 from the list
itr = myList.begin();
while(itr.hasNext())
{
if(itr.next() == 1)
{
// Remove this item
myList.remove(itr);
lprintfln("Removed 1");
}
}
// Now show the list again
showList();
}
void keyPressEvent(int keyCode, int nativeCode)
{
this->close();
}
void showList()
{
lprintfln("I've got %d items", myList.size());
List<int>::ListIterator itr = myList.begin();
while(itr.hasNext())
{
lprintfln("Next value : %d", itr.next());
}
}
};
extern "C" int MAMain()
{
Moblet::run(new MyMoblet());
return 0;
}There are two conceptually related, but utterly separate collections in MoSync - Stack and Queue. They both are designed for serial access to collections where the order of the collection is vital.
Stacks are part of the MAUtil namespace. To use them, you will need to include MAUtil/Stack.h.
#include <MAUtil/Stack.h> using namespace MAUtil;
The Stack collection (capitalised to show that we don't mean the stack program memory, but a Stack<> collection), is a vector, but where you can only access the most recently added item. You can put as many items as you want onto the Stack, but you can only get the latest item. If you imagine a stack of books, you can see that it is only the book at the top which is accessible. This kind of collection is also called first-in-last-out or very occasionally, FILO.
You create a Stack like you would a vector
Stack<MyObject*> myStack;
Unlike vectors though, you cannot specify a size in advance. It uses the vector's default initial size of 4, and will resize itself when it needs to.
When you want to add an item on a Stack, you are said to push it onto the Stack. The method for adding to a stack is then
myStack.push(new MyObject());
When you want to remove an item from the stack, you are said to pop it off the Stack.
myStack.pop();
Remember, if you have a collection of object pointers, popping an item off the stack will not destroy the object. You have to call delete yourself.
To get access to the next item on the Stack using the method peek().
MyObject* nextObject = myStack.peek();
You can test the size of the Stack using size() although you cannot test its capacity. You can also see if it has no items in it using empty(). You can remove all the items from the stack at once using clear().
There are no iterators in the stack. If you want to find an item, you have to keep popping items off the top until you get the one you want. If you want to remove an item from the middle, you need to copy the data to another Stack.
As you'll see from the example below, iterating Stacks is laborious. They are best suited to times when the order is important. They are frequently used to allow users to retrace their steps. For instance, you can keep track of the order the user navigated the screens in your application. When the users wants to go back one screen, then you can pop the last value off your stack.
#include <MAUtil/Moblet.h>
#include <conprint.h>
#include <MAUtil/Stack.h>
using namespace MAUtil;
class MyMoblet : public Moblet
{
public:
Stack<int> myStack;
MyMoblet()
{
// Create a list with an item missing.
myStack.push(3);
myStack.push(1);
myStack.push(0);
// Show the original stack
showStack();
// Now add 2 into the stack
// We need another stack to copy removed items to.
Stack<int> tempStack;
while(myStack.peek() != 1)
{
// Copy the top of the stack to another stack. Remember that the new stack will
// have everything in reverse order
tempStack.push(myStack.peek());
myStack.pop();
}
// Add the value 2
myStack.push(2);
// Now copy everything back again
while(tempStack.size() > 0)
{
myStack.push(tempStack.peek());
tempStack.pop();
}
// Now show the Stack again
showStack();
// Now remove 1 from the stack
while(myStack.peek() != 1)
{
// Copy the top of the stack to another stack. Remember that the new stack will
// have everything in reverse order
tempStack.push(myStack.peek());
myStack.pop();
}
// The item at the top is 1. Remove it
myStack.pop();
// Now copy everything back again
while(tempStack.size() > 0)
{
myStack.push(tempStack.peek());
tempStack.pop();
}
// Now show the Stack again.
showStack();
}
void keyPressEvent(int keyCode, int nativeCode)
{
this->close();
}
void showStack()
{
lprintfln("I've got %d items", myStack.size());
// We need to copy the Stack to another stack whilst we go through it.
Stack<int> tempStack;
while(myStack.size() > 0)
{
lprintfln("Next value : %d", myStack.peek());
tempStack.push(myStack.peek());
myStack.pop();
}
// OK, we've shown them all, now we need to put myStack back together.
while(tempStack.size() > 0)
{
myStack.push(tempStack.peek());
tempStack.pop();
}
}
};
extern "C" int MAMain()
{
Moblet::run(new MyMoblet());
return 0;
}Queues are part of the MAP namespace. To use them, you will need to include MAP/Queue.h, and ensure that you've got MAP.lib included as a library in your project settings. Alternatively, copy the file Queue.h out of the includes directory and include it directly in your project, although if you do this, you will need to replace newobject() with new and deleteobject() with delete, or alternatively, implement the MemoryMgr class as well.
#include <MAP/Queue.h> using namespace MAP;
Queues are logically very similar to Stacks, but the implementation is quite different. Differences in implementation will be highlighted as the collection is described.
Logically, a queue is the same as a Stack, with the exception that the first item is the only one available, not the last item. This is sometimes called first-in-first-out or very occasionally FIFO.
To create a queue, it is almost the same as stack
Queue<MyObject> myQueue;
The important difference to note is the data type you provide it. MoSync queues only contain pointers. You provide it with the type of data pointer you want. The above code will create a Queue of MyObject pointers, and not MyObject, despite what it looks like. If you had the code
Queue<MyObject*> myQueue;
You would get a queue of MyObject**. Equally then
Queue<int> myQueue;
Will create a queue of int* and not int.
When you add an item to a queue, this is called enqueueing, and the method is enqueue(). To remove a method, you dequeue() it. Whereas with the Stack, when you peek() at a value it leaves it on the Stack and have to pop() it off, dequeue() will remove it from the collection. It is the responsibility of the code calling dequeue() to delete the object after use if necessary to prevent memory leaks.
myQueue.enqueue(new MyObject()); MyObject* currentObject = myQueue.dequeue();
Whilst Queues were not designed for random access, there are methods in the MoSync implementation for accessing values at will. There aren't any iterators with queues however.
You can read values using peekAt() method, providing the method with the index number of the value you want, or peek() which will return the next item, although these will leave the item in the queue.
You can also find the location in the queue of a specific object. The find() method will return an items index number.
Like vectors, you can set capacity of the queue, and it has an array internally for storage. Unlike a vector, you cannot resize a queue, so when it is full, then that's it. Your item will not be added, no return value will be given by enqueue() and no error will be raised, so it is important to check the amount of space left in the queue using getCapacity() (not capacity() like in vector) and getCount() (not size()).
You can remove all the items in the queue (but not delete the objects) using clear().
Queues are useful for marshalling activities. For instance, if you've got a long list of items which need to be downloaded, rather than creating an instance of Downloader for each of them, you can have one Downloader and a queue. You can create a class which gets the next URL from the queue and downloads the data. Once it is complete, it can check the queue again for the next request.
There are some collections in MoSync which are a little more powerful, allowing you to access their contents through you own index. The basis for these is the Dictionary. Whilst you never create a Dictionary on its own, only classes derived from Dictionary they have a common syntax.
Dictionaries are collections of Pairs (you may know these also as Key/Value pairs). Each pair has a key with which you can reference your value. Often, you don't need to know about the pairs in the collection, but if you iterate through a Dictionary, then your iterator will be a pair.
To create a Dictionary, you need to create one of the derived classes, Map, HashMap or Set. They all follow the same pattern
Map<Key Type, Value Type> myMap; HashMap<Key Type, Value Type> myHashMap; Set<Key Type, Value Type> mySet;
For example, you can create a collection of the names of your friends and their phone numbers. Both their names and numbers will be stored as strings. The names will be the key and the phone number the value.
Map<String, String> myFriends;
You can then add items to the collection.
myFriends.insert("Rupert Bear", "Norwood 1212");The insert() method actually returns another Pair, this time with a Dictionary::Iterator and a boolean value. The iterator points to the value you've just added, and the boolean contains true if the insert was successful.
Note, unlike Vectors, there is no add method, because Dictionaries don't keep the same concepts of ordering.
Dictionary classes are all random-access, you can have access to any item at any time. We can find Rupert's phone number at any time. The find method returns a Pair<String, String>. The Pair has two properties for the key and value. Rather than being called key and value, they are called first and second. The key is in first, and the value is in second.
String& rupertsNumber = myFriends.find("Rupert Bear")->second;Map and HashMap also provide support for [] operators. This doesn't return the Pair but just the value.
String& rupertsNumber = myFriends["Rupert Bear"];
myFriends.erase("Rupert Bear");is valid. Note that the method is erase() and not remove() as it is on vectors and lists.
So, Dictionaries are power collections we can use very flexibly to store data. There are some differences between the three collections.
The Map is the simplest of the Dictionary classes. It is a simple mapping between the key and the value. For a given key, it will return the location of the value. It achieves this by comparing the key provided with its list of keys. It checks each one, and when it finds a match it will return the value. For this reason, Map is most suitable when the collection is small. With a very large collection, any search operation may have to compare every key in its collection until it finds the correct value. The elements in Map are sorted from lower to higher key values.
The HashMap converts the key you provide using a hash function. It then assigns the value into a location in memory depending on the value of the hash. This is important, as it can calculate this hash again when you want to retrieve the value. This means that it doesn't have to compare all of the keys looking for the value you want. It does mean that it does a little more work than a Map, but it is much more suitable for larger collections, e.g. collections which are likely to have more than five entries.
The Set is like a map, except that values are unique as well as keys. As the values are unique, then the storage is in the order of the values, and not the keys. This means that it is unlikely that when you iterate through a collection, that the values are in the same order as they were entered in. Sets are essential when having unique keys and unique values is essential. Set does not support the [] operator, so you have to use the .find() method to retrieve values. The keys in a Set are not hashed.
Dictionary Iterators cannot be unassigned, which makes iterating through Dictionaries quite verbose. There also isn't a handy macro like there is for vector. You have to either already have an Iterator or create one in the for statement.
for(Map<String, String>::Iterator itr = myFriends.begin();
itr != myFriends.end();
itr++)
{
// Do something.
}To create an iterator, you need to type it exactly as the Dictionary is typed, so if you've got
Map<String, String> myFriends;
Then the Iterator has a type of
Map<String, String>::Iterator
As described above, Iterators provide access to Pairs. You need to use the first and second properties on them for the key and value respectively.
for(Map<String, String>::Iterator itr = myFriends.begin();
itr != myFriends.end();
itr++)
{
lprintfln("Friend: %s Number: %s", itr->first.c_str(), itr->second.c_str());
}Below is code to create an manipulate a HashMap<String, String>. You will see how the order changes.
#include <MAUtil/Moblet.h>
#include <conprint.h>
#include <MAUtil/HashMap.h>
#include <MAUtil/String.h>
using namespace MAUtil;
class MyMoblet : public Moblet
{
public:
HashMap<String, String> myFriends;
MyMoblet()
{
// Add some friends
myFriends.insert("Rupert Bear", "Norwood 1212");
myFriends.insert("Noddy", "Playtown 2020");
myFriends.insert("Windy Miller", "Trumpton 2323");
// Show the original dictionary
showDictionary();
// Find a friend
String friendsNumber;
friendsNumber = myFriends.find("Rupert Bear")->second;
lprintfln("Rupert's number is %s", friendsNumber.c_str());
// Erase a friend
myFriends.erase("Noddy");
// Show the new dictionary
showDictionary();
// Find a friend by iterator
HashMap<String, String>::Iterator myFriend = myFriends.begin();
lprintfln("My first friend is %s whose number is %s",
myFriend->first.c_str(), myFriend->second.c_str());
}
void keyPressEvent(int keyCode, int nativeCode)
{
this->close();
}
void showDictionary()
{
lprintfln("I've got %d items", myFriends.size());
for(HashMap<String, String>::Iterator itr = myFriends.begin();
itr != myFriends.end();
itr++)
{
lprintfln("Friend: %s Number: %s", itr->first.c_str(),
itr->second.c_str());
}
}
};
/*
* Main program starts here.
*/
extern "C" int MAMain()
{
Moblet::run(new MyMoblet());
return 0;
};