[C++]イテレータの扱いについて

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
yu
記事: 5
登録日時: 5年前
住所: 東京

[C++]イテレータの扱いについて

#1

投稿記事 by yu » 5年前

こんにちは。yuと申します。
件名の内容に関して、色々と調べてはいるものの答えが見つからないため皆様のお力添えを頂きたいと思います。

[内容]
双方向リストクラス(std::list)に格納された文字列を含む構造体(STRINFO)のリストに対し、特定文字列が含まれているかどうか順次検索をかけ、
見つかった時点で同構造体に含まれる文字列の使用有無を管理するメンバの値を書き換えようとしています。
もともとはリストに対して線形探索をおこなっていましたが、これだと処理時間がかかりすぎるため、処理時間の短縮のためにバイナリサーチへと変更
を試みています。そのため、「list⇒vector」へ変換をおこなったうえで、検索をかけています。

文字列検索の結果は構造体(STRINFO)のuseflgに格納されるため、この結果を検索対象のリスト「listB」に反映させたいのですが、どのようにおこなえば良いのでしょうか。


[STRINFO構造体]
stringname //文字列
useflg //文字列の使用有無を管理するメンバ

std::list< STRINFO >* pstrlist[ ] = {
&listA,
&listB, //←このリストが対象
&listC
};

//「listB」 list⇒vectorへの変換
std::vector< STRINFO > itechange( pstrlist[ 1 ]->begin(), pstrlist[ 1 ]->end() );

//イテレータの宣言
std::vector< STRINFO >::iterator itevstring;


/*****処理省略*****/

//バイナリサーチ
int left = 0; //リスト左辺
int right = itechange.size(); //リスト右辺
int mid = 0; //中間点
int result = 0;

while( left <= right ){

mid = left + ( right - left ) / 2; //中間点の抽出
itevstring = ( itechange.begin() + mid ); //イテレータに中間点を格納

result = _tcscmp( itevstring -> stringname, itevbace -> stringname ) //「itevbace」は比較用のリストです。

if( result > 0){
right = midpoint - 1; // 次回は左側を探索する
}
else if( result < 0 ){
left = midpoint + 1; // 次回は右側を探索する
}
else{
itevstring->useflg = true; // 一致したため、当該文字列は使用済みとする
}
}

上記のような探索処理をおこなっていますが、「itevstring」の検索結果を、おおもとの「listB」に反映するにはどのような処理が適しているのでしょうか?

アバター
tk-xleader
記事: 153
登録日時: 9年前
連絡を取る:

Re: [C++]イテレータの扱いについて

#2

投稿記事 by tk-xleader » 5年前

 たとえば、itrchangeをstd::vector<STRINFO>からstd::vector<std::pair<STRINFO,std::list<STRINFO>::iterator> >に変更した上で、STRINFOとそれに対応するlistのiteratorをpairで管理するという方法があります。
 その場合、itrchangeを構築する方法としては、

コード:

// <utility>ヘッダをincludeすること。

itrchange.reserve(pstrlist[1].size());
for(std::list<STRINFO>::iterator itr = pstrlist[1]->begin(),end = pstrlist[1]->end(); itr != end; ++itr){
    itrchange.push_back(std::make_pair(*itr,itr));
}
とした上で、itrvstring->stringname/useflgとしている箇所を、itrvstring->first.stringname/useflgに書き換えればいいかと思います。
オフトピック
 今回のような処理であれば、std::multimapを使ったほうがいいかもしれませんね。その場合のコードは以下のような形になります。

コード:

// <map>をincludeすること。

struct STRINFOComparer{
	typedef bool result_type;
	typedef STRINFO first_argument_type, second_argument_type;
	bool operator(const STRINFO& first,const STRINFO& second){
		return _tcscmp(first.stringname,second.stringname) < 0;
	}
};

/*略*/

std::multimap<STRINFO,std::list<STRINFO>::iterator,STRINFOComparer>itrmap;
for(std::list<STRINFO>::iterator itr = pstrlist[1]->begin(),end = pstrlist[1]->end(); itr != end; ++itr){
    itrmap.insert(std::make_pair(*itr,itr));
}

std::pair<std::multimap<STRINFO,std::list<STRINFO>::iterator,STRINFOComparer>::iterator,std::multimap<STRINFO,std::list<STRINFO>::iterator,STRINFOComparer>::iterator>result = itrmap.equal_range(*itevbace);
for(std::multimap<STRINFO,std::list<STRINFO>::iterator,STRINFOComparer>::iterator itr = result.first; itr != result.second; ++itr){
	(*itr).first.useflg = true;
}
もしC++11あるいは14を使ってもよいのであれば、もっと簡潔に書けます。

yu
記事: 5
登録日時: 5年前
住所: 東京

