AList – C++ 关联数组
以标准 C++ 的方式实现关联数组（字典）。
引言
本文介绍字典类型对象的标准 C++ 实现。这类特殊对象存在于其他编程语言中，如 Java、C# 以及 JavaScript、PHP、Lua 等脚本语言。STL 库中有一个字典对象的标准实现，称为 std::map。您也可以在 CodeProject 上找到另一个实现，但它使用 STL 的 std::vector 类。本文展示的实现根本不使用 STL。所有类都用标准的 C++ 语言编写，并且还添加了一些有用的扩展。
背景
字典作为一种数据类型非常有用，因为它们可以在基础容器中存储不同类型的值。有些技术将这类对象引入为基础对象，例如 Adobe 的 PDF 规范。PDF 文档中的所有对象都是字典对象。例如，您可以包含描述 Person 实体的不同数据，如姓名、年龄、出生日期，以及与其他父 Person 元素相关的其他 Person 实体等。XML 适用于收集这些信息，因为它可以包含整数、浮点数、字符串、布尔值或其他复杂数据类型。但在 C++ 中处理 XML 可能不像处理数组那么容易。
那么信息是如何存储在字典中的呢？它使用 **键值对** 来存储数据。**键** 是 **数据** 的唯一标识符。请参阅以下链接以了解有关关联数组或所谓的字典的一般讨论： http://en.wikipedia.org/wiki/Associative_array。
JavaScript 字典对象示例
在 JavaScript 中，可以使用 Array 或 Object 类将对象声明为字典类型对象，如下所示：
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;
因此，这基本上可以映射到以下 XML 片段：
<person>
<name>Jonny</name>
<age>32</age>
<male>true</male>
<boss>
<name>Anna</name>
<age>41</age>
<male>false</male>
</boss>
</person>
了解 STL 在 C++ 语言方面提供的功能非常有趣。
STL std::map 作为 C++ 字典实现示例
这是模板类 std::map 的声明。
map <key_type, value_type [, comparing_option [, memory_allocator] ] > map_name
它的用法如下：
std::map<std::string, std::string> person;
person["name"] = "Johny";
person["age"] = "32";
person["male"] = "true";
然后我们来到必须添加另一个 person 对象的部分，但正如您所见，使用当前的 person 类声明是不可能的。它被定义为使用 std::string 数据类型作为键，这没问题。但它也将 std::string 数据类型作为值，而这并不是我们所需要的，对吧？
如何解决这个问题？好吧，使用 std::map 类——没有办法从中逃脱。它实现了字典类型，但仅限于单层级对象。而且，值是相同的数据类型，这可能是一个问题。
AList 类作为简单的替代方案
在我开始处理这个问题时，我一直在思考字典对象的 JavaScript 实现。下面我提供了 AList 类的完整实现，因为它并不长。
#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
首先，有一个简单的 enum 定义，它涵盖了一些基本数据类型，如布尔值、数字和字符串等。还有两个附加数据类型：一个用于 AList 对象（对于嵌入式对象很重要），另一个用于任何数据类型的通用类对象（用户特定）。之后，定义了一个抽象的 _Generic 类。接下来，声明了通用的 item 字段，它会保存不同类型的值。它有两个重要的成员，可以通过 **索引** 和 **名称** 访问。
现在我们来到 ItemInfo 类的定义，它代表我们字典集合中的一个条目。它定义了接受不同数据类型的运算符，以及输出流运算符，这样您就可以在标准控制台输出上打印该值。
接下来定义的容器类是字典 AList 类。它也定义了标准运算符，以便您可以像使用简单数组（如 JavaScript 中）一样使用它。此类允许您将任何基本类型以及另一个 AList 对象或任何类型的对象放入容器中。这足以支持本文开头的示例。
如何使用
要使用它，您需要创建 AList 类的对象，并将它们连接在一起，如下所示：
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;
要在控制台输出上打印它，请参见下文：
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;
输出如下：
AList 和 ItemInfo 类接口
下面列出了 AList 类所有公共成员函数的简短列表。
// Clears the AList array
inline void empty();
// Gets the element using its index
inline ItemInfo& operator[] (const int index);
// Gets the element using its name
inline ItemInfo& operator[] (const char* name);
// Outputs AList array on the console window
friend inline ostream& operator << (ostream &stream, AList& ref);
// Gets the size of the AList array
inline int get_size();
// Gets the elements collection
inline ItemInfo** get_items();
这是 ItemInfo 类的公共接口。
// Assignment operator
inline ItemInfo& operator = (ItemInfo& ref);
// Assignment operator
inline ItemInfo& operator = (const bool& ref);
// Assignment operator
inline ItemInfo& operator = (const int& ref);
// Assignment operator
inline ItemInfo& operator = (const float& ref);
// Assignment operator
inline ItemInfo& operator = (const double& ref);
// Assignment operator
inline ItemInfo& operator = (const char* ref);
// Assignment operator
inline ItemInfo& operator = (_Generic* ref);
// Assignment operator
inline ItemInfo& operator = (void* ref);
// Outputs the element on the console window
friend inline ostream& operator << (ostream &stream, ItemInfo& ref);
// Gets the element using its index
ItemInfo& operator [] (const int index);
// Gets the element using its name
ItemInfo& operator [] (const char* name);
// Gets the index of the element
inline int get_index();
// Sets the index of the element
inline void set_index(const int index);
// Gets the name of the element
inline char* get_name();
// Sets the name of the element
inline void set_name(const char* name);
// Gets the type of the element
inline _ItemValueType get_type();
// Gets the value of the element
inline _ItemValueInfo get_value();
从 AList 元素中收集正确的值
这是容器中每个元素的默认值定义。
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;
要获取容器中元素的原始值，请执行以下操作：
// Gets the "name" as string
char* name = person["boss"]["name"].get_value().sValue;
// Gets the "age" as integer
int age = person["boss"]["age"].get_value().iValue;
// Gets the "male" as bool
bool male = person["boss"]["male"].get_value().bValue;
// Gets the "boss" subarray
AList& boss = (AList&)(*person["boss"].get_value().aValue);
// Gets "user-defined" object (if any)
MyObject* myObject = (MyObject*)(array["key"].get_value().oValue);
AList 与 std::map STL 类比较
这里的想法绝不是要取代 std::map STL 类。本文介绍的 AList 类并不像 std::map 那样实现高级数据存储结构（如 **哈希表**），也不像它那样对集合中的元素进行高级搜索。它只是在开发者的需求超出 std::map 类的字典实现时提供了一个选项，尤其是在处理 XML 文件或 PDF 文档等多层级问题时。
关注点
这是一个我一直以来都在研究的非常有趣的课题，我希望开发者能在他们的日常项目中找到它的用处。
历史
- AList 版本 1.0，2011 年 11 月。