テンプレートクラスの基礎の部分が分かりません。

Question

以下はある参考書で使用されているプログラムです。
テンプレートクラスの説明をしているのですが、一部説明がなく、ネットで検索しても出てこなかったのでこちらで質問させて頂きました。

以下の(あ)のコードが急に出てきて何を表しているのか具体的に分かりません。
テンプレートクラスのメンバ変数なら、「data_t next;」とすればいいはずなのに、listの型を使用しています。
そして(い)でもlist型の戻り値を返す関数を作成しています。
(う)(え)ではlist型でオブジェクトとポインタを宣言しています。
ただ、今まで出て来た参考書の説明では(う)(え)の「<char>」の部分は、data_tの型にしか掛かっていませんでした。
なので<char>は非公開メンバのdataか、公開メンバのgetdata()にしか掛かってないと思っていました。
ですがこのプログラムではnextや*getnext()にもかかっています。

ちょっと話が分かりにくいかもしれませんが、要は(あ)が何を表しているのか知りたいのです。
回答宜しくお願いします。

// 単純な汎用リンクリスト
#include <iostream>
using namespace std;

template <class data_t> class list {
data_t data;
list *next;　　　・・・・・・(あ)
public:
list(data_t d);
void add(list *node) {node->next = this; next = 0; }
list *getnext() { return next; }　　　・・・・・(い)
data_t getdata() { return data; }
};

template <class data_t> list<data_t>::list(data_t d)
{
data = d;
next = 0;
}

int main()
{
list<char> start('a'); 　　　　・・・・・・(う)
list<char> *p, *last;　　　　　・・・・・・(え)
int i;

// リストを作成する
last = &start;

for(i=1; i<26; i++) {
p = new list<char> ('a' + i);
p->add(last);
last = p;
}

// リストを追跡する
p = &start;

while(p) {
cout << p->getdata();
p = p->getnext();　　　　　　　・・・・・・(お)
}
cout << "\n";

return 0;
}

Answer 1

テンプレートは全く関係ありませんね。
リスト構造が理解できていないだけです。

リストとは、データに次のデータの位置を付け加えて、データをつないでいくもの
だと思っていますね。
'a'、'b'、'c' をつなぎたい。
'a' というデータに、次の 'b' の位置を付け加える。
'b' というデータに、次の 'c' の位置を付け加える。
'c' というデータに、次のデータはないので 0 を付け加える。

データの型は char。次のデータの位置は char *。だから、

class list {
	char data;
	char *next;
}

でいいじゃないか。

なぜ、char *next; でなく list *next; でないといけないのか？
という質問ですね。

先頭の start に 'a' というデータと 'b'の位置が入っているとすれば、
start.next が char * だから、*start.next で 'b' というデータは取り出せます。

ところが、'b' というデータ自身からは、'c' の位置が入っている next を
取り出せません。

start.next が list* だったら、*start.next が
「'b' と 'c' の位置が入っている list という箱」になるので、
(*start.next).data で 'b' が取り出せ、
(*start.next).next で 'c' の位置が取り出せます。
(*start.next).data は start.next->data、
(*start.next).next は start.next->next と書けます。

p = &start; で p は 「'a' と 'b' の位置」の両方が入った箱を指します。
p->getdata() は p->data であり 'a' です。　
p->getnext() は p->next であり、'b' の位置です。
p = p->getnext() で p は 「'b' と 'c' の位置」の両方が入った箱を指します。

だから、next は　char * ではなく、list * でなければならないのです。

もう一度繰り返します。
class list を、「データと次のデータの位置が入った箱」にしたくても、実際には
「データと次の箱の位置が入った箱」でないと、データを順に取り出すことができないのです。

Comments

[iwanami]

回答ありがとうございます。
自分の分からない所を的確にまとめてくださりありがとうございます。
漠然と想像していたリスト構造を具体的に教えてくださり助かりました。

Answer 2

data_t *nextと書くところを

そんな謎の思い込みは捨ててください

data_tが例えばintだったとして

int data;
int* next;

だったらリストにならないでしょう。

Comments

[iwanami]

回答ありがとうございます。
そこが曖昧かもしれません。
僕はその形でもリストは出来ると思っているのですが、*next　はオブジェクト自身の(言い方が適切ではないかもしれませんが)クラス型でないと、リストは出来ないのでしょうか。

[ozwk]

nextの型がint(のポインタ)だったら
nextのnextが存在しないじゃないですか
それだとリストじゃなくてただの値を2つメンバに持つ型です

[iwanami]

>>1つ目の回答に関して
ozwkさんが言っていた事について考えていたのですが、このプログラムの start や p、last　と言ったポインタは確かにchar型だと成り立たないですね。
それでlist自身のクラスの型で宣言しているとすると、少し分かった気がします。

>>2つ目の回答に関して
（時間差で返信にズレを生じさせてしまいましたが。）
確かにそれだと next はただint型 の値を指しているポインタに過ぎないですね。

Answer 3

