- 1 名前：デフォルトの名無しさん mailto:sage [04/11/25 21:11:32]
- C++ のジェネリックプログラミングの話をしましょう。
以下のスレッドを統合するスレです。
STLスレッド
Part1 pc.2ch.net/tech/kako/1004/10042/1004287394.html
Part2 pc3.2ch.net/tech/kako/1026/10267/1026793823.html
【C++】Boost使い集まれ！
pc3.2ch.net/test/read.cgi/tech/1033830935/ (html化待ち?)
Generic Programming with C++ Template
pc.2ch.net/tech/kako/1008/10085/1008593126.html
【C++】template 統合スレ -- STL/Boost/Loki, etc.
pc2.2ch.net/tech/kako/1037/10377/1037795348.html
【C++】template 統合スレ -- Part2
pc2.2ch.net/test/read.cgi/tech/1047978546/ (html化待ち)
【C++】template 統合スレ -- Part3
pc5.2ch.net/test/read.cgi/tech/1066493064/ (html化待ち)
【C++】template 統合スレ -- Part4
pc5.2ch.net/test/read.cgi/tech/1083550483/ (html化待ち)
【C++】template 統合スレ -- Part5
pc5.2ch.net/test/read.cgi/tech/1091522597/
関連スレ、その他リンクは >>2-5 あたりに。
- 511 名前：デフォルトの名無しさん mailto:sage [2005/05/15(日) 22:32:53 ]
- ん？これでできてるっぽいぞ。
template<> A::A( int b);
- 512 名前：デフォルトの名無しさん mailto:sage [2005/05/15(日) 23:29:21 ]
- >>511
あれ？本当だね。という事は、template <>の構文がちゃんとメンバテンプレート
に適用されているみたいだね。俺の勘では、明示的特殊化になってなくて、単なる
オーバーロードのような気もするが・・・・
- 513 名前：デフォルトの名無しさん mailto:sage [2005/05/15(日) 23:36:57 ]
- もう少し規格票をよく読んでみる・・・・・
>>508はそしたら違う事に関してなのかな。
- 514 名前：デフォルトの名無しさん mailto:sage [2005/05/15(日) 23:41:09 ]
- >>511
しかし、そのコードは構文的に正しいとは言えないですよね。
謎だ。
- 515 名前：デフォルトの名無しさん mailto:sage [2005/05/15(日) 23:41:17 ]
- 特殊化とインスタンス化とを混同してない？
- 516 名前：デフォルトの名無しさん mailto:sage [2005/05/15(日) 23:55:33 ]
- >508が示したように、コンストラクタテンプレートに対して
テンプレート引数を明示する方法は無い。
しかし、（メンバ）関数テンプレートの特殊化を宣言する再には、
テンプレート引数を明示しなくても、関数引数の型から
テンプレート引数の推測が働く。
>>514
明示的特殊化の構文は
template<> delcaration
だから、>511は構文的に正しいと言える。
- 517 名前：デフォルトの名無しさん mailto:sage [2005/05/15(日) 23:58:48 ]
- 構文的には確かに正しいのだけれど、もともとの506の要求は
明示的インスタンス化（≠明示的特殊化）なわけで・・・
- 518 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 00:02:05 ]
- 勉強になった。
- 519 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 00:08:01 ]
- >>517
それがどうした？
明示的インスタンス化の構文は
template declaration
だ。あとは同じ。
- 520 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 00:12:53 ]
- >>519
すまんすまん。それでVC++7.1で通ったよ。
- 521 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 00:15:29 ]
- コンパイラに「これこれのテンプレートをT型でインスタンス化しますた」
とレポートするスイッチがあればいいのに
- 522 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 00:17:31 ]
- 実体化の位置を決定するルールは結構複雑だからな。
- 523 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 00:59:29 ]
- おまえらの必死さに笑った。
C++の中途半端なtemplate機能でメンテ不能の駄作を量産してる様は、
まるでVBで汎用ライブラリを作る馬鹿とそっくりだな。
- 524 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 01:03:16 ]
- C++知らないのに、知ってる振りして
がんばって煽るアンタもそうとう必死だが
- 525 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 01:35:46 ]
- むしろC++で駄目なのは
テンプレートじゃなくてコンストラクタ
- 526 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 01:47:19 ]
- >>525
コンストラクタの何が不満だって？
- 527 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 02:48:50 ]
- 純粋なOO言語と比べると
C++のOOは不完全
- 528 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 03:05:21 ]
- >>526
class A
{
int a;
public:
A( int a_ ) : a(a_){;}
};
class B : A
{
public:
B(){ int a = 略; A::A(a);}
B( int a ) : B(){;}
};
- 529 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 03:16:11 ]
- 何がしたいのか理解に苦しむ。C++について理解しているとは思えないコードだ。
- 530 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 03:30:52 ]
- >>529
これが出来ないから嫌だなと。
＞B(){ int a = 略; A::A(a);}
これはAに突っ込む引数aを
Bのコンストラクタ内で生成したい時。
C++ではAのコンストラクタは、Bの初期化リストにしか
置けないので複雑なロジックは難しい。
＞B( int a ) : B(){;}
これは多重定義したコンストラクタから
デフォのコンストラクタを予呼びたい時。
デフォのコンストラクタに生成時にかならず呼ばれる
初期化コードを収める。
これが出来ないと全てのコンストラクタに
同じ初期化コードを書かなければならない。
- 531 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 04:43:03 ]
- >>530
最初の：AはBの基底クラス。最初にAが構築されなきゃBが構築できない。
2番目の：B() {Init();} B(int a) {Init();hogehoge(a);}
- 532 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 08:55:21 ]
- 最初のは
static int hoge() {return 略}
B() : A(hoge()) {}
とかすれば。
- 533 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 09:05:50 ]
- >>530
そういうことか。
ではどうしたらいいと思う？
Dは両方いけるんだっけか？
- 534 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 09:06:24 ]
- >>531
> Aが構築されなきゃBが構築できない
関係ない。
> Init()
Init() の中に初期化リストが書けない。
- 535 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 09:07:23 ]
- >>532
hoge() の値を初期化リストで２度使いたくなったらやっぱり困るな。
「略」が軽くて副作用がなければ、２回呼び出すんだろうけど。
- 536 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 09:10:37 ]
- 要は設計が悪いんだろ。
- 537 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 09:18:31 ]
- まあそうだな。C++の設計の悪さは今更いかんともしがたい部分がある。
- 538 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 11:19:33 ]
- >>530
> C++ではAのコンストラクタは、Bの初期化リストにしか
> 置けないので複雑なロジックは難しい。
コンストラクタの途中でexceptionが起きたことを考えると、
>>532のような方法で初期化リストを旨く使う方法に頭を悩ませるのが良い。
>>528のやり方ではコンストラクト失敗時のデストラクトの扱いがかなり難しくなる。
初期化リストで上手くできない場合は、
exception safeの事を考えるとコンストラクタ自体がかなり複雑になってしまう。
- 539 名前：>>538 mailto:sage [2005/05/16(月) 11:21:07 ]
- 定義順じゃなくて、初期化リスト記述順だといいのになあと思ったことはある。
- 540 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 12:06:24 ]
- >>539
それだと、コンストラクタごとに初期化順が変わってしまう。
Ex.
class foo {
public:
foo() : a_(), b_() {}
foo(int a) : b_(a), a_(a) {}
...;
};
- 541 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 12:21:40 ]
- >>540
539はまさにそれを意図しているのだと思うが、何か不都合があるの?
- 542 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 12:53:52 ]
- >>541
初期化リストに載ってないメンバはどうすればいい? by コンパイラ
- 543 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 13:14:10 ]
- くるしゅうない。よきにはからえ。
- 544 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 13:17:59 ]
- 構築した順番の逆順で解体することを保証しなきゃならんので
コンストラクタごとに初期化順が変わったら大変だ。
- 545 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 14:05:33 ]
- なるほど。それもそうだ。
- 546 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 15:32:47 ]
- つーか藻前らEffectiveC++くらい読んどけよ。
- 547 名前：デフォルトの名無しさん [2005/05/16(月) 20:25:46 ]
- template< uint n > class X
{
public:
void f(...);
}
こういうクラスがあったとして、
nが1だった場合 → X::f( uint f0 );
nが2だった場合 → X::f( uint f0, uint f1 );
nが3だった場合 → X::f( uint f0, uint f1, uint f2 );
こういうふうにテンプレート引数によって
関数の引数の数が変わるようにしたいんですが可能ですか？
出来ないまでも、代替手段みたいなのはありますか？
- 548 名前：デフォルトの名無しさん [2005/05/16(月) 20:53:37 ]
- あの〜
templateって実はマクロ？
- 549 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 21:23:34 ]
- >>547
関数のデフォルト引数でなんとかしろ。同一のテンプレートパラメータの型を
持つクラスは２回以上は定義できん。
- 550 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 21:58:37 ]
- >>549
了解、こういうのも出来るといいですね。
- 551 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 22:15:27 ]
- いやだから、ディフォルト引き数で何が不満なんだ?
- 552 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 22:22:47 ]
- それぞれ特殊化で可能じゃない？もちろんそうするのが良いか悪いかは別。
- 553 名前：デフォルトの名無しさん [2005/05/16(月) 22:26:17 ]
- >>551
例えばベクトルクラスがあります。
template< uint n >class vector;
これをインスタンス化したい場合、こういうふうに書きたいんです。
vector<2> v2 = vector<2>(5,1);
vector<3> v3 = vector<3>(5,1,6);
vector<4> v4 = vector<4>(5,1,6,3);
vector<5> v5 = vector<5>(5,1,6,3,9);
vector<100> v100 = vector<100>(5,1,6,3,9,5,1,6,3,9, 5,1,6,3,9,5,1,6,3,9, 5,1,6,3,9,5,1,6,3,9, 5,1,6,3,9,5,1,6,3,9, 5,1,6,3,9,5,1,6,3,9, 5,1,6,3,9,5,1,6,3,9, 5,1,6,3,9,5,1,6,3,9, 5,1,6,3,9,5,1,6,3,9, 5,1,6,3,9,5,1,6,3,9, 5,1,6,3,9,5,1,6,3,9);
自然な欲求だと思います。
- 554 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 22:31:08 ]
- >>553
そういう時のためのstd::vectorではないかと思うのだが・・・・
- 555 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 22:34:16 ]
- static const uint initialValues[] = {5, 1, 6, 3, 9,};
std::vector<uint> v5 = std::vector<uint>(initailValues, initialValues + sizeof(initialValues) / sizeof(*initialValues));
- 556 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 22:34:58 ]
- その例なら
配列を初期化して、std::vectorにぶち込めばいいじゃん
どうしてもやりたいならBOOST_PPで特殊化
- 557 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 23:09:19 ]
- 部分特殊化。以降略。なんか馬鹿みてえ。
#include <iostream>
#include <cstddef>
template <std::size_t N, typename T = int>
class vec {
T a[N];
public:
vec(T i) {
a[0] = i;
std::cout << a[0] << std::endl;
}
};
template <typename T>
class vec<2, T>
{
T a[2];
public:
vec(T i, T j) {
a[0] = i; a[1] = j;
std::cout << a[0] << ' ' << a[1] << std::endl;
}
};
int main()
{
vec<1> v1 = vec<1>(5);
vec<2> v2 = vec<2>(5,1);
}
- 558 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 23:21:18 ]
- 特殊化はイヤというか面倒くさすぎるから、普通はこんなカンジだろうね
template<uint Dim> class vector {
double *const coord;
public:
vector(double x) : coord(new double[sizeof(char[Dim == 1]) * Dim])
{ coord[0] = x; }
vector(double x, double y) : coord(new double[sizeof(char[Dim == 2]) * Dim])
{ coord[0] = x; coord[1] = y; }
vector(double x, double y, double z) : coord(new double[sizeof(char[Dim == 3]) * Dim])
{ coord[0] = x; coord[1] = y; coord[2] = z; }
};
int main() {
vector<1> v(1);
vector<1> v1(1, 2); // error
vector<2> v2(1, 2);
vector<2> vv2(1); // error
vector<3> v3(1, 2, 3);
}
- 559 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 23:24:56 ]
- やはりコンストラクタのオーバーロードに落ち着くか。
- 560 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 23:25:18 ]
- >>
そうするまでもなく
普通に多重定義でいいと思うよ。
template <std::size_t N, typename T = int>
class vec {
T a[N];
public:
vec( T x, T y)
{
if( N > 0 )a[0] = x;
if( N > 1 )a[1] = y;
}
vec( T x, T y, T z)
{
if( N > 0 )a[0] = x;
if( N > 1 )a[1] = y;
if( N > 2 )a[2] = z;
}
};
- 561 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 23:27:04 ]
- ちなみに、 sizeof(char[Dim == 1]) ってのは、
Dim == 1 のときは、1 で、そうでなければ、コンパイルエラーね
- 562 名前：デフォルトの名無しさん mailto:sage [2005/05/16(月) 23:59:25 ]
- どうも読みにくいので、直した
template<unsigned Dim> class vector {
double coord[Dim];
public:
vector(double x) {
sizeof(char[Dim == 1]); // Dim == 1 でなければエラー
coord[0] = x;
}
vector(double x, double y) {
sizeof(char[Dim == 2]); // Dim == 3 でなければエラー
coord[0] = x; coord[1] = y;
}
vector(double x, double y, double z) {
sizeof(char[Dim == 3]); // Dim == 3 でなければエラー
coord[0] = x; coord[1] = y; coord[2] = z;
}
};
int main() {
vector<1> v(1);
vector<1> v1(1, 2); // コンパイルエラー
vector<2> v2(1, 2);
vector<2> vv2(1); // コンパイルエラー
vector<3> v3(1, 2, 3);
}
- 563 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 02:55:12 ]
- おまえらの必死さに笑った。
C++の中途半端なtemplate機能でメンテ不能の駄作を量産してる様は、
まるでVBで汎用ライブラリを作る馬鹿とそっくりだな。
- 564 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 02:57:49 ]
- ×メンテ不能
○俺に理解不能
- 565 名前：デフォルトの名無しさん [2005/05/17(火) 07:37:28 ]
- あーあ、4,5,6って別々にするわけ？テンプレの意味ねー
- 566 名前：デフォルトの名無しさん [2005/05/17(火) 07:41:46 ]
- テンプレートはマクロ
www.iba.k.u-tokyo.ac.jp/〜yanai/template_tips.html
- 567 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 10:05:48 ]
- >>563
まあ同意。boostとか見てても思うが、言語使用の範囲内でどうにかしようとするから無理が出てくる。
パズルとしては興味深いが、無理やりやってるからどうしてもキモくなる。
新しいプリプロセッサ作ったほうがマシな気がする。
- 568 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 12:24:00 ]
- >>566
典型的なアホっぽいが。
exportはComeauでサポートされていることすら知らんようだし。
- 569 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 12:40:07 ]
- >>566
> まず最も重要な事実は、templateはマクロであるということである。
そもそも、始めの仮定についてキチンと論証してない時点でアウトだな。
- 570 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 13:16:28 ]
- templateはマクロだよ。
マクロと聞いてCやC++のプリプロセッサ(やVBAなどアプリケーション内のスクリ
プティング言語)しか思いつかない人に向けた文章ではなかろ。
- 571 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 14:01:12 ]
- >ここではオブジェクト指向に則ったよいtemplateの使い方を模索する。
この時点で道を誤っている気が。
- 572 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 14:29:53 ]
- templateの明示的インスタンス化なんて、少し考えれば
使い道などろくに無い機能だとわかるだろうに
しかも使う必要も無い機能だし
それにこだわってる時点で、ダメだなそのページ
- 573 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 18:56:42 ]
- ネタをまじめに叩くなよ
- 574 名前：デフォルトの名無しさん [2005/05/17(火) 20:39:55 ]
- ねたじゃねーし
templateはコンパイルする前に展開されるからマクロなの
- 575 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 20:42:50 ]
- コンパイルする前に展開しちゃったら
タイプセーフは無理じゃないの？
- 576 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 20:47:38 ]
- いいよわからん奴は無理に使うな
- 577 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 21:03:14 ]
- マクロで使える構文を限定的にして型を認識させたのがテンプレート
- 578 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 21:12:28 ]
- みんな好き勝手に「マクロ」の意味を定義して使ってるから、話が噛み合わない
だけでしょ。
- 579 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 21:56:51 ]
- おっと、ここで578が正式にマクロの定義とやらを教えてくれるらしいぞ
- 580 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 22:03:42 ]
- なにこの意味不明な反応
- 581 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 22:21:02 ]
- 付き合うだけ無駄でつ
- 582 名前：デフォルトの名無しさん [2005/05/18(水) 07:21:54 ]
- 普通のマクロでも引数の数を変えられるようなことはできないから
>>553
- 583 名前：デフォルトの名無しさん mailto:sage [2005/05/20(金) 00:28:48 ]
- VC7.1で
std::list<int>使うとポインタの保存のためか
std::vector<int>の3倍近いメモリ使うんだが、
省メモリな実装のlistって無理なのかな？
- 584 名前：デフォルトの名無しさん mailto:sage [2005/05/20(金) 00:55:57 ]
- >>583
SGI STLのstd::slistなら、一方向リストだけど、少しでも少ないかも。
- 585 名前：デフォルトの名無しさん mailto:sage [2005/05/20(金) 01:45:41 ]
- リストすら作りを理解してないのかよ。
- 586 名前：デフォルトの名無しさん mailto:sage [2005/05/20(金) 12:25:58 ]
- std::vectorのresizeコストが気になるようならstd:;dequeとか
- 587 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 00:07:18 ]
- つうか双方向リストは最低2つはポインタが必要なんだから当たり前の気がするんだが
- 588 名前：583 mailto:sage [2005/05/21(土) 00:47:56 ]
- サイズは可変で大きい、挿入削除が定数時間(->list)、省メモリ(->vector)
を同時に満たしたかったので...
とりあえず挿入削除の速いlistを選択したけど、以外とメモリ食うって分かった。
小規模のvectorをlistで繋ぐか584さんのslistつかうのがいい気がしてきた。
双方向リストだとポインタが64bit化したらさらに事態は悪化するのも気になるし...
- 589 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 00:53:20 ]
- だから小規模なvectorをつなぐぐらいならdeque使えってばよ
- 590 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 00:54:03 ]
- >>587
要素が int で、双方向のポインタがあるわけで
それぞれサイズが同じなら、int の 3倍ですね。
>>585 も指摘してますが、糞当たり前です。
- 591 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 00:54:46 ]
- >588
データ構造の勉強からやり直して来い。
- 592 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 00:55:27 ]
- s/int の/1要素あたり int の/
- 593 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 00:56:22 ]
- >>588
中身の小さいオブジェクトを入れると、相対的にlistはポインタなどの管理部分が
大きく見えてしまうからねえ。
ケースバイケースで使い分けるしかない。
それとstd::slistのiteratorは、forward iteratorなので、bidirectional iteratorのlist
に比べると実行効率の悪いメンバ関数がいくつか存在するから、その点もよく確かめてね。
- 594 名前：583 mailto:sage [2005/05/21(土) 01:04:49 ]
- dequeだと
中間への挿入、削除した場合に
参照と反復子が死滅。
- 595 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 01:05:46 ]
- >>588
テキストエディタみたいに、挿入が同一箇所に連続して発生するようなら
ギャップベクタを検討するといいかも
- 596 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 01:34:23 ]
- >>594
それが問題になるなら、もう list しかないんじゃないかなぁ。
「小規模のvectorをlistで繋ぐ」なんてのも、全然ダメだろ。
- 597 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 01:43:48 ]
- もはやtemplateの話題じゃなくて、「データ構造とアルゴリズム」の世界だな。
- 598 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 02:11:25 ]
- listとかvectorはあるのに、より優れた概念のS式がないのはおかしい
- 599 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 03:42:02 ]
- >>598
あなたね（汗
インタプリタじゃないんですから。
- 600 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 05:55:52 ]
- >>599
もっと詳しく。
・・・って言っても無駄か。
何もわかってないくせに噛み付いてるの見え見えだもんな。
- 601 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 08:25:20 ]
- S式ってツリー構造じゃ無かったっけ？違った？
- 602 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 08:41:31 ]
- >>600
赤黒木だけじゃ足りないってのかい。
- 603 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 09:18:31 ]
- >>597
STLネタがそっちに向かうのは自然だと思うけど？
- 604 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 09:22:59 ]
- > つうか双方向リストは最低2つはポインタが必要なんだから当たり前の気がするんだが
直前の要素のポインタと直後の要素のポインタの排他的論理和演算結果を保持しておけ。
そうしておけばポインタ1つで双方向からリストをたどることができる。
実行時にそれなりのコストはかかるが、、、
- 605 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 10:01:07 ]
- >>604
結局サイズは変わらないわけだが。
しかも「ポインタ同士のXOR」？ﾜｹﾜｶﾗﾝ。
- 606 名前：604 mailto:sage [2005/05/21(土) 10:23:45 ]
- 以下のようなリンクリストがあったとする。
A‐B‐C
この時、B のポインタ領域には &A ^ &C となる値がセットされることになる。
順方向でA、Bまで読み込んできた場合、Aのアドレスは判っているはず。
このため、&A ^ (&A ^ &C) を計算することでCのアドレスが取得できる。
同様に逆方向でC、Bまで読み込んでいる場合、Cのアドレスは判っているため、&C ^ (&A ^ &C) を計算することでAのアドレスが取得できる。
これが magic list というデータ構造。
- 607 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 10:35:12 ]
- >>606
代償としてイテレータのサイズが大きくなるから、使い道は微妙だけどな。
- 608 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 10:43:01 ]
- >>606
ふーん。
std::list の実装に使われてるのは見たこと無いんだけど、
標準コンテナの実装としては何か問題があるのかな？
と考えたら、イテレータを取得した後に要素の削除・追加をするとマズイような気がした。
- 609 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 10:44:00 ]
- >>604
リストを変更しないときのコストはたいしてかからないんじゃないか。
簡単なループの場合、movl (%eax),%eax が xorl (%eax),%eax になるだけだろう。
>>607
イテレータのサイズなんて問題になることがそうそうあるとは思えんが。
前後に追加削除があるとイテレータが無効になってしまうから
std::listとはコンパチにならなくなることの方がまだ問題になりそうだ。
- 610 名前：604 mailto:sage [2005/05/21(土) 10:50:55 ]
- >>607
イテレータのサイズとリンクリストに保持される各要素のデータサイズを同列で比較するのもどうかと思うが。
イテレータにポインタを2つほど追加したところで、8バイトしかサイズは増えない。
（処理が複雑化する分、イテレータオブジェクトのサイズはもう少し増えると思うが。）
しかし、双方向ポインタにしてしまうと、各要素毎に4バイトの投資が必要となる。
- 611 名前：604 mailto:sage [2005/05/21(土) 10:58:43 ]
- >>608>>609
確かにイテレータの取得後に前後の要素が追加削除されると痛い。
排他制御の問題を抱え込むから、std::list との互換性は考えない方が吉かと。
|
 |
