リスト構造について

[カスタム]

はじめまして、カスタムと申します。
早速ですが質問させていただきます。

リスト構造についてです。
単刀直入に
大きさの違う要素をリストとしてつなげることは可能ですか？

リストにポインタを持たせてそのポインタはそれぞれ異なる別の型の構造体なりクラスを指す
のようなことはＣやＣ＋＋で実現可能なんでしょうか。

void型ポインタやテンプレートクラスなども考えてみましたが、どうもうまく考えがまとまりません。

あまり上手な表現法が見つからずこんな下手な質問になってしまい申し訳ありません。お忙しいとは思いますがぜひともご助言のほどよろしくお願いします。

[へろりくしょん]

可能ですよ。

というより割と使われてると思いますよ。

Ｃ＋＋の場合はよくは分かりませんが、Ｃの場合繋げる型の種類が決まっている場合は共用体を使うのが一般的じゃないでしょうか。

昔、Ｃ言語ライクなマクロ言語のコンパイラを作った時はそうしましたね。

[ISLe]

C++なら共通の親クラスを継承したクラスは、親クラス型のポインタに代入できます。
リストから親クラス型ポインタを取り出してメンバ関数を呼ぶときそれが仮想関数なら継承先のクラスでオーバーライドしたメンバ関数が呼ばれます。
オブジェクト指向ではポリモーフィズム(多態性)と呼ばれます。

#内部で共用体使ってサイズを合わせて固定サイズのメモリをやりくりすることもできます。

[dic]

可能です

私は純粋なＣを知りませんが
C/C++で、そのようなことが発生すると設計から考え直しますね

[カスタム]

解答ありがとうございます。

> Ｃ＋＋の場合はよくは分かりませんが、Ｃの場合繋げる型の種類が決まっている場合は共用体を使うのが一般的じゃないでしょうか。

ここ最近使ってなかったので共用体の存在をごっそり忘れてました(汗)
言われてみれば確かにその方法がありました
ただやっぱり変数名が変わってしまうところあたりはどんな数値が入ってるかっていうパラメータを持たせて、それによって分岐あたりで処理するしか対処方法はないですか…？


> C++なら共通の親クラスを継承したクラスは、親クラス型のポインタに代入できます。
> リストから親クラス型ポインタを取り出してメンバ関数を呼ぶときそれが仮想関数なら継承先のクラスでオーバーライドしたメンバ関数が呼ばれます。
> オブジェクト指向ではポリモーフィズム(多態性)と呼ばれます。
>
> #内部で共用体使ってサイズを合わせて固定サイズのメモリをやりくりすることもできます。

親クラス型のポインタだと子クラスで新しく宣言した変数や関数は確かスコープできなかった気がするんですが、なにか対処法などあったりしますか？
関数のほうは仮想関数を使用すれば何とかなると思うんですが。。。

[組木紙織]

Type Erasure かCRTPを使えば解決できると思います。(どちらも完全にはりかいできてないので思いつきですが、)
boost::anyを利用してあげてもいい気がします。
(これも結局Type Erasureかな。)

[たかぎ]

別のアプローチを示すために、あえて（C++ではなく）Cで考えると...

struct list_node
{
struct list_node *next;
};

struct foo { ... };
struct bar { ... };

struct foo_node
{
struct list_node node;
struct foo value;
};

struct bar_node
{
struct list_node node;
struct bar value;
};

struct int_node
{
struct list_node node;
int value;
};

このようにしておけば、どんな型でもリストに挿入することができます。
ノード単体を見て、どんな型の値を保持しているかを知るには、それを判別するためのメンバがもう一つ必要になります。

[へろりくしょん]

>このようにしておけば、どんな型でもリストに挿入することができます。

しかし、これだと struct list_node node; を必ず構造体の先頭のメンバにしなければいけませんね。
でなければ、常に(struct list_node*)へのキャストが必要です。

私ならば、struct list_node node; を構造体の先頭のメンバにし忘れる自信があります。
Ｃはポインタからポインタへのキャストは何も言ってくれませんから、ちょっと危険な気がします。

struct hoge_node{
    ...
    void *next;
};

と同じぐらい危険だと思うのですが。

struct list_node node; が必ず構造体の先頭のメンバに現れるような工夫が必要だと思います。
もしくは、先頭のメンバで無い場合エラーを起こすような工夫ですか。

でなければ、ちょっと使うにはためらってしまうデータ構造ですね。


＃私見ですので、怒らないでくださいね。

[ISLe]

> 私ならば、struct list_node node; を構造体の先頭のメンバにし忘れる自信があります。
> Ｃはポインタからポインタへのキャストは何も言ってくれませんから、ちょっと危険な気がします。

