汎用コンテナ

C++ の標準ライブラリの中で特によく使うのは何だろうかと考えてみると、それは入出力関係とコンテナだろうと思う。 そして C に入出力関数は有るがコンテナは無い。

C でプログラミングしているとハッシュテーブルやらリストやらを何度も書くはめになる。 充分に汎用性のある形で書くのは大変だ。

単相

まず様々な型に対応することは諦めて char* を格納するスタック構造を考えるとこんな風になる。

// stack.h
struct pair {
  char* str;
  struct pair* next;
};

typedef struct pair* stack;

void stack_push(stack* st, char* str);
char* stack_pop(stack* st);

// stack.c
#include <stdlib.h>
#include <stdio.h>
#include "stack.h"

void stack_push(stack* st, char* str) {
  struct pair* p = malloc(sizeof(struct pair));
  p->next = *st;
  p->str = str;
  *st = p;
}

char* stack_pop(stack* st) {
  if(*st) {
    char* p = (*st)->str;
    struct pair* next = (*st)->next;
    free(*st);
    *st = next;
    return p;
  }
  return NULL;
}

char* を格納することは問題なく出来る。

#include <stdio.h>
#include "stack.h"

int main(void) {
  stack st=NULL;
  stack_push(&st, "abc");
  stack_push(&st, "def");
  printf("%s\n", stack_pop(&st));
}

だがこれが他の型に対応したい場合にはどうすればいいのか。 いちいちライブラリを書き直すのだろうか。 ひとつのプログラム中で複数の型に対してスタックが必要になったら同じようなものをもうひとつ書くのか。

void*

すぐに思い付く解決策としては格納する要素の型をいっそ void* にしてしまうという方法が考えられる。

// stack.h
struct pair {
  void* str;
  struct pair* next;
};

typedef struct pair* stack;

void stack_push(stack* st, void* p);
void* stack_pop(stack* st);
||<

>|c|
// stack.c
#include <stdlib.h>
#include <stdio.h>
#include "stack.h"

void stack_push(stack* st, void* p) {
  struct pair* n = malloc(sizeof(struct pair));
  n->next = *st;
  n->str = p;
  *st = n;
}

void* stack_pop(stack* st) {
  if(*st) {
    void* p = (*st)->str;
    struct pair* next = (*st)->next;
    free(*st);
    *st = next;
    return p;
  }
  return NULL;
}

だがもちろん問題はある。 型を消してしまうのだから型の間違いがあっても捕捉されないのだ。

// test.c
#include <stdio.h>
#include "stack.h"

int main(void) {
  stack st=NULL;
  stack_push(&st, "abc");
  stack_push(&st, "def");
  printf("%s\n", stack_pop(&st));
  int* p = stack_pop(&st); // 型が間違っていても通っちゃう！
  printf("%d\n", *p);
}

ちなみに C++ では C よりも void* に関する暗黙の型変換ルールが厳しくなっているので陽にキャストをしないと警告が出るかもしれない。

マクロ

様々な型に対応したいが同じようなものを再度書くのは避けたいという要求を実現するためにはマクロが使える。 型をパラメータとして受け取り、関数を定義するようなマクロを作ればよいのだ。

// stack.h
#include <stdlib.h>

#define declare_stack_methods(value_type)                                 \
                                                                          \
struct pair_##value_type {                                                \
  value_type* str;                                                        \
  struct pair_##value_type* next;                                         \
};                                                                        \
                                                                          \
typedef struct pair_##value_type* stack_##value_type;                     \
                                                                          \
void stack_push_##value_type(stack_##value_type* st, value_type* p) {     \
  struct pair_##value_type* n = malloc(sizeof(struct pair_##value_type)); \
  n->next = *st;                                                          \
  n->str = p;                                                             \
  *st = n;                                                                \
}                                                                         \
                                                                          \
value_type* stack_pop_##value_type(stack_##value_type* st) {              \
  if(*st) {                                                               \
    void* p = (*st)->str;                                                 \
    struct pair_##value_type* next = (*st)->next;                         \
    free(*st);                                                            \
    *st = next;                                                           \
    return p;                                                             \
  }                                                                       \
  return NULL;                                                            \
}

複数の型に対応した関数群をひとつのマクロから生成することが出来て、もちろん型が誤っていればコンパイラが警告してくれる。

#include <stdio.h>
#include "stack.h"

declare_stack_methods(char)
declare_stack_methods(int)

int main(void) {
  stack_char stack1=NULL;
  stack_int stack2=NULL;
  stack_push_char(&stack1, "abc");
  stack_push_char(&stack1, "def");
  printf("%s\n", stack_pop_char(&stack1));
  int* p = stack_pop_char(&stack1); // 型の間違いを警告してくれる！

  stack_push_int(&stack2, &((int){2}));
  printf("%d\n", *stack_pop_int(&stack2));
}

しかし、問題点もある。 一般的なアーキテクチャでは char* と int* は同じサイズなので機械語レベルでは同じものになるであろうと考えられるにもかかわらずそれぞれ定義しているのだから実行可能プログラムの大きさは倍になる。 コンパイラの最適化が強力であればうまく統合してくれる可能性はあるものの、それをあてに出来ない環境では多用できない。

インターフェイスだけ分ける

上述の void* を使うバージョンで実装し、表層的なインターフェイス部分はマクロで生成するという方法がとれる。

// stack.h
struct pair {
  void* str;
  struct pair* next;
};

typedef struct pair* stack;

void stack_push(stack* st, void* p);
void* stack_pop(stack* st);

#define declare_stack_methods(value_type)                                    \
                                                                             \
struct pair_##value_type {                                                   \
  value_type* str;                                                           \
  struct pair_##value_type* next;                                            \
};                                                                           \
                                                                             \
typedef struct pair_##value_type* stack_##value_type;                        \
                                                                             \
inline void stack_push_##value_type(stack_##value_type* st, value_type* e) { \
  stack_push((stack*) st, e);                                                \
}                                                                            \
                                                                             \
inline value_type* stack_pop_##value_type(stack_##value_type* st) {          \
  return (value_type*) stack_pop((stack*) st);                               \
}

// stack.c
#include <stdlib.h>
#include <stdio.h>
#include "stack.h"

void stack_push(stack* st, void* p) {
  struct pair* n = malloc(sizeof(struct pair));
  n->next = *st;
  n->str = p;
  *st = n;
}

void* stack_pop(stack* st) {
  if(*st) {
    void* p = (*st)->str;
    struct pair* next = (*st)->next;
    free(*st);
    *st = next;
    return p;
  }
  return NULL;
}

実装は void* 版がただひとつであり、型の辻褄を合わせるためだけのインターフェイス関数は必要に応じてマクロで生成するというものである。 使い方は上述の場合とほぼ同じだ。

#include <stdio.h>
#include "stack.h"

declare_stack_methods(char)
declare_stack_methods(int)

int main(void) {
  stack_char stack1=NULL;
  stack_int stack2=NULL;
  stack_push_char(&stack1, "abc");
  stack_push_char(&stack1, "def");
  printf("%s\n", stack_pop_char(&stack1));
  int* p = stack_pop_char(&stack1); // 型の間違いを警告してくれる！

  stack_push_int(&stack2, &((int){2}));
  printf("%d\n", *stack_pop_int(&stack2));
}

今回はコンテナを汎用にする方法をいくつか考えたが、結局はどれも微妙に不格好だと思う。 C++ のテンプレートは実に有難いものだと認識するに至った。

Document ID: e10221e78f6843cd385c148e0accdcbd