W jaki sposób można przechowywać w tablicy mieszane typy danych (int, float, char itp.)?

145

Chcę przechowywać mieszane typy danych w tablicy. Jak można to zrobić?

chanzerre
źródło
8
Jest to możliwe i istnieją przypadki użycia, ale prawdopodobnie jest to wadliwy projekt. Nie do tego służą tablice.
djechlin

Odpowiedzi:

244

Elementy tablicy można uczynić unią rozłączną, znaną również jako unia oznaczona .

struct {
    enum { is_int, is_float, is_char } type;
    union {
        int ival;
        float fval;
        char cval;
    } val;
} my_array[10];

Element typeczłonkowski jest używany do przechowywania wyboru, który element członkowski unionma być używany dla każdego elementu tablicy. Więc jeśli chcesz przechowywać intw pierwszym elemencie, zrób:

my_array[0].type = is_int;
my_array[0].val.ival = 3;

Jeśli chcesz uzyskać dostęp do elementu tablicy, musisz najpierw sprawdzić typ, a następnie użyć odpowiedniego elementu członkowskiego unii. switchStwierdzenie jest przydatne:

switch (my_array[n].type) {
case is_int:
    // Do stuff for integer, using my_array[n].ival
    break;
case is_float:
    // Do stuff for float, using my_array[n].fval
    break;
case is_char:
    // Do stuff for char, using my_array[n].cvar
    break;
default:
    // Report an error, this shouldn't happen
}

Do programisty należy upewnienie się, że element typeczłonkowski zawsze odpowiada ostatniej wartości przechowywanej w pliku union.

Barmar
źródło
23
+1 Jest to konsekwencja wielu języków tłumaczeniowych napisanych w C
texasbruce
8
@texasbruce jest również nazywany „związkiem oznaczonym”. Używam tej techniki również w moim własnym języku. ;)
Wikipedia używa strony ujednoznaczniającej określenie „ związek dyskryminowany ” - „związek rozłączny” w teorii mnogości oraz, jak wspomniał @ H2CO3, „związek oznaczony” w informatyce.
Izkata
14
A pierwszy wiersz strony związku oznaczonego w Wikipedii mówi: W informatyce związek oznaczony, zwany także wariantem, zapisem wariantu, związkiem dyskryminowanym, związkiem rozłącznym lub typem sumy, ... Został wymyślony tak wiele razy, że ma wiele nazwy (takie jak słowniki, skróty, tablice asocjacyjne itp.).
Barmar
1
@Barmar Przepisałem to jako „tagged union”, ale potem przeczytałem Twój komentarz. Wycofałem edycję, nie chciałem niszczyć twojej odpowiedzi.
32

Użyj związku:

union {
    int ival;
    float fval;
    void *pval;
} array[10];

Będziesz jednak musiał śledzić rodzaj każdego elementu.


źródło
21

Elementy tablic muszą mieć ten sam rozmiar, dlatego nie jest to możliwe. Możesz obejść ten problem, tworząc typ wariantu :

#include <stdio.h>
#define SIZE 3

typedef enum __VarType {
  V_INT,
  V_CHAR,
  V_FLOAT,
} VarType;

typedef struct __Var {
  VarType type;
  union {
    int i;
    char c;
    float f;
  };
} Var;

void var_init_int(Var *v, int i) {
  v->type = V_INT;
  v->i = i;
}

void var_init_char(Var *v, char c) {
  v->type = V_CHAR;
  v->c = c;
}

void var_init_float(Var *v, float f) {
  v->type = V_FLOAT;
  v->f = f;
}

int main(int argc, char **argv) {

  Var v[SIZE];
  int i;

  var_init_int(&v[0], 10);
  var_init_char(&v[1], 'C');
  var_init_float(&v[2], 3.14);

  for( i = 0 ; i < SIZE ; i++ ) {
    switch( v[i].type ) {
      case V_INT  : printf("INT   %d\n", v[i].i); break;
      case V_CHAR : printf("CHAR  %c\n", v[i].c); break;
      case V_FLOAT: printf("FLOAT %f\n", v[i].f); break;
    }
  }

  return 0;
}

Wielkość elementu złącza to wielkość największego elementu, 4.


źródło
8

Istnieje inny styl definiowania unii znaczników (pod jakąkolwiek nazwą), który IMO sprawia, że ​​jest o wiele przyjemniejszy w użyciu , poprzez usunięcie unii wewnętrznej. Jest to styl używany w systemie X Window do rzeczy takich jak zdarzenia.

