spliceを含んだlistのループを正しく行うには? – プログラミング – Home

spliceを含んだlistのループを...
 
通知
すべてクリア

[解決済] spliceを含んだlistのループを正しく行うには?


Orange
 Orange
(@Orange)
ゲスト
結合: 14年前
投稿: 14
Topic starter  

お世話になります
Win7 VC++2008 Express で開発しております

listのループ中にspliceを行う場合、
以下の記述で正しくループする保障があるのかお教えください。
あと、他に良い記述などがありましたらお教え頂けないでしょうか。

一応私の環境で正しい結果が得られているので、
正しくループするという認識でいるのですが。
他に良い確認の方法がわからなくて悩んでいます。

よろしくお願いいたします。

#include <list>

using namespace std;

int main(void)
{
list<bool> alive;
list<bool> dead;

alive.push_back(true);
alive.push_back(true);
alive.push_back(true);
alive.push_back(false);
alive.push_back(true);
alive.push_back(false);
alive.push_back(true);
alive.push_back(true);

// falseをdeadに移動させ、aliveをtrueだけにする
list<bool>::iterator li = alive.begin();
while(li != alive.end())
{
if( *li == false )
{
list<bool>::iterator sli = li;
++li; // spliceの後に行うとデバッグアサートで引っかかる
dead.splice(dead.end(), alive, sli);
}
else
{
++li;
}
}

// 結果出力
・・・

return 0;
}


引用未解決
トピックタグ
poyonshot
 poyonshot
(@poyonshot)
ゲスト
結合: 13年前
投稿: 1
 

1行で書くとか
dead.splice(dead.end(), alive, li++);

splice を使わないとか(コピーのコストが気になる。)
dead.push_back(*li);
li = alive.erase(li);

どうでしょう。


返信引用
Orange
 Orange
(@Orange)
ゲスト
結合: 14年前
投稿: 14
Topic starter  

> 1行で書くとか

なるほど!
引数に渡す時点でコピーが発生するので、わざわざ一時的なコピーを作る必要はありませ
んね。
コードもすっきりして良い感じになりました。ありがとうございます。

// falseをdeadに移動させ、aliveをtrueだけにする
list<bool>::iterator li = alive.begin();
while(li != alive.end())
{
if( *li == false )
{
dead.splice(dead.end(), alive, li++);
}
else
{
li++;
}
}

> splice を使わないとか

falseになったデータをtrueにして、再びaliveへ移動することを考えているので
spliceを使っております。

// deadになったデータを一つ復活!
li = dead.begin();
*li = true;
alive.splice(alive.end(), dead, li);


返信引用
επιστημη
 επιστημη
(@επιστημη)
ゲスト
結合: 14年前
投稿: 40
 

/*
* 要素のコピーを許すなら、僕ならこうする
*/
#include <list>
#include <algorithm>
#include <iterator>
#include <iostream>

using namespace std;

struct is_true {
bool operator()(bool b) const { return b; }
};

int main() {
list<bool> alive;
list<bool> dead;

alive.push_back(true);
alive.push_back(true);
alive.push_back(true);
alive.push_back(false);
alive.push_back(true);
alive.push_back(false);
alive.push_back(true);
alive.push_back(true);

// falseをdeadに移動させ、aliveをtrueだけにする
dead.splice(dead.end(), alive, stable_partition(alive.begin(),alive.end(),
is_true()), alive.end());

// 結果確認
cout << boolalpha;
cout << alive: ;
copy(alive.begin(), alive.end(), ostream_iterator<bool>(cout, ));
cout << endl;
cout << dead : ;
copy(dead.begin(), dead.end(), ostream_iterator<bool>(cout, ));
cout << endl;
}


返信引用
Orange
 Orange
(@Orange)
ゲスト
結合: 14年前
投稿: 14
Topic starter  

一旦、trueとfalseに分けてfalseの部分を移動させるということですね。
これは思いつきませんでした、勉強になります。
要素がポインタであれば問題なく使えると思いました。

> 要素のコピーを許すなら、僕ならこうする

「要素のコピーを許さない」であれば、どのような方法になるのでしょうか?
すごく興味があります!
さしつかえがなければ、ぜひお教えください。


返信引用
επιστημη
 επιστημη
(@επιστημη)
ゲスト
結合: 14年前
投稿: 40
 

/*
* 要素のコピーを許さないなら、参照コンテナでいんぢゃね?
* compiled by Visual C++ 10
*/
#include <array>
#include <list>
#include <algorithm>
#include <iterator>
#include <memory>
#include <iostream>

using namespace std;

typedef shared_ptr<bool> item;

int main() {
list<item> alive;
list<item> dead;

array<bool,8> input = { true, true, true, false, true, false, true, true};
transform(input.begin(), input.end(),
back_inserter(alive),
[](bool b) { return make_shared<bool>(b);});

// falseをdeadに移動させ、aliveをtrueだけにする
dead.splice(dead.end(),
alive,
stable_partition(alive.begin(), alive.end(),
[](item b) { return *b;}),
alive.end());

// 結果確認
cout << boolalpha;
cout << alive: ;
for_each(alive.begin(), alive.end(), [](item x) { cout << *x << ' '; });
cout << endl;

cout << dead : ;
for_each(dead.begin(), dead.end(), [](item x) { cout << *x << ' '; });
cout << endl;
}


返信引用
Orange
 Orange
(@Orange)
ゲスト
結合: 14年前
投稿: 14
Topic starter  

「要素のコピーを許さない」場合の方法を教えて頂きありがとうございます。
自分では、list<bool*> でも問題ないと思ったのですが、list<shared_ptr<bool>> を使
用する理由は、
右辺値参照により要素自体のコピーも発生しなくなることを意図しているからでしょうか?
何度も質問してすみません、よろしければお願いいたします。

#include <algorithm>

using namespace std;

typedef shared_ptr<bool> item;

int main() {

// 右辺値参照の確認
bool b0 = true, b1 = false, b2 = false;
b1 = b0; // 値がコピーされる
b2 = _Move(b0); // 右辺値参照を試みる。
// プリミティブな型は移動するのか分かりません

bool *pb0 = &b1, *pb1 = 0, *pb2 = 0;
pb1 = pb0; // アドレスがコピーされる
pb2 = _Move(pb0); // 右辺値参照を試みる。
// やはりプリミティブな型は移動しない?
// というか確認方法がわかりません…

item i0(new bool(true)), i1, i2;
i1 = i0; // 左辺値参照が呼ばれコピーが発生する。(参照数は1から2になる)
i2 = _Move(i0); // 右辺値参照が呼ばれ移動するだけなのでコピーは発生しない。
// i0の値はデバッガーでempty。(参照数は2のまま)

return 0;
}


返信引用
επιστημη
 επιστημη
(@επιστημη)
ゲスト
結合: 14年前
投稿: 40
 

そんな深遠な意味なんざカケラもありゃせんです。
「shared_ptrなら後始末にdeleteしまくらんでも勝手に消えてくれんじゃん」
そんだけ。


返信引用
Orange
 Orange
(@Orange)
ゲスト
結合: 14年前
投稿: 14
Topic starter  

教えて頂いたコードが高度すぎて、いらぬ深読みをしてしまったみたいです^^;
とても勉強になりました。

poyonshot さん
επιστημη さん
ご回答ありがとうございました。


返信引用

返信する

投稿者名

投稿者メールアドレス

タイトル *

プレビュー 0リビジョン 保存しました
共有:
タイトルとURLをコピーしました