数据结构

GLib 包含许多基本数据结构，如数组、链表、哈希表、队列、树等。

数组

GLib 数组 (GArray) 类似于标准 C 数组，但它们在添加元素时会自动增长。

数组元素可以是任何大小（尽管一个数组中的所有元素都是相同的大小），而且该数组可以自动清除为“0”并以零结尾。

要创建一个新的数组，请使用 g_array_new()。

要在数组中添加元素，最坏情况为 O(n)，请使用 g_array_append_val()、g_array_append_vals()、g_array_prepend_val()、g_array_prepend_vals()、g_array_insert_val() 和 g_array_insert_vals()。

要在 O(1) 中访问数组的一个元素（读取或写入该元素），请使用 g_array_index()。

要设置数组的大小，请使用 g_array_set_size()。

要释放一个数组，请使用 g_array_unref() 或 g_array_free()。

所有排序函数内部都会调用快速排序（或类似的）函数，该函数的平均成本为 O(n log(n))，最坏情况成本为 O(n^2)。

这里有一个示例，它将整数存储在一个 GArray 中

GArray *array;
int i;

// We create a new array to store int values.
// We don't want it zero-terminated or cleared to 0's.
array = g_array_new (FALSE, FALSE, sizeof (int));

for (i = 0; i < 10000; i++)
  {
    g_array_append_val (array, i);
  }

for (i = 0; i < 10000; i++)
  {
    if (g_array_index (array, int, i) != i)
      g_print ("ERROR: got %d instead of %d\n",
               g_array_index (array, int, i), i);
  }

g_array_free (array, TRUE);

指针数组

指针数组 (GPtrArray) 类似于数组，但仅用于存储指针。

如果您从数组中删除元素，数组末尾的元素会移动到之前被删除元素占用的空间中。这意味着您不应该依赖于特定元素的索引保持不变。在遍历数组时删除元素时也应小心。

要创建一个指针数组，请使用 g_ptr_array_new()。

要向指针数组中添加元素，请使用 g_ptr_array_add()。

要从指针数组中删除元素，请使用 g_ptr_array_remove()、g_ptr_array_remove_index() 或 g_ptr_array_remove_index_fast()。

要访问指针数组的一个元素，请使用 g_ptr_array_index()。

要设置指针数组的大小，请使用 g_ptr_array_set_size()。

要释放指针数组，请使用 g_ptr_array_unref() 或 g_ptr_array_free()。

一个使用 GPtrArray 的示例

GPtrArray *array;
char *string1 = "one";
char *string2 = "two";
char *string3 = "three";

array = g_ptr_array_new ();
g_ptr_array_add (array, (gpointer) string1);
g_ptr_array_add (array, (gpointer) string2);
g_ptr_array_add (array, (gpointer) string3);

if (g_ptr_array_index (array, 0) != (gpointer) string1)
  g_print ("ERROR: got %p instead of %p\n",
           g_ptr_array_index (array, 0), string1);

g_ptr_array_free (array, TRUE);

字节数组

GByteArray 是一个可变的字节数组，基于 GArray，用于提供在添加元素时自动增长的字节数组。

要创建一个新的 GByteArray，请使用 g_byte_array_new()。

要向 GByteArray 中添加元素，请使用 g_byte_array_append() 和 g_byte_array_prepend()。

要设置 GByteArray 的大小，请使用 g_byte_array_set_size()。

要释放 GByteArray，请使用 g_byte_array_unref() 或 g_byte_array_free()。

使用 GByteArray 的示例

GByteArray *array;
int i;

array = g_byte_array_new ();
for (i = 0; i < 10000; i++)
  {
    g_byte_array_append (array, (guint8*) "abcd", 4);
  }

for (i = 0; i < 10000; i++)
  {
    g_assert (array->data[4*i] == 'a');
    g_assert (array->data[4*i+1] == 'b');
    g_assert (array->data[4*i+2] == 'c');
    g_assert (array->data[4*i+3] == 'd');
  }