Przykład w odpowiedzi Barmara nadaje nazwę valunii wewnętrznej. Przykład w odpowiedzi Sp. Wykorzystuje anonimową sumę, aby uniknąć konieczności określania za .val.każdym razem, gdy uzyskujesz dostęp do rekordu wariantu. Niestety „anonimowe” wewnętrzne struktury i związki nie są dostępne w C89 ani C99. Jest to rozszerzenie kompilatora, a zatem z natury nieprzenośne.

Lepszym sposobem IMO jest odwrócenie całej definicji. Uczyń każdy typ danych własną strukturą i umieść tag (specyfikator typu) w każdej strukturze.

typedef struct {
    int tag;
    int val;
} integer;

typedef struct {
    int tag;
    float val;
} real;

Następnie zawijasz je w związek najwyższego poziomu.

typedef union {
    int tag;
    integer int_;
    real real_;
} record;

enum types { INVALID, INT, REAL };

Teraz może się wydawać, że się powtarzamy i tak jest . Ale weź pod uwagę, że ta definicja prawdopodobnie będzie izolowana do pojedynczego pliku. Ale wyeliminowaliśmy szum związany ze specyfikacją półproduktu, .val.zanim dotrzesz do danych.

record i;
i.tag = INT;
i.int_.val = 12;

record r;
r.tag = REAL;
r.real_.val = 57.0;

Zamiast tego trafia na koniec, gdzie jest mniej nieprzyjemny. :RE

Inną rzeczą, na którą to pozwala, jest forma dziedziczenia. Edycja: ta część nie jest standardową wersją C, ale używa rozszerzenia GNU.

if (r.tag == INT) {
    integer x = r;
    x.val = 36;
} else if (r.tag == REAL) {
    real x = r;
    x.val = 25.0;
}

integer g = { INT, 100 };
record rg = g;

Odlewanie w górę i w dół.


Edycja: Jedną rzeczą, o której należy pamiętać, jest konstruowanie jednego z nich za pomocą inicjatorów wyznaczonych przez C99. Wszystkie inicjatory członków powinny przechodzić przez tego samego członka unii.

record problem = { .tag = INT, .int_.val = 3 };

problem.tag; // may not be initialized

.tagInicjator może być ignorowane przez kompilatora, ponieważ .int_inicjatora, który następuje aliasy tym samym obszarze danych. Nawet jeśli mamy poznać układ (!), A to powinno być OK. Nie, nie jest. Zamiast tego użyj tagu „internal” (nakłada on tag zewnętrzny, tak jak chcemy, ale nie myli kompilatora).

record not_a_problem = { .int_.tag = INT, .int_.val = 3 };

not_a_problem.tag; // == INT
luser droog
źródło
.int_.valnie aliasuje jednak tego samego obszaru, ponieważ kompilator wie, że .valznajduje się on na większym przesunięciu niż .tag. Czy masz link do dalszej dyskusji na temat tego domniemanego problemu?
MM
5

Możesz zrobić void *tablicę, z oddzielną tablicą size_t.Ale tracisz typ informacji.
Jeśli chcesz w jakiś sposób zachować typ informacji, zachowaj trzecią tablicę int (gdzie int jest wartością wyliczoną) Następnie zakoduj funkcję, która rzutuje w zależności od enumwartości.

dzada
źródło
możesz również przechowywać informacje o typie w samym wskaźniku
phuclv
3

Unia to standardowa droga. Ale masz też inne rozwiązania. Jednym z nich jest tagged pointer , który obejmuje przechowywanie większej ilości informacji w „wolnych” bitach wskaźnika.

W zależności od architektur możesz użyć niskich lub wysokich bitów, ale najbezpieczniejszym i najbardziej przenośnym sposobem jest użycie nieużywanych niskich bitów , korzystając z wyrównanej pamięci. Na przykład w systemach 32-bitowych i 64-bitowych wskaźniki do intmuszą być wielokrotnościami 4 (zakładając, że intjest to typ 32-bitowy), a 2 najmniej znaczące bity muszą mieć wartość 0, dlatego możesz ich użyć do przechowywania typu twoich wartości . Oczywiście przed wyłuskiwaniem wskaźnika należy wyczyścić bity znacznika. Na przykład, jeśli twój typ danych jest ograniczony do 4 różnych typów, możesz go użyć jak poniżej

void* tp; // tagged pointer
enum { is_int, is_double, is_char_p, is_char } type;
// ...
uintptr_t addr = (uintptr_t)tp & ~0x03; // clear the 2 low bits in the pointer
switch ((uintptr_t)tp & 0x03)           // check the tag (2 low bits) for the type
{
case is_int:    // data is int
    printf("%d\n", *((int*)addr));
    break;
case is_double: // data is double
    printf("%f\n", *((double*)addr));
    break;
case is_char_p: // data is char*
    printf("%s\n", (char*)addr);
    break;
case is_char:   // data is char
    printf("%c\n", *((char*)addr));
    break;
}

