> しかし、リストはデータのアドレスがバラバラなので配列に比べて低速です。
本当に遅いのでしょうか？
シーケンシャルアクセスする限り配列とリストで速度差は殆どありません。
データに対するランダムアクセスをしなければならないのであれば、
そもそもリスト構造を選択することが *設計上の誤り* です。

> 具体的には一度に複数のデータをリストに追加したい場合などです。
配列にデータを追加するよりリストにデータを追加するほうが、
一般的には遥かに高速です(時と場合により100倍以上速い)

何か勘違いをしていませんか？

局所性? 連続性ではなくて?

> 具体的には一度に複数のデータをリストに追加したい場合などです。
list< vector<X> > ではご不満でしょうか?

MSDNにデータの局所性が低いとページフォールトが発生し、
パフォーマンスが低下するとの記述がありました。
自分でも確かめてみて(検索)、リストは配列に比べて低速でした。

STLはまだ使ったことが無いので解りません
これを機会に勉強してみようと思います

> MSDNにデータの局所性が低いとページフォールトが発生し、
> パフォーマンスが低下するとの記述がありました。
これは御意ですが
# でもこの「局所性」の意味は若干異なるような気がする

> 自分でも確かめてみて(検索)、リストは配列に比べて低速でした。
この速度低下の原因がページフォルトかどうかは検証していないのでしょう？

二分木検索のような検索はランダムアクセスが発生する典型例なので
リストが配列より遅いのは当然です。というか、そーいうのは設計が
不良なので、比較に意味がありません。

struct hoge_t {
int key;
char *text;
};
のような hoge_t の配列を text でソートするような場合は、配列を使っても
データの局所性は全くありません。ページフォルトが多発してもおかしくないです。

すみません。「局所性」ではなく『連続性』を高めたいでした。

確かに、ただ遅かったという結果しか調べていません。

処理速度を比較したリスト、配列は、自作のものですか？それともどこかのライブラリ
のものですか？（STLではないのですよね）
また、実際の比較結果は、どのくらいの数のデータをどのように追加しようとして、
どのくらいの時間がかかったのでしょうか。
そのような具体的なデータを教えて頂かないと、どのような解決法が適切なのか、分か
りかねます。

自作です。 以下のコードで配列は約140ms、リストは約260msでした
データの追加では約33msかかっています

class A : public CListData<A>
{
public:
int a;
};

A* p;
A a[50000];

//リストに追加
for(i = 0; i < 50000; i++)
{
p = new A;
List.Insert(p);
}

//配列の要素全てをインクリメントするのを50回繰り返す
for(i = 0; i < 50; i++)
{
for(j = 0; j < 50000; j++)
a[j].a++;
}

//リストの全てのデータをインクリメントするのを50回繰り返す
for(i = 0; i < 50; i++)
{
p = List.GetFirst();
while(p)
{
p->a++;
p = p->GetNext();
}
}

いや、だから、用途によるんだってば。
追加や削除じゃなくて、既にある全候補に処理するんなら、各候補にランダムにアクセスできる
配列の方が、次の候補をたぐらなくてはいけないリストより速いのは当然です。

でも、実際の使い方はいろいろあるでしょ？
・追加や削除が頻繁に発生する/しない
・その追加や削除も必ず一番後(or前)の要素が対象になる/任意の要素が対象になる
・頻繁にソートを行う/行わない
とか。
それぞれに応じて、配列、リストの利点、欠点があるわけで、用途に応じて適切なデータ構造
を選択する必要があります。
ちなみに、この手の話は一般的に「アルゴリズムとデータ構造」という非常に定番で基礎的な
テーマです。いくらでも記事や本が出ていますので、ネットなり本なりで、調べてみて下さい。

> しかし、リストはデータのアドレスがバラバラなので配列に比べて低速です。
> なので部分的でもいいのでデータをまとめて配置したと考えています。

部分的に一度に追加する時だけ「配列」で追加する方法ばいいんじゃないですか？

配列をリストで管理しようと思います。
これなら全てをリストで管理するよりいいと思うので。

どうもありがとうございました。