g_byte_array_free (array, TRUE);

如果您对表示字节序列的不可变对象感兴趣，请参见 GBytes。

单链表

GSList 结构及其关联函数提供标准单链表数据结构。此数据结构的优点是在复杂度 O(1) 中提供插入/删除操作，而在复杂度 O(n) 中提供访问/搜索操作。而比 GList（双链表）的优点是它们在空间中更轻巧，因为它们只需要保留一个指针，但它将最差情况下的访问/搜索成本增加了一倍。

列表中的每个元素都包含一段数据，以及一个指向列表中下一个元素的指针。使用此指针可以仅在一个方向上移动列表（不同于双链表，允许在两个方向上移动）。

每个元素中包含的数据可以是整数（使用类型转换宏），或者只是指向任何类型的数据的指针。

请注意，大多数 GSList 函数希望传递指向列表中第一个元素的指针。插入元素的函数会返回列表的新开始，而这有可能已改变。

没有用于创建 GSList 的函数。NULL 被视为空列表，因此您只需将 `GSList*` 设置为 `NULL`。

要添加元素，请使用 g_slist_append() 、 g_slist_prepend() 、 g_slist_insert() 和 g_slist_insert_sorted() 。

要删除元素，请使用 g_slist_remove() 。

要查找列表中的元素，请使用 g_slist_last() 、 g_slist_next() 、 g_slist_nth() 、 g_slist_nth_data() 、 g_slist_find() 和 g_slist_find_custom() 。

要查找一个元素的索引，请使用 g_slist_position() 和 g_slist_index() 。

要对列表中每个元素调用一个函数，请使用 g_slist_foreach() 。

要释放整个列表，请使用 g_slist_free() 。

双链表

GList 结构及其关联函数提供标准双链表数据结构。此数据结构的优点是在复杂度 O(1) 中提供插入/删除操作，而在复杂度 O(n) 中提供访问/搜索操作。而比 GList（双链表）的优点是它们在空间中更轻巧，因为它们只需要保留一个指针，但它将最差情况下的访问/搜索成本增加了一倍。

列表中的每个元素都包含一段数据，以及指向列表中原先和下一个元素的指针。使用这些指针可以仅在一个方向上移动列表（不同于GSList，允许在两个方向上移动）。

双链表不跟踪项的数量，也不跟踪列表的开始和结尾。如果您想要快速访问列表的开始和结尾，和/或列表中的项的数量，请使用 GQueue 。

每个元素中包含的数据可以是整数（使用类型转换宏），或者只是指向任何类型的数据的指针。

请注意，大多数 GList 函数期望接收分配给列表中第一个元素的指针。插入元素的函数将返回列表的新的开始位置，该位置可能发生改变。

没有用于创建 GList 的函数。NULL 被视为一个有效的空列表，因此您只需将一个 GList* 设置为 NULL 即可进行初始化。

要添加元素，请使用 g_list_append()、g_list_prepend()、g_list_insert() 和 g_list_insert_sorted()。

要访问列表中的所有元素，请遍历列表

GList *l;
for (l = list; l != NULL; l = l->next)
  {
    // do something with l->data
  }

要为列表中的每个元素调用一个函数，请使用 g_list_foreach()。

要遍历列表并修改它（例如删除某个元素），while 循环更合适，例如

GList *l = list;
while (l != NULL)
  {
    GList *next = l->next;
    if (should_be_removed (l))
      {
        // possibly free l->data
        list = g_list_delete_link (list, l);
      }
    l = next;
  }

要移除元素，使用 g_list_remove()。

要在列表中导航，请使用 g_list_first()、g_list_last()、g_list_next()、g_list_previous()。

要在列表中查找元素，请使用 g_list_nth()、g_list_nth_data()、g_list_find() 和 g_list_find_custom()。

要查找元素的索引，请使用 g_list_position() 和 g_list_index()。

