C言語でArrayList

分類:[その他]

非常〜に基礎的なことですが、
動的に伸び縮みするデータ構造(ArrayListみないたやつ)を作りたいですが、
なにかヒントありませんでしょうか？
データの挿入、削除、追加、抽出しても
ほとんどパフォマンスが劣化しないつくりにしたい。。。
お願いします。

こんにちは中博俊です。

アルゴリズムの本にそのあたりはいっぱい載ってます。
線形リストとかね

■No12365に返信(中博俊さんの記事)
> こんにちは中博俊です。
>
> アルゴリズムの本にそのあたりはいっぱい載ってます。
> 線形リストとかね

ありがとうございました

とりあえず、参考に
http://www9.plala.or.jp/sgwr-t/c/sec15-5.html

ここに書かれているのは、ほんとに基本的なものです。
これがわからないならば、C言語を最初から勉強しなおしたほうがいいです。

一応、先のサイトのトップページ
http://www9.plala.or.jp/sgwr-t/

ArrayListみたいなものを目指すとなると、クラスの概念がないC言語では相当面倒臭そう。

C++でよければstd::listがあるんですけどねぇ。。。

■No12370に返信(Blueさんの記事)
> とりあえず、参考に
> http://www9.plala.or.jp/sgwr-t/c/sec15-5.html
>
> ここに書かれているのは、ほんとに基本的なものです。
> これがわからないならば、C言語を最初から勉強しなおしたほうがいいです。
>
> 一応、先のサイトのトップページ
> http://www9.plala.or.jp/sgwr-t/
>
> ArrayListみたいなものを目指すとなると、クラスの概念がないC言語では相当面倒臭そう。
>
> C++でよければstd::listがあるんですけどねぇ。。。

ありがとうございます。

まさにこれでいけそうですね。勉強したことがあることを今思い出しました^^;
大量のデータの削除でも持ってる次のポインタを書き換えるだけでおわりますね。
ただ配列のようにダイレクトに特定のインデックスにアクセスするような
手段がない。。。てか自分でなんとかしろって話かもしれませんね。
ここらへんがネックになるかも（自分の実装がここがとろい処理になりそうな。。）
あ、メモリ開放も時間かかりそうな。。

挫折したらstd::listでいきます^^;
一応、C++コンパイラでCだけ書いている状態ですので。

> 一応、C++コンパイラでCだけ書いている状態ですので。
では、最初からC++でかかれてみては？
テンプレートやオペレータ、クラスなどがあるので扱いやすいかと。
# 私の場合はいざとなったらMFCのソースをコソーリ覗いて参考にしています。
# (CMapやCArray等)

■No12373に返信(Blueさんの記事)
>>一応、C++コンパイラでCだけ書いている状態ですので。
> では、最初からC++でかかれてみては？
> テンプレートやオペレータ、クラスなどがあるので扱いやすいかと。
> # 私の場合はいざとなったらMFCのソースをコソーリ覗いて参考にしています。
> # (CMapやCArray等)

いろいろと実験してみました、listはなかなか良い感じです。
ただ、やはりインデックスがないのが。。。
イテレータを常に把握して、またそれと同じ位置を保持する数値型の変数を使えば
なんとかなるかなって思います。たぶん注意点としては、なるべく相対位置でイテレータを
移動することで、結構高速にできるのではないと思います。

というかlistをラップしてArrayListそのものを作ることも簡単ですよね^^;

余談ですが、C/C++系ってほんと速度が速いですね。一度この味を知ってしまったら
.NETに戻れないかも^^;今のところ自分は.NETしか知りませんが

VisualStuidioからnativeコードをはかなくなる日がもし来たらかなりショックかも。
#nativeアプリケーションを作る方法は絶対になくなりはしないでしょうけど、
#VSからはできなくなったらかなりさびしい。。
#とりあえずVS2005はまだ大丈夫みたいですね。

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

> いろいろと実験してみました、listはなかなか良い感じです。
> ただ、やはりインデックスがないのが。。。

std::vecetor のソースを参考にしてみては？

> 余談ですが、C/C++系ってほんと速度が速いですね。一度この味を知ってしまったら
> .NETに戻れないかも^^;今のところ自分は.NETしか知りませんが

