【C++】STL（Standard Template Library）相談室 11
コンテナの使い分けってどうすればいいんですか？
ランダムアクセスが不要な場合は list を使えばいいとして
vector と deque の使いわけがよく分かりません
色々なソースを見ると、vector の使用頻度が高いように思えるのですが
要素の追加で再配置しなくていい分 deque の方がいいんじゃないですか？
dequeだとブロックで扱えないので、そこが使い分けるポイントかな。
>>672 deque には vector には無い空間オーバーヘッドと速度オーバーヘッドがある。
vector で済むところに使えば無駄になることもある。
どちらが大きな問題になりやすいかと言えば vector の再配置だろうから、
ランダムアクセスコンテナとして deque を優先的に使うという話には一理ある。
>>673-674 大きさを指定し、あまり拡張のない場合は vector の方がパフォーマンスがいいということですか
ありがとうございます、1つの基準にします
入門書がだいたいvectorで始まるもんで、dequeのほうがいい場面でもvector使っちゃう人が初心者には多いような
・・・上級者にも多いとは言わないよね
dequeが意外と遅い場合もあってポインタのvectorですませちゃうな。
要素の追加も大抵上限や要素数わかってたりするからreserveで十分だし。
本当にどっちでもいいならvectorを使うだろう。わざわざ複雑な方を使うこともない。
でもコンテナの使用頻度的にはvector>deque>listかな。listが要る場合ってほとんどない。
シーケンシャルアクセル：
list > vector > deque
ランダムアクセス：
vector > deque
追加：
list > vector > deque
追加(サイズ変)：
list > deque > vector
この認識であってる？
シーケンシャルは
vector > list
なのでは？
>>679 シーケンシャルアクセル：
vector > deque >> list
ランダムアクセス：
vector > deque
追加：先頭：キャパシティ変更なし
list > deque >>> vector
追加：先頭：キャパシティ変更
list > deque >>> vector
追加(サイズ変)：
list > deque > vector
>
> この認識であってる？
すまん、途中で送信しちゃった。
とにかく参照はvector最強、でいいよ。
>>679 こうじゃない？
シーケンシャルアクセス：
vector > deque >> list
ランダムアクセス：
vector > deque >>> list
挿入：先頭：キャパシティ変更なし
deque > list >>>> vector
挿入：先頭：キャパシティ変更あり
list >> deque >>>> vector
挿入：中間：キャパシティ変更なし
list >>> vector > deque
挿入：中間：キャパシティ変更あり
list >>>> vector > deque
挿入：末尾：キャパシティ変更なし
vector > deque > list
挿入：末尾：キャパシティ変更あり
list >> deque >>>> vector
不等号並べて書いちゃう男の人って・・・
こうやって見ると、deque の使い所がいまいち……。
メモリ効率を度外視し、vector をほぼ固定配列として使える場合、
vector でなく deque にしかできないこと、使う理由ってありますか？
dequeは名前の通りキューとしてだけ使えばおｋ
>>684 いろいろ間違ってるだろ。
dequeはオブジェクトのメモリ領域がエレメント複数個をまとめてアロケートされるからvectorのキャパシティ変更に関わらず
挿入：先頭
list > deque >>>> vector
挿入：末尾
vector > deque >= list
挿入：末尾：キャパシティ変更あり
list >= deque >>>> vector
だしdequeは全てのエレメントが連続しているわけじゃないから実際には
挿入：中間
list > deque > vecto
しかも「キャパシティ変更」の有無でvector以外のクラスの順位が変わるのも変。
知ったかぶりはやめろ。
dequeは末尾・先頭への追加に限れば、メモリ拡張の必要がある時にも
既存の要素のコピーが発生せず、参照やポインタも無効化されない。
これは大きな利点だと思う。
deque<bool>はコンテナ用件を満たすけど
vector<bool>は満たさないという問題も。
速度に関しては実測せよとアレに書いてあったじゃろ？
そして、自信を持ってvectorを選択せよ、とも。
アレが何かわからない人には教えてあげません＾＾
[ vector ]
[ ][ deque ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] list
こういうことですか
deque はリストと同じような構造だと思ってました
dequeはVCだと要素数2の配列がlist構造だね。
他の処理系は知らん。
両刀マッチョ行列
>>688 listの挿入はメモリ確保が生じるからキャパシティに余裕があるvector,dequeに対しては
挿入：先頭：キャパシティ変更なし
deque > list >>>> vector
挿入：末尾：キャパシティ変更なし
vector = deque > list
でいいだろ。
いやいやいや deque は、”一般的な利用”においては、vectorに比べ圧倒的に速いぞ。
極論言えば、むしろvectorがいらんぐらいだ。 vectorの利点はmemcpy()が使えるぐらいのもんだ
その”一般的な利用”とかいうのはどんな統計的手法に基づいて評価されたものなのだ。
ちゃんとソースを出すのだ。
ここは文系のカスプログラマが思い込みでクソ垂れる場所じゃないんで。
たかだかコレクションの実装について速いだの遅いだの言ってるお前らがカワイイよ。
おおまかな使い分けについては規格に書いてあるよ
特に(dequeやlistを使う)理由がないときはvector
先頭末尾への挿入削除が多い場合はdeque
中間への挿入削除が多い場合はlist
だった気がする
確か過去スレでdeque vs vectorの議論あったな
いやいや圧倒的に速いならdeque使うしかないだろ
お前らのアプリはコレクションに支配されてんの？
実行時間の80%はこれらをソートしたりナメたり入れたり出したりしてんの？
>>701 vectorからdeque へのtypedef書き加えるだけでも、多くのケースで体感スピード上がるという話
>>702 英語は読めないのでエスペラント語でお願いします。
vectorはメモリの連続性が真に必要なときと１バイトでもメモリ使用量を減らしたいときにだけ使え。
エスペラントなんて欧米の一部言語学保守派しか使ってないだろ
10000件近い固定サイズ構造体をdequeで使ってたんだが、boost::poolのアロケータ組み込んだら
計測値で1.7倍程度速くなった。
アルゴリズム以前にアロケータでのメモリ確保処理の速度も考えたほうがよさげ
（vectorではこうはいかない）
ちょっと書き方が不足してた
10000件近いデータを、数百～数千件単位で頻繁に挿入・削除してるという使い方。
>>707 それはとくにdequeが適する
場合なのでは？
万能コンテナなんか存在しない、
使い分けが大切、でFA。
>>706 日本語なんて極東の小さな島国でしか使われていませんよ？
それのせいでコンピュータ関連の書籍が
日本語になるのは世界から1,2年遅れていて、
プログラマになったばかりの小学6年生が学習書にも困る有様です。
まったく持ってIT後進国です。
誰も万能、って話をしていない現実ｗ
>>705 ＞１バイトでもメモリ使用量を減らしたい
フラグメを考えると、使用量は逆に
意外と増えがち。
vectorのオススメは
○reserve()できるとき。
○挿入が少なく、参照が多いとき。
だろう。
そういったケースだと、
vector<CLS*>かdeque<CLS*>かlist<CLS*>の方がよさげ
構造体をまるまる挿入するのが負荷が掛かるから。
listはlist同士の連結にコストがかからないから
状況が許すならそれも高速、安価で便利＾＾
画像処理で垂直方向の連続性は重視しないからとdeque<vector<T> >にしたら驚くほど遅くなったな。
垂直方向は参照回数少ないからそんなに遅くならないと思ったのに。
いくらメモリプールしたところで実際に100バイトの転送が発生すれば遅い。ポインタの付け替えだけなら
どれだけ巨大でも4バイトの挿入だけ。
馬鹿か垂直方向でもメモリの前後順序性は崩れないだろうが
メモリ確保がボトルネックなっているなら
Googleメモリ確保使うと良いよ。
ソースコードの変更無しで最適化出来る。
しかし、メモリ確保でボトルネックになっているのは
ほとんど処理してないって事。
もともとのソースがへぼってこと。
>>696 ,, -──- ､._
．-"´ ＼．
：/ _ノ ヽ､_ ヽ.：
：/ oﾟ(（●）) (（●）)ﾟoヽ：
：| （__人__） |：
：l ) ( l：
：` ､ `ー' /：
：, -‐ (_). ／
：ｌ_ｊ_ｊ_ｊ と)丶─‐┬．''´
：ヽ ：i |：
：/ ：⊂ノ|：
なんだ、本当のことを言われてくやしかったのか？
「定量化できないものは評価できない」
まじめに議論するところでもないんだなこれが・・・
そうでもないよ。それはその時にいる人間のレベル次第。
無能なドカタが、実生活では絶対不可能な上から目線を楽しみに来てる時とかは
まじめな議論にはならんが、いつもそうと決まったわけでもない。
listは10万要素くらい一度に確保するとめちゃめちゃ遅いのもデメリットか
mapやlistは使い所が難しいところ。
速度は気にしないならいつでも使える。
dequeもそう。
基本はvectorとstringだな。
これでも使い方次第でパフォーマンスが落ちるが。
vectorは再配置が起きると、以前の2倍確保するらしい。
これがかなりくせ者。
自前で確保したなら50Mで済むところが
自動だと100M確保したりする。
再配置の起こらないvector互換クラスはない物か。
fileをHDDに記録するように分断しつつvectorの機能も使えるやつ
そりゃdequeじゃね？
dequeは再配置はしないの?
>>728 構造的にFATと似てるので、HDDと同じような
索引テーブル上の再配置しかしないのじゃないかと思う。
730 ：
729：2009/12/09(水) 06:31:55
あーごめん。挿入すると再配置発生するそうだ
>>724 mapの使いどころは簡単。
キー検索を多用するときだろ。
>>725 それは実装によるんだろうが、じゃあ
どんなアルゴリズムがいいのか、
というと、難しいだろう。
アロケータみたいに、テンプレート
型引数で、容量拡張方法を設定
できてもいいのにね。
単にラップしてreserveを自前で行うようにすればいいだけ。
vector
要素追加: O(n)
要素削除: O(n)
ランダムアクセス: O(1)
list
要素追加: O(1)
要素削除: O(1)
deque
末端要素追加: O(1)
末端要素削除: O(1)
中間要素追加: O(n)
中間要素削除: O(n)
ランダムアクセス: O(1)
ビッグオー表記における定数時間とは
毎回1マイクロ秒でも定数だし
毎回100000000000時間でも定数には違いない。
>>736 > vectorの存在価値ないな
>>735がいってるようにランダムアクセスO(1)でもvectorとdequeでは実際に要する時間は違う。
dequeはめっちゃ遅いぞ大抵の処理系では
末端からニョキニョキ伸び縮みするような構造のために作られたものだからな
要するにstackとqueue用
でも遅すぎるので誰も使わない
固定長配列でok
dequeのバッファが最近の実装になるほどサイズが小さい傾向にあるのは
何でだろう？
大抵の実装でvectorの要素追加がときどきO(n)になるけど、
これって仕様に明記されてたっけ？
されてる
というかO(n)はデタラメで本当は別の定義がなされているからな
たまにとんでもなくコストが掛かるぜ
正しくは償却時間
償却時間はεπιστ?μηが勝手に作り出した謎の単語だ
まあ正しくは償却時間計算量あるいは償却計算量あたりかな
意味不明というほどではないが
JISにはなんて書いてあるんだろ。
戻り値も正しくは返却値って言うんだってね。
知らんかった。
>>747 「償却定数～」じゃないと意味わかんないってば。
JISでは「みなし定数時間」とかだったような
償却でも別にいいと思うけどね
「戻り値」や「フレンド関数」と同じくらい何を指してるか明白だと思う
こないだC++相談室で見た「テンプレートクラス」は謎杉だと思った
誰だよ考えたやつ
クラステンプレートで書かれたクラスなんじゃね？＜テンプレートクラス
クラステンプレート：template<typename T> class Hoge;
テンプレートクラス：Hoge<int>
？
素直に考えればクラステンプレートはテンプレートの一種でテンプレートクラスはクラスの一種であろうと考えるのは自然な考え。
それに沿えば
>>753のどこに謎があるんだ？。
>>571-754 言葉のうえで
戻り値が returns を指し、フレンドが friend を指すってのは理解できるが
テンプレートクラスが instantiated class を指すってのはちょっと理解できないな
JISにもそんな言葉はない(実は1箇所あるんだけどねｗ)
もちろん、
>>752-754のような想像をすることはまったく難しいことではないし、
JISの具現されたクラスの代替が欲しい気持ちも分かる
謎なのは instantiated class からどうやってテンプレートクラスっていう言葉を生み出したのかってこと
たとえば、禿が「instantiated classよりもtemplate classのほうがよくね？」って言ったなら謎はそれで解決
そもそも
>>751-754はどこでその言葉を覚えたのかが気になる。できれば教えて欲しい
template<...>
class ...
テンプレートクラスって読みたくなるだろ？
クラステンプレート
関数テンプレート
メンバ関数テンプレート
>>755 > そもそも
>>751-754はどこでその言葉を覚えたのかが気になる。できれば教えて欲しい
なんで
>>751-754がその言葉を以前にどこかで覚えていたということが確定事項なんだ？
>>752は推測を書いてるだけだし
>>754は単語の意味論で素直に推測をした場合には
>>753が書いた具体例に問題は見つからないと書いてるだけのようだが。
そんなことはたった今知ったばかりの言葉についても書けるだろ。
C++ Templates: The Complete Guide 7.1 にも記述があるね
> クラステンプレート、テンプレートクラス
俺はC++3rdでそう学習したけど。
っていうか今の今まで、他に呼び方が存在するなんて思ったこともなかった。
>>761を引っ張ってきた人エロイ！
template function とかもあるね
そりゃ日本人も外人も適当に名詞化するわなあ
規格にあってもinstantiated classじゃただの実体化されたクラスの意味でテンプレートとの関係をうかがわせるものは何もないからな。
規格にない俗語でもより本質に近い言葉があればそっちのほうを使いたくなるわな。
うかがわせてるだろ十分に。
そのプログラム中でインスタンスが生成されたクラスのことですか？
循環参照リストをSTLコンテナとして作ろうとしたら
beginとendが一緒になってしまって
STLコンテナには成れなかったでござる
よくわからんけど
*begin == *end かつ begin != end なイテレータにすれば？
余計なフラグを持つことになってオーバーヘッドになりそうだけど
>>769 循環参照リストにするからには
circular<int> c;
// 10個くらいpush_back
std::vector<int> v(c.begin() + 5, c.begin() + 5);
みたいな使い方もしたくて、
begin != end にしても無理だと思う。
そうすると、beginかendであることを示せる特殊なイテレータを生成できればいいわけだな。
例えば、inc/decされていない同士の比較は常にfalseを返すとか。
要素数0のときはちょっと考えないといけないが。
循環参照リストでなく循環リストでないの？
おいといて、begin,endをオフセットさせるメンバとか、内容でなく移動距離で比較するイテレータとか用意すれば？
circular<int> c;
// 10個くらいpush_back
c.setiteroffset(5);
std::vector<int> v(c.begin(), c.end());
std::vector<int> v((c.begin()+5).resetmove(), c.distanceiter(c.size()));
773 ：
デフォルトの名無しさん：2010/01/09(土) 14:38:06 BE:1050556875-2BP(0)
class C
{
C(char*psz){};
C(int n){};
};
とすると、
C c[]={"hogehoge",0xaf0};
と設定できますが、
std::vetor<C> vc={"hogehoge",0xaf0};
と設定出来ないのは何故でしょうか？
設定する方法などがあればご教授願いたいのですが。
775 ：
774：2010/01/17(日) 18:53:46
間違えた
×＞vetor
○＞vector
>>774 現行の規格では = {...} によるクラス型の初期化を定義する方法が無いから。
次の規格改訂で可能になる。
777 ：
デフォルトの名無しさん：2010/01/25(月) 22:26:42
イテレータの要素を全部足すのってどうしたらいいですか？
template<class Dest, class Iterator>
typename void add_range(Dest& dst, Iterator first, Iterator last) {
for(; first != last; first++) dst += *first;
};
>>777 #include <numeric>
std::accumulate()
トンクス
for( Particles::iterator pi = ps->begin(); pi != ps->end(); ++pi )
{
for( Particles::iterator pj = ps->begin(); pj != ps->end(); ++pj)
{
・・・
}
}
このようにイテレータを作っているのですが、このままでは範囲がΣi（０～N）Σj（０～N)というふうに計算されるのですが
Σi（０～N-1）Σj（i+1～N)というふうに計算するにはどうおけばよいのかわからないので質問させていただきます。
for( Particles::iterator pi = ps->begin(); pi != ps->end()-1; ++pi )
{
for( Particles::iterator pj = pi; pj != ps->end(); ++pj)
{
・・・
}
}
>>782 pj = pi + 1 じゃなくていいの？
イテレータの種類はランダムアクセス可能なやつなのかどうなのか
ランダムアクセス不可ならstd::advance必須
adavanceなんぞ使わんでも++pj != ps->end();で十分じゃね
二つ前のレスも読めんのか馬鹿が
788 ：
781：2010/02/01(月) 00:47:17
遅れましたが
>>782のように置いたのですがどうもうまくいかないみたいです。
std::advanceってランダムアクセスイテレータの場合だけ別処理になったっけ？
for( Particles::iterator pi = ps->begin(); pi != ps->end(); ++pi )
{
for( Particles::iterator pj = ps->begin(); pj != ps->end(); ++pj)
{
if(pi >= pj) continue;
・・・
}
}
で解決しました
これはひどい
>789
> 14882:2003 24.3.4p1
> Since only random access iterators provide + and - operators, the library provides two function templates
> advance and distance. These function templates use + and - for random access iterators (and are,
> therefore, constant time for them); (後略)
ってことでちゃんと別処理だね。
ランダムアクセスイテレータは+と-オペレーターのみを提供するので、ライブラリーは二つの
関数テンプレートに前進と間隔を提供する。
それらの関数テンプレートは+と-をランダムアクセスイテレーターのために使う。
その結果それらの為にそれらの関数テンプレートは定数時間です。
ああ、一箇所間違い発見、さてどこでしょう。
のみ
一箇所どころじゃねーだろ
では2箇所ということで・・・
もう一つはどこでしょうか。
２ちゃんに書いてしまったこと
イテレータの種類による分岐はiterator_categoryの型による特殊化なのかな？
>>799 VC9は
template<class _Iter> inline
typename iterator_traits<_Iter>::iterator_category _Iter_cat(const _Iter&)
{
typename iterator_traits<_Iter>::iterator_category _Cat;
return (_Cat);
}
template<class _InIt, class _Diff> inline
void advance(_InIt& _Where, _Diff _Off)
{
_Advance(_Where, _Off, _Iter_cat(_Where));
}
template<class _FI, class _Diff> inline
void _Advance(_FI& _Where, _Diff _Off, forward_iterator_tag);
以下input,bidirectional,random_access
だった。
㌧
やっぱりiterator_categoryをタグにして特殊化してるんだね。
自作イテレーターの場合に気をつけよう。
vector<int>に対して、すべてのデータが負であるかを判定したい時に
簡単にかけるようなアルゴリズムってある？
(forallみたいなの)
全部掛け算して負だったらどう？
MSB の and
-1,1,1の場合にだめじゃん
そういうんじゃなくて
struct NEG{
bool operator()(int n){return n<0;}
};
こういう関数オブジェクトがあれば
forall(v.begin(),v.end(),NEG());
こんな感じで呼び出せばtrueがかえる、みたいな感じの
find_if()に負判定の動詞を食わせたら？
あ、それいいですね。thx
MSBだけ取り出してANDするよりも
とりあえず全データANDしておいて
最後にMSBだけチェックした方が
全体のコストが減るのでは？
負ゼロはどうすんの
815 ：
デフォルトの名無しさん：2010/02/06(土) 08:37:45
vector<int>に対して
>>813 処理系やデータによるとしか。
例えば、できるだけ早く探索を打ち切ったほうが、キャッシュミスが減って速くなるかもしれない。
例えば、処理するデータの正数出現率に片寄りがあるかもしれない。
VS2010beta使ってて、stack<T>にemplaceってメンバがあるんだけどこれって何者？
テンプレ－トタイプ(T)のmoveコンストラクタ呼び出し版のpushかな
なるほど、どうりで検索してもヒットしないわけだ、ありがとう
C++0xの記事がヒットするんじゃねぇの
次のような比較関数を書こうとして必要になったんですが
bind3rdってないんですよね
struct sorter:binary_function<T,T,bool>{
bool operator()(const T&lhs,const T&rhs)const{
return distance(lhs,x)<distance(rhs,x); //このxを第3のパラメータにしたい
}
};
//こんな感じで使いたかった
sort(v.begin(),v.end(),bind3rd(sorter(),v[0]));
こういう場合いい方法ってありますか？
>>821 sort(v.begin(),v.end(),boost::bind(sorter(),_1,_2,v[0]))
別にbindする必要なくね？
struct sorter:binary_function<T,T,bool>{
const T &t_;
sorter( const T &t ) : t_(t){}
bool operator()(const T &lhs, const T &rhs) const{
return distance( lhs, t_ ) < distance( rhs, t_ );
}
};
sort( v.begin(), v.end(), sorter(v[0]) );
目からウロボロスでした。助かります
ファンクターの保持、コピー、使用のタイミングはそれぞれ規定がないから
ファンクター内で凝った副作用をさせないようにね。
一年くらい前と同じ話題を振るとはなかなかやるな
そういや結構長持ちしてるんだなこのスレ。
valarrayの質問はどこでしたらいいですか？
標準でテンプレートによるライブラリだからここでもいいだろうしC++相談室でもいいだろうし。
std::sprintfおせーぞ
なんとかしろや
STLじゃねーよ
速度クリティカルなところでsprintfなんて使うな
律儀だな
ん、じゃー何を使えばいい？
そもそも速度が要求される所で、文字列をこねくり回すのが間違い？
printf/sprintfは内部で使用メモリやらCPUリソースやらがものすごい事になってるんで
デバッグや速度必要なところでは使うなよ
かといって代わりのコード書くとなると ものすごい事になるし
フォーマットする部分が酷いんだからそこを特殊化すればよろし
コンテナを受け取るtemplate<class T>で、コンテナタイプで特殊化したい場合は
T::container_categoryでできますが、イテレータ型を受け取る場合は同じことって不可能でしょうか？
std::iterator_traits<T>::iterator_category
iterator_categoryで分かるのはランダムアクセスとかで、コンテナの種類が正確には分からないのでは？
std::vector<T>::iteratorとかでオーバーロードするんじゃね
一般にイテレータ型からコンテナ型の導出はできない。
例えばイテレータの実装が単にポインタだったらコンテナは？
traits
＞コンテナタイプで特殊化したい場合はT::container_categoryで～
ってのがあんまり意味が呑み込めないというか
iterator_categoryみたいにタグディスパッチでオーバーロードするって話なのか？
ってかcontainer_categoryってSTLにあったっけ？
boostのcontainer_traitsでそんなようなのものを見た記憶があるけど
844 ：
デフォルトの名無しさん：2010/03/04(木) 10:42:40
質問です。
std::set<std::string>を使おうとすると、どうしてもエラーになってしまいます。
std::set<std::string> s;
s.insert("1");
setとstringは組み合わせられないのでしょうか？
set<int>などは普通に使えているのですが…。
環境はVS2008です。
すいません。#include <string>していなかっただけでした…
STLのエラーメッセージはわかりづらいよ…（自分が悪い）
コンテナの内容を表示するこんなマクロを書いたんですが
tを入力しなくてもよいように出来たりしますか？
#define SHOW(v,t,sep) copy((v).begin(),(v).end(),ostream_iterator<t>(cout,sep));cout << endl
template <typename T>
void Show(const T &v, const std::string &sep)
{
std::copy(v.begin(), v.end(), std::ostream_iterator<typename T::value_type>(std::cout, sep.c_str()));
std::cout << std::endl;
}
マクロ使うにしてもブロックで囲むか
セミコロンをカンマに変えないと下のように書いたとき
意図しない動作になるよ
if(～) SHOW(～);
単純にブロックで囲むとそれはそれで問題なので do { /* */ } while(0) が普通。
双方向イテレータはどうしてランダムアクセス出来ないんですか？
前方と後方に自由に進めるならランダムアクセスできると思います。
計算量が多くてもランダムアクセスできた方が便利なのに
あえて出来ないようにして何か得があるんですか？
std::advanceで出来るでしょ
単に[]演算子を提供してないだけで、
それはわざとそういう設計になってる
>>854 特定の利用ケースでそのほうが便利なのであれば、ランダムアクセスできるかのような
インターフェースをかぶせることはプログラマの自由。
一般的には、計算量を無視することは不適切。
ありがとうございます。
ランダムアクセスと双方向イテレーターを分ける
計算量ってどれくらいですか？
>>857 ランダムアクセスが O(1) で双方向がコンテナのサイズ N に対して O(N) 。
O(1) とは言っても償却定数時間が許されていたかもしれない。
1とNの間はどっちにしたらいいですか？
酸素とオゾンだろ常識的に考えて
N/2とかは？
あと計算量がインデックスに依存する場合も教えてください。
宿題っぽいな
どんだけ人に頼ってんだよアホか
>>854 君が その遅いランダムアクセス子を知らずに使ってしまうからだよ
その前にO(N)とかの意味がわかっていないような・・・
>>868 ＞ランダムアクセス子
イテレータにもキャラ化の波が。ｗ
>>863 O(N/2)=O(N)
これがわからなければでなおせ。
f(N) が O(g(N)) とは
N>M ならば f(N) < C g(N)
となるような M と C が存在すること？
>>872 なんかよくわかんないんだけど、計算量の話じゃなさそうだから、たぶんちがう。
Taylor展開の剰余項みたいのをイメージしろ。
873は何をいいたいのだろうか
O(N^(1/2))などは１とNの間だろ？
ああ、NとN/2が同じってことがわかんない人につっこんでんじゃなくて
1とNの間の話ね
lognとかもそうだな
元の質問の話なら
> 1とNの間はどっちにしたらいいですか？
「どっち」かじゃないとダメなんじゃね？
そんなわけないだろ、
ツリー構造みたいなのだとlogじゃね？
なんだか高度そうなお話しているとこ申し訳ないのですが、
「最後の要素を指すiteratorを取得する」方法はありますでしょうか？
現在のところ…。
list<int> m;
m.push_back(1);
list<int>::iterator it;
it = m.end();
--it;
// これで、iteratorが最後の要素を指すようになったぞ
とやっているのですが…。
push_backは返り値を返しませんし、backは参照を返されるので、末尾のiteratorを得るにはこれしかないのかなと
m.rbegin();
なるほど！
ありがとうございます
&m.back()でよくね。
ポインタもイテレータさ！って感じで使ってもSTL的には困らないし
list<int> m;
int const *it = &m.back();
while(++it != m.end());
こうですかわかりません
相談室の質も落ちたな・・・
間違いだらけじゃねーか
>>887 間違いだらけ？ >884 のほかに何かあるか？
ツリー構造のコンテナのイテレーターは何イテレーターが適していますか？
>>888 iteratorがポインタで実装されているという保証は一切ない
>>888は884が間違ってるって指摘だろ
それは884の内容じゃん
俺も「>884のほかに（やりかた）何かあるか？」という意味でとれた
>>892 それはちょっと自身の読解力に不安を持ったほうがいいレベル
>>889 選ぶとすればbidirectional_iteratorかなぁ
たとえばinorderならrootから左右にすすめるコンテナとみなせるわけだし
tree<int,sorter=less<int>,order=inorder<int> > t;
木もSTLにあったら良いのに
list<int>::iterator it = --m.end();
881 を見て、一行で書くとこうなるのかなと思ったのですが
これだと RVO は効かなくなるのでしょうか?
Nに関係なく定数ならランダムイテレーター
それ以外は双方向イテレーターでいいですか？
コンテナのインデックスがIとしてO( I )とかO( I^2 )は
双方向かランダムどっちですか？
>>896 そんなオーダーはない。
平均するか最悪の場合を考える。
O(N)かそれより大きければ基本bidirectionalじゃね？
日本語でおｋ
>>889 仕様と実装による。
普通は、イテレータにあわないと思う。
どこかでみたなツリーのイテレータ
幅優先か深さ優先かで二つ定義されてた記憶が
tree.hhを思い出した
std::map の内部とかで 使われてなかったっけ？ xtree か何かそんな感じの
あれってイテレータ持ってなかったっけ
あったなぁ tree.hh
GPL だったから使わなかったけど、すごい参考になった
tree.hhってのが何かしらないけど
自分でツリー書いて幅か深さ、必要なのをtemplateでtag受け取って特殊化して組めばいいだけの話ではないの？
tree.hhも知らないなんてダッセ～
あれ？tree.hhってGPLだったっけ？
不審なファイルはGPLだと思って扱った方がいい
感染ってからじゃ遅い
Boost.PropertyTreeはどうなっているんだろう？
あれも構造としては木だけど。
tree.hh使わないとツリーも実装できないなんてﾀﾞｯｾｰ
B木とか赤黒木とか自分で書きたくないです
プログラム素人がプロの書いたコードに勝てるわけ無いだろｗ
おとなしく権威には従えよ
プログラム素人が「初心者」って意味なら勿論勝てるわけないし、
有名どころのライブラリを書いてるプロが優秀なのも言わずもがなだが、
もしそのついでにアマチュア全般とプロ全般を比較したがっているなら、
これについては、コードの品質とは殆ど関係無い。
プログラム素人が「初心者」
でないとしていきなり
アマチュア全般
ですか
おめでたいですね
5行も使って読解力の無さをアピールされても・・・。
いきなりというなら、いきなりプログラム素人とか言い出す人が問題なんだよ。
また読解力の無い馬鹿が湧いてきた。
>>910 いや実用的な物は書けないかもしれないが
後学のために実験プログラムを書くことは、赤黒木のソースを
読むときに大いに役立つぞ
setの要素をファイルに書き出して、またsetに読み込めるような関数を作ったんだ。
そこでiteratorが指す位置も保存して、また復元できるようにしたい。でもできない。
助けてくださいエロい人。
>>918 なにを試して「できない」と判断したの？
iteratorそのものを保存するんじゃ無理だろ。
何回++したらendと等しくなるかとかを保存しないといけないんじゃねーの
意外と面倒臭いなこれ……
キーとして機能してる値を保存じゃダメなのかい
そもそもsetは、あまりiteratorを介してアクセスするものじゃないよね。
どちらかというと全体で一塊で意味のあるようなデータだし。
問題のiteratorの保存/復元だが、値を保存して読み込むときにfindでいいと思う。
>>918 distance と advance を使ってできることとは違うのかな？
vectorのoperator[]の計算量は定数時間だと思っていたが
正しくは償却定数時間なんだな
要素の参照得るだけなのにそれマジソース総力
C++2003の仕様書の470ページ
実装としてどんなのを想定してるんだろ。
バッファの連続性保証がなかった頃の名残なのかな
vectorの中身が配列とは規定されてはないからね。
>>927 実際にアクセスされるまでメモリの確保が遅延されるシステムとか
単純なコピーオンライト実装だと 非const[]時に償却時間がかかる
>>931 コピーオンライトは、stringだったら
かなりの値打ちだと思うけど、
vectorだったらやりすぎだと感じるな。
std::stackにclear()は無いんですね
空にしたい場合こうやるよりほかにやり方はありますか？
while(!s.empty()){s.pop();}
s = std::stack<T>();
メモリが開放されて欲しいか否かによるね
開放されて欲しくない場合は正攻法は
>>933しかない
reinterpret_cast<std::deque&>(s).clear(); なんて鼻から悪魔な邪道もあるけど
そんな事するくらいなら最初からdeque使った方がいい
>>934 stackってコピー演算子定義されたたのか。これはいいこと知った。
Container c が protected だから継承すれば中のやつもいじり放題。
>>935 それ動くのか？
むしろ、それが機能するstackは使いたくないな。
stackはdequeをメンバに持って
そのメンバ関数呼んでるだけだぜ
他のコンテナを使う事もできるが、デフォルトはdeque
なんでSTLとかBoostって命名規則小文字だらけなの？
かっこいいけど。
Shiftとか小指疲れるし
SHIFTを押すときに指がつってえらいことになったから
943 ：
587：2010/03/27(土) 20:52:24
“_”もShift使うんじゃない？位置も酷いし。
SpaceShift使うとか工夫すれば良いのにねぇ。
>>939 >他のコンテナを使う事もできるが、デフォルトはdeque
じゃあ実際に何のコンテナを使っているかわからなければ
>reinterpret_cast<std::deque&>(s).clear();
なんて出来ないね
そりゃそうだが、何のコンテナを使うかを指定するのはユーザだから、分からないなんてことはない
型引数にだって残るわけだし
そういう考え方はバグの元
プログラマが管理する物を減らさないとそのうち手に終えなくなるぞ
使ってるコンテナの型はstackがContainerって名前で持ってるから
>>935 解放されて欲しいじゃなくて、解法されて欲しくない場合か、なるほど
そうなると、速度的にはどちらが有利なんだろう
container_typeだった
>>947 大文字の時点で標準じゃ無いだろう。
内部のコンテナを使って欲しいならそれなりのメンバ関数なりtypedefがあるんじゃね？
reinterpret_castは悪い冗談だ。
reinterpret_cast に関しては鼻から悪魔って言ってるじゃないかw そこでマジにならないで
>>951 だからcontainer_typeだってば
規格書にもちゃんと書かれてる歴とした標準のtypedef
直接触りたければ内部コンテナは「c」っていう名前でprotectedになってるから
継承して触ることも出来る
cも規格で決められてるのね
ただ仮想デストラクタでないクラスを継承するのもねえ
private継承なら安全だけどstackにアップキャストできないし
>>953 そんなDirtyな事はしたくないなあ
そこまでして自分の意見を通したいのか
LIFO以外の操作したい、clear()がないとダメというのなら
それはstackがそもそも適していないということでは
>>955 したくないなあ、って誰もやれとは言ってないぞ
自分の意見を通したいのは君自身じゃね？
自分も規格書見て確かめたよ
コンテナにdeque以外が指定されてたらどうすんだ
>>956 stack<hoge> s;
s=stack<hoge>()がスマートかな
961 ：
957：2010/03/28(日) 00:27:37
>>960 記法で代替できるかじゃなくて、選択したデータ構造が
stackである必然がないんじゃないかって話
端的にいえばdeque使えよってだけ
>>961 IDが出ないんだから何とでも言えるわな
>>958 言っておくが、コンテナの種類はテンプレート引数から指定するんだぞ
そしてデフォルト引数がdequeなのは規格で決まっている
stackにpush、pop以外にclearが欲しいという気持ちは分かるが
規格上可能かどうかの話と、推奨されるかどうかの話がごっちゃになってるな
自分で付け足せばいい
#include <stack>
template <typename T, typename Seq = std::deque<T> >
class my_stack : protected std::stack<T, Seq> {
private:
typedef std::stack<T, Seq> base;
public:
using base::value_type;
using base::reference;
using base::const_reference;
using base::size_type;
using base::container_type;
explicit my_stack(const Seq& c = Seq()) : base(c) { }
using base::empty;
using base::size;
using base::top;
using base::push;
using base::pop;
void clear() { base::c.clear(); }
};
デストラクタ
デフォルトでいいだろ
そういうこっちゃな
Stackアダプタぐらい自作した方が良い
STLのコンテナって継承していいんだっけ
コンテナアダプタはおｋ？
だって継承ないじゃん
単にガワを被せただけ
コンポジションに近い
ちょっと質問の仕方に問題があった
デストラクタが仮想でないことに気をつければ
コンテナアダプタは継承しても問題ないよね
>>972 そこは public 継承じゃなけりゃ問題にならんだろ。
>>976 public継承しなければコンパイルエラーになるだろ
コンストラクタとデストラクタのあるクラスをprivate継承すると
コンパイルできない
んなこたぁない
できねえよ
試してみろよ
コンストラクタにアクセスできませんって叱られる
こんな簡単なプログラムでもコンパイルできないよ
class A {
A() {}
~A() {}
};
class B : A {
B() {}
~B() {}
};
int main()
{
B b;
}
>>982 あったりまえだろう。Bのコンストラクタ、デストラクタがprivateになっとるだろうが。
皆が言ってるのはこうでしょ。
class A {
public:
A() {}
~A() {}
};
class B : private A {
public:
B() {}
~B() {}
};
int main()
{
B b;
}
アホすぎて吹いた
No problem
>>967でもpublic継承したいところを
涙を飲んでちゃんとprotected継承してるでしょ