Jeśli możesz upewnić się, że dane są wyrównane do 8 bajtów (jak w przypadku wskaźników w systemach 64-bitowych lub long longi uint64_t...), będziesz mieć jeszcze jeden bit na tag.

Ma to jedną wadę, że będziesz potrzebować więcej pamięci, jeśli dane nie były przechowywane w zmiennej gdzie indziej. Dlatego w przypadku, gdy typ i zakres danych jest ograniczony, możesz przechowywać wartości bezpośrednio we wskaźniku. Ta technika została użyta w 32-bitowej wersji silnika Chrome V8 , gdzie sprawdza najmniej znaczący bit adresu, aby sprawdzić, czy jest to wskaźnik do innego obiektu (np. Podwójne, duże liczby całkowite, ciąg lub jakiś obiekt), czy też 31 -bitowa wartość ze znakiem (nazywana smi- małą liczbą całkowitą ). Jeśli to jest int, Chrome po prostu wykonuje arytmetyczne przesunięcie w prawo o 1 bit, aby uzyskać wartość, w przeciwnym razie wskaźnik jest wyłuskiwany.


W większości obecnych systemów 64-bitowych wirtualna przestrzeń adresowa jest nadal znacznie węższa niż 64 bity, stąd najwyższe najbardziej znaczące bity mogą być również używane jako znaczniki . W zależności od architektury masz różne sposoby używania ich jako tagów. ARM , 68k i wiele innych można skonfigurować tak, aby ignorowały górne bity , co pozwala na swobodne ich używanie bez martwienia się o segfault lub cokolwiek. Z powyższego powiązanego artykułu w Wikipedii:

Istotnym przykładem użycia oznaczonych wskaźników jest środowisko uruchomieniowe Objective-C na iOS 7 na ARM64, szczególnie używane na iPhone 5S. W systemie iOS 7 adresy wirtualne mają 33 bity (wyrównane do bajtów), więc adresy wyrównane do słów używają tylko 30 bitów (3 najmniej znaczące bity to 0), pozostawiając 34 bity na tagi. Wskaźniki klasy Objective-C są wyrównane do słów, a pola znaczników są używane do wielu celów, takich jak przechowywanie liczby odwołań i określanie, czy obiekt ma destruktor.

Wczesne wersje systemu MacOS wykorzystywały oznaczone adresy zwane uchwytami do przechowywania odniesień do obiektów danych. Wysokie bity adresu wskazywały, czy obiekt danych był odpowiednio zablokowany, możliwy do usunięcia i / lub pochodził z pliku zasobów. Spowodowało to problemy ze zgodnością, gdy adresowanie MacOS wzrosło z 24 bitów do 32 bitów w Systemie 7.

https://en.wikipedia.org/wiki/Tagged_pointer#Examples

Na x86_64 nadal możesz ostrożnie używać wysokich bitów jako tagów . Oczywiście nie musisz używać wszystkich tych 16 bitów i możesz pominąć niektóre bity na przyszłość

We wcześniejszych wersjach Mozilla Firefox używali również małych optymalizacji całkowitoliczbowych, takich jak V8, z 3 małymi bitami używanymi do przechowywania typu (int, string, object ... itd.). Ale od czasu JägerMonkey wybrali inną ścieżkę ( nowa reprezentacja wartości JavaScript Mozilli , łącze zapasowe ). Wartość jest teraz zawsze przechowywana w 64-bitowej zmiennej o podwójnej precyzji. Gdy doublejest znormalizowany , można go użyć bezpośrednio w obliczeniach. Jeśli jednak wszystkie 16 bitów o wyższej wartości to 1s, co oznacza NaN , niższe 32 bity zapiszą adres (w komputerze 32-bitowym) do wartości lub wartości bezpośrednio, pozostałe 16 bitów zostanie użyte do przechowywania typu. Ta technika nazywa się boksem NaNlub nun-boxing. Jest również używany w 64-bitowym JavaScriptCore WebKit i SpiderMonkey Mozilli, a wskaźnik jest przechowywany w niskich 48 bitach. Jeśli głównym typem danych jest zmiennoprzecinkowy, jest to najlepsze rozwiązanie i zapewnia bardzo dobrą wydajność.

Przeczytaj więcej o powyższych technikach: https://wingolog.org/archives/2011/05/18/value-representation-in-javascript-implementations

phuclv
źródło