Introduction
This article is about the standard C++ implementation of the dictionary type object. These special objects exist in other programming languages like Java,
C#, and scripting languages like JavaScript, PHP, Lua, etc. There is a standard implementation of the dictionary object inside the STL library, called
std::map. Another implementation can be found here on the CodeProject, but using the STL std::vector class.
The implementation shown in this article does not use STL at all. All classes are written in the standard C++ language, and also some useful extensions have been added.
Background
Dictionaries as data types are useful as they keep different types of values inside a basic container. Some technologies introduce this type of objects as basic
ones, like in Adobe's PDF specification. All objects inside the PDF document are dictionary objects. As an example, you could have different data describing
the Person entity like name, age, birth date, other Person entities that are in relation to the parent Person element, etc. XML is useful to collect these information
as there can be integers, floats, strings, booleans, or other complex data types. But working with XML in C++ might not be as easy as working with, let's say, arrays.
So how is information stored inside a dictionary? It uses key-value pairs to store data. The key is a unique identifier to the data.
Please see the following link for a general discussion considering associative arrays or, so called,
dictionaries: http://en.wikipedia.org/wiki/Associative_array.
JavaScript example of dictionary object
An object in JavaScript can be declared as a dictionary-type object using the Array or Object class, see below:
var person = new Array();
person.name = "Johny";
person.age = 32;
person.male = true;
person.boss = new Object();
person.boss["name"] = "Anna";
person.boss["age"] = 41;
person.boss["male"] = false;
So, this basically maps to the following XML segment:
<person>
<name>Jonny</name>
<age>32</age>
<male>true</male>
<boss>
<name>Anna</name>
<age>41</age>
<male>false</male>
</boss>
</person>
It is very interesting to see what STL has to offer when it comes to the C++ language.
STL std::map as an example of a C++ implementation of dictionary
This is a declaration of the template class std::map:
map <key_type, value_type [, comparing_option [, memory_allocator] ] > map_name
It can be used like this:
std::map<std::string, std::string> person;
person["name"] = "Johny";
person["age"] = "32";
person["male"] = "true";
Then we come to the part where we must add another person object, but as you can see, with the current declaration of the person class, it is impossible.
It is defined to use the std::string data type as the key, which is OK. But it also takes a std::string data type as the value, and that is not what we need, right?
How do we overcome this issue? Well, with the std::map class - no way out from here. It implements the dictionary type but only for single-level hierarchy objects.
Also, values are of the same data type, and this could be an issue.
AList class as a simple alternative
I was thinking about a JavaScript implementation of dictionary objects when I started to work on this issue. Below, I am giving the full implementation
of the AList class, since it is not too long:
#ifndef ALIST_H_INCLUDED
#define ALIST_H_INCLUDED
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <typeinfo>
using namespace std;
typedef enum __ItemValueType
{
IVT_NULL = 0,
IVT_BOOL = 1,
IVT_INT = 2,
IVT_FLOAT = 3,
IVT_DOUBLE = 4,
IVT_STRING = 5,
IVT_LIST = 6,
IVT_OBJECT = 7
} _ItemValueType;
class _Generic
{
public:
_Generic()
{
}
virtual ~_Generic()
{
}
protected:
virtual void Destroy() = 0;
};
typedef struct __ItemValueInfo
{
int index;
char* name;
_ItemValueType type;
union
{
bool bValue;
int iValue;
float fValue;
double eValue;
char* sValue;
_Generic* aValue;
void* oValue;
};
} _ItemValueInfo, *_lpItemValueInfo;
class ItemInfo : public _Generic
{
public:
ItemInfo()
{
memset(&m_value, 0, sizeof(_ItemValueInfo));
m_value.type = IVT_NULL;
m_value.index = -1;
}
ItemInfo(ItemInfo& ref)
{
m_value.type = ref.get_type();
switch (m_value.type)
{
case IVT_BOOL:
{
m_value.bValue = ref.get_value().bValue;
}
break;
case IVT_INT:
{
m_value.iValue = ref.get_value().iValue;
}
break;
case IVT_FLOAT:
{
m_value.fValue = ref.get_value().fValue;
}
break;
case IVT_DOUBLE:
{
m_value.eValue = ref.get_value().eValue;
}
break;
case IVT_STRING:
{
char* sValue = ref.get_value().sValue;
int len = strlen(sValue) + 1;
m_value.sValue = (char*)malloc(len);
strncpy(m_value.sValue, sValue, len-1);
m_value.sValue[len-1] = '\0';
}
break;
case IVT_LIST:
{
m_value.aValue = ref.get_value().aValue;
}
break;
case IVT_OBJECT:
{
m_value.oValue = ref.get_value().oValue;
}
break;
default:
{
memset(&m_value, 0, sizeof(_ItemValueInfo));
m_value.type = IVT_NULL;
}
break;
}
}
virtual ~ItemInfo()
{
free(m_value.name);
Destroy();
}
inline ItemInfo& operator = (ItemInfo& ref)
{
Destroy();
m_value.type = ref.get_type();
switch (m_value.type)
{
case IVT_BOOL:
{
m_value.bValue = ref.get_value().bValue;
}
break;
case IVT_INT:
{
m_value.iValue = ref.get_value().iValue;
}
break;
case IVT_FLOAT:
{
m_value.fValue = ref.get_value().fValue;
}
break;
case IVT_DOUBLE:
{
m_value.eValue = ref.get_value().eValue;
}
break;
case IVT_STRING:
{
char* sValue = ref.get_value().sValue;
int len = strlen(sValue) + 1;
m_value.sValue = (char*)malloc(len);
strncpy(m_value.sValue, sValue, len-1);
m_value.sValue[len-1] = '\0';
}
break;
case IVT_LIST:
{
m_value.aValue = ref.get_value().aValue;
}
break;
case IVT_OBJECT:
{
m_value.oValue = ref.get_value().oValue;
}
break;
default:
{
memset(&m_value, 0, sizeof(_ItemValueInfo));
m_value.type = IVT_NULL;
}
break;
}
return (*this);
}
inline ItemInfo& operator = (const bool& ref)
{
Destroy();
m_value.type = IVT_BOOL;
m_value.bValue = ref;
return (*this);
}
inline ItemInfo& operator = (const int& ref)
{
Destroy();
m_value.type = IVT_INT;
m_value.iValue = ref;
return (*this);
}
inline ItemInfo& operator = (const float& ref)
{
Destroy();
m_value.type = IVT_FLOAT;
m_value.fValue = ref;
return (*this);
}
inline ItemInfo& operator = (const double& ref)
{
Destroy();
m_value.type = IVT_DOUBLE;
m_value.eValue = ref;
return (*this);
}
inline ItemInfo& operator = (const char* ref)
{
Destroy();
m_value.type = IVT_STRING;
int len = strlen(ref) + 1;
m_value.sValue = (char*)malloc(len);
strncpy(m_value.sValue, ref, len-1);
m_value.sValue[len-1] = '\0';
return (*this);
}
inline ItemInfo& operator = (_Generic* ref)
{
Destroy();
m_value.type = IVT_LIST;
m_value.aValue = ref;
return (*this);
}
inline ItemInfo& operator = (void* ref)
{
Destroy();
m_value.type = IVT_OBJECT;
m_value.oValue = ref;
return (*this);
}
friend inline ostream& operator << (ostream &stream, ItemInfo& ref)
{
switch (ref.get_type())
{
case IVT_BOOL:
{
stream << ref.get_value().bValue;
}
break;
case IVT_INT:
{
stream << ref.get_value().iValue;
}
break;
case IVT_FLOAT:
{
stream << ref.get_value().fValue;
}
break;
case IVT_DOUBLE:
{
stream << ref.get_value().eValue;
}
break;
case IVT_STRING:
{
stream << ref.get_value().sValue;
}
break;
case IVT_LIST:
{
stream << "[List]";
}
break;
case IVT_OBJECT:
{
stream << "[Object]";
}
break;
default:
{
}
break;
}
return stream;
}
ItemInfo& operator [] (const int index);
ItemInfo& operator [] (const char* name);
inline int get_index()
{
return (m_value.index);
}
inline void set_index(const int index)
{
m_value.index = index;
}
inline char* get_name()
{
return (m_value.name);
}
inline void set_name(const char* name)
{
int len = strlen(name) + 1;
m_value.name = (char*)realloc(m_value.name, len*sizeof(char));
strcpy(m_value.name, name);
m_value.name[len-1] = '\0';
}
inline _ItemValueType get_type()
{
return (m_value.type);
}
inline _ItemValueInfo get_value()
{
return (m_value);
}
protected:
virtual void Destroy()
{
if (m_value.type == IVT_STRING)
{
free(m_value.sValue);
}
if (m_value.type == IVT_LIST)
{
delete (m_value.aValue);
}
m_value.type = IVT_NULL;
}
private:
_ItemValueInfo m_value;
};
class AList : public _Generic
{
public:
AList()
{
m_items = NULL;
m_size = 0;
}
virtual ~AList()
{
empty();
}
inline void empty()
{
Destroy();
}
inline ItemInfo& operator[] (const int index)
{
ItemInfo* pItem = find_item(index);
if (pItem != NULL)
{
return (*pItem);
}
else
{
m_size++;
m_items = (ItemInfo**)realloc(m_items, m_size*sizeof(ItemInfo*));
m_items[m_size-1] = new ItemInfo();
m_items[m_size-1]->set_index(index);
return (*(m_items[m_size-1]));
}
}
inline ItemInfo& operator[] (const char* name)
{
ItemInfo* pItem = find_item(name);
if (pItem != NULL)
{
return (*pItem);
}
else
{
m_size++;
m_items = (ItemInfo**)realloc(m_items, m_size*sizeof(ItemInfo*));
m_items[m_size-1] = new ItemInfo();
m_items[m_size-1]->set_name(name);
return (*(m_items[m_size-1]));
}
}
friend inline ostream& operator << (ostream &stream, AList& ref)
{
stream << "[List]";
return stream;
}
inline int get_size()
{
return m_size;
}
inline ItemInfo** get_items()
{
return m_items;
}
inline ItemInfo* find_item(const int index)
{
int iIndex = -1;
for (int i=0; i<m_size; i++)
{
if (m_items[i]->get_index() == index)
{
iIndex = i;
break;
}
}
if (iIndex != -1)
{
return (m_items[iIndex]);
}
else
{
return NULL;
}
}
inline ItemInfo* find_item(const char* name)
{
int iIndex = -1;
for (int i=0; i<m_size; i++)
{
if (strcmp(m_items[i]->get_name(), name) == 0)
{
iIndex = i;
break;
}
}
if (iIndex != -1)
{
return (m_items[iIndex]);
}
else
{
return NULL;
}
}
protected:
virtual void Destroy()
{
for (int i=0; i<m_size; i++)
{
delete m_items[i];
}
free(m_items);
m_size = 0;
}
private:
ItemInfo** m_items;
int m_size;
};
ItemInfo& ItemInfo::operator[] (const int index)
{
return (((AList&)(*m_value.aValue))[index]);
}
ItemInfo& ItemInfo::operator[] (const char* name)
{
return (((AList&)(*m_value.aValue))[name]);
}
#endif // ALIST_H_INCLUDED
First, there is a simple enum definition which covers some basic data types like booleans, numbers, and strings, etc. There are also two additional
data types: one for AList objects (important for embedded objects), and one for a general class object of any data type (user specific). After that,
an abstract _Generic class has been defined. Next, the general item field has been declared that keeps values of different types.
It has two important members that can be accessed by an index and a name.
Now we come to the definition of the ItemInfo class which represents an entry in our dictionary collection. It has defined operators to accept different
data types, and also the output stream operator so you can print the value on the standard console output.
The container class that is defined next is the dictionary AList class. It also has standard operators defined to work with it like you do with the simple
array (like in JavaScript). This class allows you to put any basic type inside the container, and also another AList object, or an object of any type.
This is enough to support the example from the beginning of this article.
How to use it
To use it, you need to create objects of the AList class, and join them together, see below:
AList person;
person["name"] = "John";
person["age"] = 32;
person["male"] = true;
person["boss"] = new AList();
person["boss"]["name"] = "Anna";
person["boss"]["age"] = 41;
person["boss"]["male"] = false;
To print it on the console output, see below:
cout << person["name"] << endl;
cout << person["age"] << endl;
cout << person["male"] << endl;
cout << person["boss"]["name"] << endl;
cout << person["boss"]["age"] << endl;
cout << person["boss"]["male"] << endl;
And, here is the output:
AList and ItemInfo class interface
Listed below is a short list of all the AList class public member functions:
inline void empty();
inline ItemInfo& operator[] (const int index);
inline ItemInfo& operator[] (const char* name);
friend inline ostream& operator << (ostream &stream, AList& ref);
inline int get_size();
inline ItemInfo** get_items();
And here is the public interface to the ItemInfo class:
inline ItemInfo& operator = (ItemInfo& ref);
inline ItemInfo& operator = (const bool& ref);
inline ItemInfo& operator = (const int& ref);
inline ItemInfo& operator = (const float& ref);
inline ItemInfo& operator = (const double& ref);
inline ItemInfo& operator = (const char* ref);
inline ItemInfo& operator = (_Generic* ref);
inline ItemInfo& operator = (void* ref);
friend inline ostream& operator << (ostream &stream, ItemInfo& ref);
ItemInfo& operator [] (const int index);
ItemInfo& operator [] (const char* name);
inline int get_index();
inline void set_index(const int index);
inline char* get_name();
inline void set_name(const char* name);
inline _ItemValueType get_type();
inline _ItemValueInfo get_value();
Collecting the correct value from an AList element
Here is the definition of the value for each element in the container:
typedef struct __ItemValueInfo
{
int index;
char* name;
_ItemValueType type;
union
{
bool bValue;
int iValue;
float fValue;
double eValue;
char* sValue;
_Generic* aValue;
void* oValue;
};
} _ItemValueInfo, *_lpItemValueInfo;
To get the original value from the element inside the container, do the following:
char* name = person["boss"]["name"].get_value().sValue;
int age = person["boss"]["age"].get_value().iValue;
bool male = person["boss"]["male"].get_value().bValue;
AList& boss = (AList&)(*person["boss"].get_value().aValue);
MyObject* myObject = (MyObject*)(array["key"].get_value().oValue);
AList compared to the std::map STL class
The idea here is not to replace the std::map STL class by any means. The AList class presented in this article does not implement advanced data storage
structures like hashtables, like std::map does, nor advanced searching through the elements of the collection. It just gives an option to the developer
when his needs exceed the dictionary implementation of the std::map class, especially in multi-hierarchy problems like in XML files or PDF documents.
Points of interest
This was a very interesting subject I have been working on, and I hope developers will find it a useful place in their everyday projects.
History
- AList version 1.0, November 2011.