その辺は用途次第ですね。

C/C++ は、実行効率の高いコードを生成しますが、それはエラーチェックやセキュリティチェックのほとんどすべてをプログラマの手に委ねているからです。

それなりの規模のアプリケーションを記述するためにはエラーチェックやセキュリティチェックは欠かせないもので、そういったものを組み込んでいくうちに C/C++ の優位性も次第に薄れていきます。
また、すべてプログラマ任せですから、「組み込み忘れ」の危険が常に伴います。

.NET ではランタイムがエラーチェックやセキュリティチェックのかなりの部分を肩代わりしてくれるので、プログラマはごく少ない努力を投入するだけで実行時エラーやセキュリティ違反を検出したら、安全に終了するアプリケーションを記述することができます。

どちらがよいかではなく、「何が必要か」を基準に選択するのが吉でしょう。

> VisualStuidioからnativeコードをはかなくなる日がもし来たらかなりショックかも。

現行の Visual Studio に収録されているプログラミング言語で、ネイティブコードを吐くコンパイラは VC++ だけなんですよね。
ドライバや実行効率を優先したコードを記述するために、まだ当分の間消えることは無いでしょうけど。。。

■No12387に返信(渋木宏明(ひどり)さんの記事)
> std::vecetor のソースを参考にしてみては？
STLのソースを読み取るのはカナリメンドそうですね。(読みにくいのが第一)

しかし、インデックスをやろうとおもうと、結構大変なんですよね。
(ランダムアクセスできないので、削除や挿入された時に再計算し直しなけらばならない)
# STLやboostライブラリを駆使すれば簡単に出来るかもしれないが。。。

std::listをstd::vectorに変更するのもありかもしれませんが、
挿入、削除の面でstd::listよりも性能がおちます。

> std::listをstd::vectorに変更するのもありかもしれませんが、
> 挿入、削除の面でstd::listよりも性能がおちます。

「その代わり」にインデックスが使えるわけですから、「インデックスが使えること」が必須であるなら、仕方の無いトレードオフと思います。

でなければ、完全に要件を満たすコードを１から自分で書くしかないでしょう。

> しかし、インデックスをやろうとおもうと、結構大変なんですよね。

はい、そういう意味でなるべく行き先(インデックス)に対して相対で
移動するようにします。
基本的に３つの位置からインデックスに移動することになりますので、
まず最短の距離になるほうを選んでそこからいくようにする予定です。
３つの位置とは
先頭、末尾、現在位置です。
たとえば、1000000 のデータに対して 890000 の位置に行きたい場合
末尾からいくようにするとなかり短くなりますので。もし、たまたま
現在位置が 890005 の場合わずか 5 の移動ですみます。
それでも、どうもがいても移動に時間がかかることが間違いなくありますが。

ま、全部当たり前の話ではありますが。。。

#現在位置はイテレータの位置ですが、同じ位置を示す数値を変数で保持します。
#確かに同期とるのも大変ですね。

> たとえば、1000000 のデータに対して 890000 の位置に行きたい場合
> 末尾からいくようにするとなかり短くなりますので。もし、たまたま
> 現在位置が 890005 の場合わずか 5 の移動ですみます。
> それでも、どうもがいても移動に時間がかかることが間違いなくありますが。

「よく使う位置」を記憶しておくブックマーク的な実装を用意してみるとか？

> #現在位置はイテレータの位置ですが、同じ位置を示す数値を変数で保持します。
> #確かに同期とるのも大変ですね。

同期は、コレクション操作内でコールバックしてもらうようにするとか。

アドバイスありがとうございます。

> 「よく使う位置」を記憶しておくブックマーク的な実装を用意してみるとか？
ブックマークの管理が大変そうで。。。^^;

> 同期は、コレクション操作内でコールバックしてもらうようにするとか。
コールバックはしないつくりにしていますが、一応内部変数への直アクセスは
避けてます。状態変数すべて関数を通して必要なチェックを行ってから設定するように
する予定です。
C言語ベースで書いてますので、オブジェクト指向もどきって感じですが。
いや、これが原型でしょう。。。

C++でクラス作ればすむ話ですが、C++は言うほど知りませんので。。。
妥協しました^^;