03 Лекция, intrusive контейнеры

(10.09.2022)

• 03 Лекция, intrusive контейнеры
  • Зачем

Зачем

В современном прграммировании доминирующие структуры данных - Вектора и Хеш-таблицы, про двухсвязные списки все забыли, но если мы посмотрим на ядро линукса, например, там доминирующая структура как раз списки, почему?

Допустим нам нужно хранить много обьектов в памяти:

• Список - без доступа к случайному элементу, разбросан по памяти
• Вектор - сложности с удалением, нужно найти сначала
• Хэш таблицы - ОК (но дорого)

В старкрафте все юниты храняться в двухсвязном списке
Статья

struct Unit
{
    Unit *prev;
    Unit *next;
    //...
    Unit *selected_prev; // для не select не испол
    Unit *selectrd_next;
    //...
};

Пример узла LRU кэша

struct Node
{
    Value value;
    Key key;
    
    // ordered by key
    Node *parent; // Можно как дерево
    Node *left;
    Node *right;
    
    // oredered by access time
    Node *next; // Можно как список
    Node *prev;
    
};

Можно выделить общий код:
C-style

struct List_element
{
    List_element *prev;
    List_element *next;
};

struct Unit
{
    List_element all_units_node;
    //...
    List_element selected_node;
    //...
};