リスト構造そのものではないですけど、おおむかしにGUIシステム作ったときは、

struct component *button, *label;
label = create_component(LABEL);
set_caption(label, "ラベル");
set_position(label, 10, 20);
button = create_component(BUTTON);
set_caption(button, "OK");
set_position(button, 100, 20);
set_callback(button, button_callback);

という感じの使い方をするように設計してました。

struct component;
だけ公開して、利用する側はポインタで受け取ってそのまま渡すしかできないようにします。
ウインドウを閉じたら載ってるコンポーネントも破棄できるようにリスト構造での管理もしてました。

けっきょくクラスもどきですけど。

[ISLe]

> struct component;
> だけ公開して、利用する側はポインタで受け取ってそのまま渡すしかできないようにします。

create_componentは実際にはcomponent構造体を先頭に配置した別の構造体を作って返してて、利用する側はcomponent構造体としてしか認識させないという点がキモです。

[たかぎ]

> しかし、これだと struct list_node node; を必ず構造体の先頭のメンバにしなければいけませんね。
> でなければ、常に(struct list_node*)へのキャストが必要です。

そんなことはありません。

struct list_node *front;

struct foo_node node1;
front = &node1.node;

struct bar_node node2;
node2.node.next = front;
front = &node2.node;

のようにすればよいので、メンバーnodeの位置にかかわらず、同じシンタックスで記述することができます。
必要なら、それを利用したマクロを定義しておけば、型に依存しないAPIを提供することができます。

struct hoge_node
{
struct hoge value;
struct list_node node;
};

のように、nodeが先頭にない可能性を考慮して、

(struct hoge*)((char*)node - offsetof(struct hoge_node, node)

とすれば、valueを参照することができます。
これもマクロ化することが可能ですね。

型チェックを入れたければ、型情報のためのメンバを追加して、assertでも使えば診断できます。

[カスタム]

ちょっと留守にしている間にこんなにものご回答いただきありがとうございます


> C/C++で、そのようなことが発生すると設計から考え直しますね

まわりにいる人間にも同じようなことを言われました
自分なりに少し設計を考え直してみたいと思います



> Type Erasure かCRTPを使えば解決できると思います。(どちらも完全にはりかいできてないので思いつきですが、)
> boost::anyを利用してあげてもいい気がします。
> (これも結局Type Erasureかな。)

ちょっと調べてきました。
なんか少し複雑でしたが、大方は理解できた気がします。
使いこなすにはもうすこし勉強が必要になるかとおもいますが、いいアドバイスありがとうございます



>このようにしておけば、どんな型でもリストに挿入することができます。

そういう風につないでいけばリストにできるということは理解できました

自分の勉強不足で一から勉強しなおして来いと言われればそれまでなんですが、リストの先頭をさせたところで、後半のvalueをどうやって指せばいいかがわかりません。ポインタあたりの知識が特に不安でして...
わがままですがクラスも含めて考えたいのでちょっとＣ＋＋で失礼します。

typedef struct list_node
{
struct list_node *next;
};

class Test{
public:
Test(){a=b=1;};
~Test(){};
int a;
out(){std::cout << a << "+" << b << "=" << a+b << std::endl;};
private:
int b;
};

typedef struct Test_node
{
list_node node;
Test value;
};

int main(void){
list_node *front;
Test_node node1;
front = &node1.node;

Test_node node2;
node2.node.next = front;
node1.node = &node2.node;

//****データを参照する部分********
char *p = node1.node;
p + sizeof(list_node);
p->a = 2;
p->out();

return 0;
}

こんな感じになるんでしょうか（あってるかとても不安です）

[へろりくしょん]

>のように、nodeが先頭にない可能性を考慮して、

>(struct hoge*)((char*)node - offsetof(struct hoge_node, node)

>とすれば、valueを参照することができます。
>これもマクロ化することが可能ですね。

すみません。　こういったコードを書かない事を前提に話してました。
わざわざ構造体の先頭へのポインタ値を計算するというのがなんだかトリッキーな感じがして、
あまりスマートではないもので。

せっかくメンバ変数には名前が付いてるのですから、名前で呼んであげるのがメンバ変数への愛だと思っています。

[たかぎ]

> わざわざ構造体の先頭へのポインタ値を計算するというのがなんだかトリッキーな感じがして、
> あまりスマートではないもので。

C++だと、継承関係のあるクラス間の型変換では、コンパイラに任せられるだけでやっていることは同じです。
offsetofマクロというのはそもそもこういう使い方のためにあるものなので、トリッキーというわけでもないと思います。