要释放整个列表，请使用 g_list_free() 或 g_list_free_full()。

散列表

一个 GHashTable 提供了键值关联，经过优化后，在提供键的情况下，可以以摊销时间复杂度 O(1) 找到、插入或删除关联值。遍历所有元素的所有操作均花费 O(n) 的时间（列出所有键/值、表大小调整等）。

请注意，在将键或值插入到 GHashTable 中时，它们都不会被复制，因此它们在 GHashTable 的整个生命期内都必须存在。这意味着可以使用静态字符串 OK，但应先使用 g_strdup() 复制临时字符串（即在缓冲区中创建的字符串和 GTK 小部件返回的字符串），然后再插入。

如果动态分配了键或值，则在从 GHashTable 中移除它们以及在用新插入项覆盖它们时，都必须小心地确保将其释放。同样，不建议在 GHashTable 中混合静态字符串和动态分配的字符串，因为此时很难确定是否应该释放该字符串。

要创建 GHashTable，请使用 g_hash_table_new()。

要在 GHashTable 中插入键值，请使用 g_hash_table_insert()。

要查找与指定键相对应的值，请使用 g_hash_table_lookup() 或 g_hash_table_lookup_extended()。

g_hash_table_lookup_extended() 也可以用于简单地检查散列表中是否存在键。

要移除键和值，请使用 g_hash_table_remove()。

要为每个键/值对调用函数，请使用 g_hash_table_foreach()，或使用迭代器迭代哈希表中的键/值对，请参阅 GHashTableIter。哈希表的迭代顺序是未定义的，您不得依赖以与插入时相同的顺序迭代键/值。

要销毁 GHashTable，请使用 g_hash_table_unref() 或 g_hash_table_destroy()。

哈希表的一个常见用例是存储有关一组键的信息，而不与每个键关联任何具体值。GHashTable 优化了一种执行此操作的方法：如果您仅存储键 == 值的键/值对，则 GHashTable 不会分配内存来存储这些值，如果您的集合很大，这将节省大量的空间。函数 g_hash_table_add() 和 g_hash_table_contains() 的设计目的是在此方式使用 GHashTable 时使用。

GHashTable 并非设计为静态初始化为编译时已知的键和值。要生成静态哈希表，请使用诸如此类的工具 gperf。

双端队列

GQueue 结构及其关联函数提供了一个标准队列数据结构。在内部，GQueue 使用与 GList 相同的数据结构以相同的复杂性存储元素，包括插入/删除（O(1)）和访问/搜索（O(n)）操作。

每个元素中包含的数据可以是整数（使用类型转换宏），或者只是指向任何类型的数据的指针。

与所有其他 GLib 数据结构一样，GQueue 不是线程安全的。对于线程安全队列，请使用 GAsyncQueue。

要创建一个新 GQueue，请使用 g_queue_new()。

要初始化一个静态分配的 GQueue，请使用 G_QUEUE_INIT 或 g_queue_init()。

要添加元素，请使用 g_queue_push_head()、g_queue_push_head_link()、g_queue_push_tail() 和 g_queue_push_tail_link()。

要移除元素，请使用 g_queue_pop_head() 和 g_queue_pop_tail()。

要释放整个队列，请使用 g_queue_free()。

异步队列

您通常需要在不同的线程之间进行通信。一般而言，最好不要通过共享内存来执行此操作，而采用显式信息传递方式。对于多线程应用程序来说，这些消息仅仅是异步的，因为同步操作完全可以在同一线程中执行。

异步队列与大多数其他 GLib 数据结构不同，因为它们可以被多个线程同时使用，而无需显式锁定，并且它们带有自己的内置引用计数。这是因为异步队列的本质在于，它始终至少被 2 个并发线程使用。

要使用异步队列，首先必须用 g_async_queue_new()创建一个队列。 GAsyncQueue结构是按引用计数的，使用 g_async_queue_ref()和 g_async_queue_unref()管理引用。

