C/C++ Tagged/Discriminated Union

Организация и обновление метаданных объединения для программного использования и доступа

Эта статья основана на темах, представленных здесь: https://medium.com/@almtechhub/c-c-self-referential-recursive-unions-22b334493eaa

Задний план

Если вы знакомы с объединениями в C/C++, то вы, вероятно, знаете, что сами по себе объединения не являются надежными структурами данных, особенно в C++, где доступ к неустановленным свойствам является неопределенным поведением. По этой причине в компьютерных науках существует давняя концепция, известная как теговые объединения.

Проще говоря, помеченные объединения — это объединения, с которыми связан фрагмент данных, отслеживающий, какие из потенциальных свойств объединения установлены в данный момент. В C++ вы можете выбирать между структурами и классами для инкапсуляции объединения или разрабатывать собственное решение для базы данных (например, карту). Конечный вариант использования, который я имею в виду, довольно прост, поэтому я собираюсь использовать структуры.

Простой пример

#include <iostream>
union vals {
  char ch;
  int nt;
};
struct tagUnion {
  char tag;
  vals val;
};
int main() {
  tagUnion tu;
  tu.tag = 'i';
  tu.val.nt = 21;
  for(int i = 0; i < 5; i++) {
    if(tu.tag == 'i') {
      std::cout << tu.val.nt << std::endl;
      tu.tag = 'c';
      tu.val.ch = 'A';
      continue;
    }
    if(tu.tag == 'c') {
      std::cout << tu.val.ch << std::endl;
      tu.tag = 'i';
      tu.val.ch = i;
      continue;
    }
  }
}

В этом примере у нас есть простое объединение, которое содержит char и int. Это объединение заключено в структуру, которая имеет переменную char и экземпляр объединения. Мы используем одну букву char для обозначения каждого типа, либо i, либо c. В main мы инициализируем объединение с тегами, а затем зацикливаемся. На каждой итерации мы проверяем, какое свойство установлено, регистрируем значение, переворачиваем тег и устанавливаем связанное свойство. Результат его запуска:

Это ожидаемый результат, мы успешно создали объединение с тегами и использовали его простым программным способом. Теперь давайте вернемся к примеру с самореферентным союзом из прошлой статьи.

Самореферентный тегированный союз

Если мы применим уроки этой статьи к примеру рекурсивного объединения из предыдущей статьи, вы получите что-то вроде:

union test {
  test * next;
  int val;
};
enum tagType { link, value };
struct taggedTest {
  tagType typ;
  test    val;
};

Однако, если мы используем эту настройку, когда мы обращаемся к taggestTest.val.next, мы указываем на другое объединение и не имеем нашего тега. Вместо этого нам нужно, чтобы объединение ссылалось на структуру taggedTest, поэтому мы используем предварительное объявление. Вот полный пример с простым тестом:

#include <iostream>
struct taggedTest;
union test {
  taggedTest * next;
  int val;
};
enum tagType { link, value };
struct taggedTest {
  tagType typ;
  test    val;
};
int main() {
  taggedTest test1;
  taggedTest test2;
  taggedTest test3;
  taggedTest test4;
  taggedTest test5;
  
  test5.val.val = 2;
  test5.typ = value;
  test4.val.next = &test5;
  test4.typ = link;
  test3.val.next = &test4;
  test3.typ = link;
  test2.val.next = &test3;
  test2.typ = link;
  test1.val.next = &test2;
  test1.typ = link;
  taggedTest * tmpTT = &test1;
  int i = 1;
  while(true) {
    if(tmpTT->typ == link) {
      tmpTT = tmpTT->val.next;
      std::cout << "Crossing Link: " << i++ << std::endl;
    } else if(tmpTT->typ == value) {
      std::cout << tmpTT->val.val << std::endl;
      break;
    }
  }
}

Вывод

Объединения имеют сомнительную ценность без отслеживания того, какое свойство активно. Это меньше беспокоит в C, который поддерживает каламбур типов, но в C++ доступ к неактивным свойствам является неопределенным поведением. Распространенным решением этой проблемы являются помеченные/размеченные объединения, которые в C++ достигаются с использованием классов или структур. Поскольку мой конечный вариант использования прост, я решил использовать структуры.

Теговые объединения довольно просты в реализации, но в сочетании с рекурсивными объединениями возникают дополнительные сложности. Когда нам нужны самоссылающиеся тегированные объединения, мы должны предварительно объявить нашу структуру и использовать указатель на структуру в качестве следующего типа в объединении.

C/C++ Tagged/Discriminated Union