まずリスト構造、ここでは単方向リストがどんな構造か理解していますか?
(単方向)リストは複数の要素を数珠つなぎにしたデータ構造です。
件の list<data_t> は数珠つなぎにされた一つ一つの数珠玉を表現しています。

この数珠玉は

• 数珠玉に納められた要素: data_t data;
• 次の数珠玉を指すポインタ: list *next;　

がそのメンバとして用意されています。
data_t getdata() で要素(の値)を返し、
list *getnext() が次の数珠玉(へのポインタ)を返します。

[追記] list<char> をそれと等価な list_of_char に置き換えました。
これでわからんとしたら、templateがわからんわけじゃない。

typedef char data_t;

class list_of_char {
  data_t data;
  list_of_char *next; // ・・・・・・(あ)
public:
  list_of_char(data_t d);
  void add(list_of_char *node) {node->next = this; next = 0; } // nodeの次にthisをつなぐ
  list_of_char *getnext() { return next; } // ・・・・・(い)
  data_t getdata() { return data; }
}; 

list_of_char::list_of_char(data_t d) {
  data = d;
  next = 0;
} 

#include <iostream>
using namespace std;

int main() {
  list_of_char start('a'); // ・・・・・・(う)
  list_of_char *p, *last;  // ・・・・・・(え)
  int i; 
  // リストを作成する
  last = &start; 
  for(i=1; i<26; i++) {
    p = new list_of_char('a' + i);
    p->add(last);
    last = p;
  } 
  // リストを追跡する
  p = &start;

  while(p) {
    cout << p->getdata();
    p = p->getnext(); // ・・・・・・(お)
  }
  cout << "\n"; 
  return 0;
}

Comments

[iwanami]

回答ありがとうございます。
リストの流れに関しては、手こずりましたが一応理解出来ていると思います。
テンプレートになって型が流動的になったので、少し理解しづらい所もありましたが、一応理解出来ていると思います。

[episteme]

ならば何が疑問なんです?

[iwanami]

(あ)が何を表しているのか知りたいです。
今までの参考書の説明だと、data_t *next;と書く所を、list *next;と書いてるのが分かりませんでした。
SaitoAtsushiさんの回答で、list *next;はlist<data_t> *next;の省略だという事を知って、自分なりに考えてみたんですが、ポインタの時にlist *next;と記述するのかと思っているのですが。

[episteme]

struct list_of_int { // intを保持する数珠玉
int data; // この数珠玉が保持するデータ
list_of_int* next; // 次の数珠玉へのポインタ
};
ならわかります?

[iwanami]

分からないです。
コンストラクタがクラス名と同じ名前の関数を使うので、それと似たようなものなのかと思っていますが。

[episteme]

追記しました。

[iwanami]

追記確認しました。
これはテンプレート構造を抜かしたリスト構造ですよね。
これを見るとテンプレート関係なくリスト構造が理解出来ていなかったのが分かります。
epistemeさんは最初からこの事を指摘していたんですね。

Answer 4

list *next; という宣言は list<data_t> *next; と書いた場合と同じです。 あるクラステンプレートの定義の中にそのクラステンプレート自身と同じ名前が現れた場合には型引数を省略できるというルールがあります。

data_t *next; ではなく list *next; であるのは、リスト (より詳しく言うなら片方向の連結リスト) というのはそういうものだとしか言いようがないのでリストのデータ構造について調べてみてください。 Wikipedia などに詳しい説明があります。

ここで定義している list というクラスはこれがリスト全体なわけではなくてリストのノードひとつを表しているということを念頭に置いて考えると分かりやすいかと思います。

Comments

[iwanami]

回答ありがとうございます。
>>list *next; という宣言は list<data_t> *next; と書いた場合と同じです。 あるクラステンプレートの定義の中にそのクラステンプレート自身と同じ名前が現れた場合には型引数を省略できるというルールがあります。
これは初めて知りました。知れて良よかったです。ありがとうございます。

>>data_t *next; ではなく list *next; であるのは、リスト (より詳しく言うなら片方向の連結リスト) というのはそういうものだとしか言いようがないのでリストのデータ構造について調べてみてください。 Wikipedia などに詳しい説明があります。
てきとうではなく何か理由があるんですね。自分なりに調べてみたんですが、ポインタだと
list *next　と宣言するのではないかと思っているんですが。

>>ここで定義している list というクラスはこれがリスト全体なわけではなくてリストのノードひとつを表しているということを念頭に置いて考えると分かりやすいかと思います。
一応リストの処理の流れは理解しているつもりです。今までは型が固定されたポインタでしたが、テンプレートになって、型が流動的になったので、ちょっと捉えにくいという所はありましたが、処理の流れは理解しているつもりです。

Answer 5

皆様回答ありがとうございました。
どの回答も助かりましたが、次に見に来る人の事を考えて、問題点とリスト構造の仕組みを具体的に書き出してくれたkazuma-sさんにベストアンサーを付けたいと思います。