要向队列发送消息的线程只需调用 g_async_queue_push()将消息推送到队列中即可。

要从异步队列中接收消息的线程只需对该队列调用 g_async_queue_pop()即可。如果此时队列中没有可用的消息，则该线程将进入休眠状态，直到有消息到达。消息将从队列中移除并返回。函数 g_async_queue_try_pop()和 g_async_queue_timeout_pop()可用分别于仅检查消息是否存在或仅等待某个时间段的消息。

对于几乎每个函数，都有两个变体，一个锁定队列，另一个不锁定队列。这样，你可以持有队列锁（用 g_async_queue_lock()获取它，用 g_async_queue_unlock()释放它），使用多条访问队列的指令。这对于确保队列的完整性是必要的，但只应在真正需要时使用，因为如果使用不当，可能会让你的工作变得更难。通常情况下，你只需要使用锁定函数变体（没有_unlocked后缀的那些变体）。

在许多情况下，当你需要将工作分配给一组工作线程时，使用 GThreadPool可能比手动使用 GAsyncQueue更方便。GThreadPool在内部使用一个 GAsyncQueue。

二叉树

GTree结构及其关联函数提供了一个经过排序的重要/值对集，该集合已针对搜索和按顺序遍历进行了优化。这意味着对于 GTree中的大多数操作（访问、搜索、插入、删除等），其时间复杂性在平均情况下为 O(log(n))，在最坏情况下为 O(n)。但是，请注意，维护一个包含 n 个元素的平衡排序的 GTree需要 O(n log(n))时间。

要创建一个新的 GTree，请使用 g_tree_new()。

要插入 GTree中的一个键/值对，请使用 g_tree_insert()（O(n log(n))）。

要删除一个键/值对，请使用 g_tree_remove()（O(n log(n))）。

要查找对应于给定键的值，请使用 g_tree_lookup()和 g_tree_lookup_extended()。

要找出 GTree中的节点数目，请使用 g_tree_nnodes()。要获得 GTree的高度，请使用 g_tree_height()。

要遍历 GTree，对遍历中访问的每个节点调用一个函数，请使用 g_tree_foreach()。

要销毁一个 GTree，请使用 g_tree_destroy()。

N 元树

GNode结构及其关联函数提供了一个N元树数据结构，其中该树中的节点可以包含任意数据。

要创建一个新树，请使用 g_node_new()。

要将一个节点插入树，请使用 g_node_insert()、g_node_insert_before()、g_node_append() 和 g_node_prepend()。

要创建一个新节点并将其插入树中，请使用 g_node_insert_data()、g_node_insert_data_after()、g_node_insert_data_before()、g_node_append_data() 和 g_node_prepend_data()。

要反转节点的子节点，请使用 g_node_reverse_children()。

要查找节点，请使用 g_node_get_root()、g_node_find()、g_node_find_child()、g_node_child_index()、g_node_child_position()、g_node_first_child()、g_node_last_child()、g_node_nth_child()、g_node_first_sibling()、g_node_prev_sibling()、g_node_next_sibling() 或 g_node_last_sibling()。

要获取有关节点或树的信息，请使用 G_NODE_IS_LEAF()、G_NODE_IS_ROOT()、g_node_depth()、g_node_n_nodes()、g_node_n_children()、g_node_is_ancestor() 或 g_node_max_height()。

要遍历树，为遍历中访问的每个节点调用一个函数，请使用 g_node_traverse() 或 g_node_children_foreach()。

要从树中删除节点或子树，请使用 g_node_unlink() 或 g_node_destroy()。

可扩展列表

GSequence 数据结构具有列表的 API，但内部使用平衡二叉树实现。这意味着 GSequence 上的大多数操作（访问、搜索、插入、删除等）在平均情况下时间复杂度为 O(log(n))，在最坏情况下为 O(n)。但是，请注意，维护一组 n 个元素的经过平衡的排序列表，需要时间 O(n log(n))。每个元素中包含的数据可以是整型值，方法是使用类型转换宏，或者仅指向任何类型数据的指针。

