GLib fornece vários tipos contêineres para conjuntos de dados: GList
, GSList
, GPtrArray
e GArray
.
Foi uma prática comum no passado usar GList e, todas situações nas quais uma sequência ou conjunto de dados precisa ser armazenada(o). Isso não é recomendável — na maioria das situações, um GPtrArray deve ser usado. Ele faz menor uso de memória (um terço a metade de uma lista equivalente), melhora localidade de cache e a mesma ou menor complexidade algorítmica para todas as operações comuns. A única situação típica na qual um GList pode ser mais apropriado é ao lidar com dados ordenados, que requer inserções custosas em índices arbitrários no vetor.
Se listas vinculadas forem usadas, tenha o cuidado de manter baixa a complexidade das operações nelas, usando análise padrão de complexidade CS. Qualquer operação que usa g_list_nth()
ou g_list_nth_data()
está quase certamente errada. Por exemplo, interação por um GList deve ser implementada usando os ponteiros vinculantes, em vez de um índice incremental:
GList *some_list, *l;
for (l = some_list; l != NULL; l = l->next)
{
gpointer element_data = l->data;
/* Faz alguma coisa com @element_data. */
}
Usar um índice incremental pode resultar em um decréscimo quadrático no desempenho (O(N^2) em vez de O(N)):
GList *some_list;
guint i;
/* Esse código é ineficiente e não deve ser usado em produção. */
for (i = 0; i < g_list_length (some_list); i++)
{
gpointer element_data = g_list_nth_data (some_list, i);
/* Faz alguma coisa com @element_data. */
}
A penalidade no desempenho vem de g_list_length()
e de g_list_nth_data()
, os quais percorrem a lista (O(N)) para realizar suas operações.
Implementar o código acima com um GPtrArray tem a mesma complexidade que a primeira (correta) implementação de GList, mas com melhor localidade de cache e menor consumo de memória, de forma a executar melhor para grandes números de elementos:
GPtrArray *some_array;
guint i;
for (i = 0; i < some_array->len; i++)
{
gpointer element_data = some_array->pdata[i];
/* Faz alguma coisa com @element_data. */
}