Re: [C++]イテレータの扱いについて

#3

投稿記事 by yu » 5年前

tk-xleader様

ご返信ありがとうございます。
前述の方法を参考に処理を作成したのですが、以下の部分でエラーが発生しています。

itevstring = ( itechange.begin() + mid ); //イテレータに中間点を格納

ここの代入部分がうまくいっていないようです。

[エラー内容]
error C2679: 二項演算子 '=' : 型 'std::_vector_iterator<_Ty,_Alloc>' の右オペランドを扱う演算子が見つかりません (または変換できません)。

pairを使用した事がなく解決方法が不明なのですが、どういった方法で代入をおこなうのが良いのでしょうか?

アバター
みけCAT
記事: 6274
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: [C++]イテレータの扱いについて

#4

投稿記事 by みけCAT » 5年前

yu さんが書きました:前述の方法を参考に処理を作成したのですが、以下の部分でエラーが発生しています。

itevstring = ( itechange.begin() + mid ); //イテレータに中間点を格納

ここの代入部分がうまくいっていないようです。
itevstringの型を std::vector<std::pair<STRINFO,std::list<STRINFO>::iterator> >::iterator にするとどうなるでしょうか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

yu
記事: 5
登録日時: 5年前
住所: 東京

Re: [C++]イテレータの扱いについて

#5

投稿記事 by yu » 5年前

みけCAT様

返信ありがとうございます。
エラー発生時に自分の方でもご指摘頂いた方法を試しているのですが、エラーが解消しませんでした。
※現在手元に確認環境が無いので、明日もう一度試してみます。

演算子のオーバロード もしくは 型のcastが必要?と考えたりもしましたが、pairを使用している際にどのような記述をおこなえば良いか解らず
手詰まりになってしまいました。

yu
記事: 5
登録日時: 5年前
住所: 東京

Re: [C++]イテレータの扱いについて

#6

投稿記事 by yu » 5年前

前回のレスの代入問題に関しては、みけCAT様にご教示頂いた方法で解決しました。
※エラーはこちらの記述ミスによるものでした・・ スミマセン

ただし、根本の問題に関しては依然解決していない状態で、以下のpairで管理する方法では「listB」内の情報が更新されていませんでした。
一旦multimapを使用した処理に変更後テストをおこなってみようと思います。


↓↓↓↓↓↓[pairによる管理]↓↓↓↓↓↓↓

たとえば、itrchangeをstd::vector<STRINFO>からstd::vector<std::pair<STRINFO,std::list<STRINFO>::iterator> >に変更した上で、STRINFOとそれに対応するlistのiteratorをpairで管理するという方法があります。
 その場合、itrchangeを構築する方法としては、

コード:

// <utility>ヘッダをincludeすること。

itrchange.reserve(pstrlist[1].size());
for(std::list<STRINFO>::iterator itr = pstrlist[1]->begin(),end = pstrlist[1]->end(); itr != end; ++itr){
    itrchange.push_back(std::make_pair(*itr,itr));
}
とした上で、itrvstring->stringname/useflgとしている箇所を、itrvstring->first.stringname/useflgに書き換えればいいかと思います。

アバター
usao
記事: 1584
登録日時: 7年前

Re: [C++]イテレータの扱いについて

#7

投稿記事 by usao » 5年前

オフトピック
やりたいことは
std::list< STRINFO >に関して,「stringname が指定の文字列と一致する要素」全てについてフラグ useflag を立てる

…で合っていますか?

こんな?
► スポイラーを表示

アバター
tk-xleader
記事: 153
登録日時: 9年前
連絡を取る:

Re: [C++]イテレータの扱いについて

#8

投稿記事 by tk-xleader » 5年前

 できる限り質問者様のコードに添った形でやりたいことを実現できる方法を考えてみていたのですが、根本からコードを直してもよいなら、std::multimap<std::string,bool*>を使って、次のように初期化して、次のように取り出すのがいいのかなと思います。

コード:

// 以下のコードは、STRINFO::useflgの型がboolであることを前提としているため、そうでない場合はboolになっている場所をその型に書き換えること。

struct CStringComparer{
    typedef bool result_type;
    typedef const TCHAR* first_argument_type;
    typedef const TCHAR* second_argument_type;
    bool operator(first_argument_type first,second_argument_type second){
        return _tcscmp(first,second) < 0;
    }
};

// C++03の場合はファンクタを実装する必要がある。C++11以降ならばラムダ式があるので不要。
class MapInitializer{
	std::multimap<const TCHAR*,bool*,CStringComparer>&map_to_initialize;
public:
	MaoInitializer(std::multimap<const TCHAR*,bool*,CStringComparer>&map_to_initialize_):map_to_initialize(map_to_initialize_){
	}
	void operator()(STRINFO& info){
		map_to_initialize.insert(std::pair<const TCHAR*,bool*>(info.stringname,&info.useflg));
	}
};