通过“迭代器”访问 GSequence，这些迭代器由 GSequenceIter 表示。迭代器表示序列中两个元素之间的位置。例如，“开头”迭代器表示序列第一个元素之前的间隙，而“结尾”迭代器表示最后一个元素之后的间隙。在空序列中，开头迭代器和结尾迭代器相同。

GSequence 的某些方法对项目范围进行操作。例如，g_sequence_foreach_range() 会对具有给定范围的每个元素调用用户指定函数。该范围由传入迭代器表示的间隙分隔，因此，如果你传入开头迭代器和结尾迭代器，那么所讨论的范围就是整个序列。

函数 g_sequence_get() 与迭代器一起使用，以访问紧跟在迭代器表示的间隙之后的元素。据说迭代器“指向”该元素。

迭代器在它对 GSequence 的大多数操作中都是稳定的。例如，一个迭代器指向序列的某个元素，即使是在序列排序之后，它也会继续指向该元素。甚至用例如 g_sequence_move_range() 将元素移到另一个序列中，也不会使指向它的迭代器失效。使迭代器失效的唯一操作是当它所指向的元素从任何序列中移除时。

要对数据进行排序，可以使用 g_sequence_insert_sorted() 或 g_sequence_insert_sorted_iter() 将数据添加到 GSequence 中，或者，如果你想添加大量数据，更有效率的做法是在无序插入后调用 g_sequence_sort() 或 g_sequence_sort_iter()。

引用计数字符串

引用计数字符串是指已经用引用计数增强以管理它们的资源的正常 C 字符串。你可以分配一个新的引用计数字符串，并根据需要获取和释放引用，而不是在调用者之间复制字符串；当该字符串上的最后一个引用被释放时，分配给它的资源将被释放。

通常，引用计数字符串可以在从文件中解析数据并将它们存储到传输给各种调用者的数据结构中时使用。

PersonDetails *
person_details_from_data (const char *data)
{
  // Use g_autoptr() to simplify error cases
  g_autoptr(GRefString) full_name = NULL;
  g_autoptr(GRefString) address =  NULL;
  g_autoptr(GRefString) city = NULL;
  g_autoptr(GRefString) state = NULL;
  g_autoptr(GRefString) zip_code = NULL;

  // parse_person_details() is defined elsewhere; returns refcounted strings
  if (!parse_person_details (data, &full_name, &address, &city, &state, &zip_code))
    return NULL;

  if (!validate_zip_code (zip_code))
    return NULL;

  // add_address_to_cache() and add_full_name_to_cache() are defined
  // elsewhere; they add strings to various caches, using refcounted
  // strings to avoid copying data over and over again
  add_address_to_cache (address, city, state, zip_code);
  add_full_name_to_cache (full_name);

  // person_details_new() is defined elsewhere; it takes a reference
  // on each string
  PersonDetails *res = person_details_new (full_name,
                                           address,
                                           city,
                                           state,
                                           zip_code);

  return res;
}

在上面的示例中，我们有多个函数采用相同的字符串用于不同的用途；使用典型 C 字符串时，我们必须在数据的生命周期规则与从原始缓冲区解析字符串的生命周期不同时复制字符串。使用引用计数字符串时，每个调用者都可以引用数据，并尽可能长时间地拥有字符串。

引用计数字符串还可以“保存在”由 GLib 拥有的全局表格中；当保存在内的字符串至少有一个引用时，用相同内容创建一个新的保存在内的引用计数字符串将返回现有字符串的引用，而不是创建一个新的引用计数字符串实例。一旦字符串丢失其最后一个引用，它将从保存在内的字符串全局表中自动移除。

引用计数字符串已在 GLib 2.58 中添加。