// C++03の場合は(ry
struct ListFlagChanger{
	void operator()(std::pair<const TCHAR*,bool*>&arg){
		*arg.second = true;
	}
};

/* 略 */

// multimapの初期化。初期化と同時にSTRINFO::stringnameを基準にソート済みとなる。
std::multimap<const TCHAR*,bool*,CStringComparer> itrmap;
std::for_each(pstrlist[1].begin(),pstrlist[1].end(),MapInitializer(itrmap));

/* 略 */

// ソート済みのmapから対象文字列を探し出してフラグを立てる。検索はmultimapなので二分検索相当の計算量(O(logn))。
std::pair<std::multimap<const TCHAR*,bool*,CStringComparer>::iterator,std::multimap<const TCHAR*,bool*,CStringComparer>::iterator> result = itrmap.equal_range(itevbace.stringname);
std::for_each(result.first,result.second,ListFlagChanger());

yu
記事: 5
登録日時: 5年前
住所: 東京

Re: [C++]イテレータの扱いについて

#9

投稿記事 by yu » 5年前

usao様、tk-xleader様

レスありがとうございました。
それぞれご回答頂いた内容を試してみましたが、それぞれ以下の部分でエラーになってしまいました。

[usao様ご回答内容]
auto fListIterCmp = []( const ListIter &lhs, const ListIter &rhs )->bool{ return (lhs->stringname < rhs->stringname); };

ここの部分で構文エラーとなってしまいました。
こちらで使用している開発環境は『visual studio 2005』なのですが、何か関連がありますでしょうか?


[tk-xleader様ご回答内容]
当方のコードをベースにした案と、根本からのコード変更案どちらも掲示して頂きありがとうございます。
こちらとしましては、まず当方のコードをベースにした案(最初のmultimap使用案)を元に処理の移植をおこないましたが、
以下の複数箇所でエラーが発生しました。

・構造体「STRINFOComparer」
オペレータ記載部分
bool operator(const STRINFO& first,const STRINFO& second){
return _tcscmp(first.stringname,second.stringname) < 0;
}

ここの部分でエラーが発生しました。
記述を以下のように変更したところ、エラーは発生しないようになりましたが、問題無いでしょうか?
「bool operator()(const ・・・」

また、上記対応後以下の箇所でもエラーが発生しています。
「itrmap.equal_range(*itevbace);」 //異なる型での比較が不可とのこと

最初にこちらでUPさせて頂いたコードに情報が不足していたため申し訳ないのですが、
「itevbace」は「STRINFO型」ではなく別の構造体メンバとなっています。
ここでは「STRLINE型」としておきます。
双方で保持するメンバは異なっていますが、今回の比較文字列のベースとなる「stringname」は共通の情報として保持しています。
こちらの情報掲示に不足があり申し訳ありません。

また、最後にもう1点ですが、
「(*itr).first.useflg = true;」 この部分の代入で「constメンバーへの代入は禁止されている」旨のエラーも発生していました。
userflg自体はconst定義しておりませんので、もしかすると前述のエラーによる影響なのかもしれませんが、こちらに関しても何かおわかりでしたら、
ご教示頂けますと助かります。

アバター
tk-xleader
記事: 153
登録日時: 9年前
連絡を取る:

Re: [C++]イテレータの扱いについて

#10

投稿記事 by tk-xleader » 5年前

 まず総論として、itevbaseがSTRINFO型ではないのであれば、最初のstd::multimapを使ったコードでは対処できないですね。multimapを使ったパターンで書くのであれば、根本からコードを書き換えたパターンを使うほうがいいような気がします。
 それと、Visual Studioが2005であれば、usaoさんのコードはコンパイルできません。なぜなら、ラムダ式というC++11以降の規格でC++に追加された機能が使用されているからです。もちろん、ファンクタに置き換えれば通りますが…

 次に各論として、std::multimap::equal_range()は、multimapのキーの型の引数を取るメンバなので、multimapのキーがSTRINFO型の場合、STRLINE型のオブジェクトを渡すことはできません。
 最後の、(*itr).first.useflgがconstメンバーになっているというエラーについてですが、これはmultimap::value_typeがstd::pair<const Key,T>であることに起因するものなので、これは私のミスです。

コード:

(*(*itr).second).useflg = true;
と直すのが一番手っ取り早いでしょうか。いずれにしても、std::multimap::equal_rangeにSTRLINE型が渡せない以上、multimapのキーをSTRINFO型のままの設計ではどうにもならないですね…

閉鎖

“C言語何でも質問掲示板” へ戻る