std::lower_boundについて
- std::lower_boundを使用して変数pをソート済み配列IntArrayに挿入する方法が分からない
- lower_boundの使用方法やコードの修正方法を教えてほしい
- 特殊ケースでの問題のため、int* pをintに修正したり、挿入後に再度ソートする方法は不要
- ベストアンサー
std::lower_boundについて
こんにちは。 std::vector< int* > IntArray; IntArray.push_back( new int( 0 ) ); IntArray.push_back( new int( 2 ) ); IntArray.push_back( new int( 1 ) ); IntArray.push_back( new int( 6 ) ); IntArray.push_back( new int( 5 ) ); IntArray.push_back( new int( 7 ) ); というint型のポインタが格納されているIntArrayを bool cmp( const int* lhs, const int* rhs ) { return *lhs < *rhs; } std::sort( IntArray.begin(), IntArray.end(), cmp ); として並べ替えたとします。 そこで新しく new int( 4 )をソートされた順番を壊さない位置に挿入したいと思いlower_boundを使用しようと思いました。 しかし、lower_boundの使い方がいまいちわかりません。 int *p = new int( 4 ); bool cmp2( const int* lhs, const int* rhs ) { return *lhs < *rhs; } std::lower_bound( IntArray.begin(), IntArray.end(), p, cmp2 ); 上記のように使用すればこの場合だと変数pを挿入する位置が返ってくるのでしょうか? 間違えているとしたら、どのように修正すれば変数pを挿入できる位置が返ってくるように書き直すことができるでしょうか?(むしろそういった実装は可能なのでしょうか) よろしくお願いします。 今回は特殊ケースでの問題ですのでint* pをintに修正する、挿入してから再度ソートする、といったことはなしでお願いします。あくまでもlower_boundで実装する場合のコードについてでよろしくお願いします。 /* VisualStudio 2008 academic edition Window7 64bit */
- 0xEF
- お礼率59% (193/327)
- C・C++・C#
- 回答数2
- ありがとう数3
- みんなの回答 (2)
- 専門家の回答
質問者が選んだベストアンサー
> 上記のように使用すればこの場合だと変数pを挿入する位置が返ってくるのでしょうか? やってみればわかることかと。 #include <iostream> #include <algorithm> #include <vector> bool cmp( const int* lhs, const int* rhs ) { return *lhs < *rhs; } int main() { std::vector<int*> IntArray; IntArray.push_back( new int( 0 ) ); IntArray.push_back( new int( 2 ) ); IntArray.push_back( new int( 1 ) ); IntArray.push_back( new int( 6 ) ); IntArray.push_back( new int( 5 ) ); IntArray.push_back( new int( 7 ) ); std::sort(IntArray.begin(), IntArray.end(), &cmp); int* p = new int(4); std::vector<int*>::iterator pos = std::lower_bound(IntArray.begin(), IntArray.end(), p, &cmp); IntArray.insert(pos, p); for ( int i = 0; i < IntArray.size(); ++i ) { std::cout << *IntArray[i] << std::endl; } }
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
おおざっぱにいえば lower_bound で返ってくるのは 指定した値より小さくない最初の位置 だから, これでいけるはずです. lower_bound で返ってきたところにいれて, それ以降をうしろにずらせばいいと思う.
お礼
ありがとうございます。 No2さんの回答をもとに実行してみたところ期待通りの動作をいたしました。 今回の件で頭で考えただけで作った気になっていた自分を戒めたいと思います。 ありがとうございました。
関連するQ&A
- メタ関数の再帰停止の方法についての質問です.
メタ関数の再帰停止の方法についての質問です. 最大公倍数を求めるメタ関数を作ろうとして引数をintに固定したものはすぐ作れたのですが 引数を任意の整数にしたものを作ろうとしたところ,いろいろな方法を試みましたがどれもだめで結局以下のようにしました. template<typename IntegerT, IntegerT Rhs, IntegerT Lhs> struct gcd; template<int Rhs, int Lhs> struct gcd<int, Rhs, Lhs> { typedef int integer_type; typedef gcd<integer_type, Rhs, Lhs> type; typedef integer_type value_type; static const value_type value = gcd<integer_type, Lhs, Rhs % Lhs>::type::value; }; template<int Rhs> struct gcd<int, Rhs, 0> { typedef int integer_type; typedef gcd<integer_type, Rhs, 0> type; typedef integer_type value_type; static const value_type value = Rhs > 0 ? Rhs : -Rhs; }; template<long long Rhs, long long Lhs> struct gcd<long long, Rhs, Lhs> { typedef long long integer_type; typedef gcd<integer_type, Rhs, Lhs> type; typedef integer_type value_type; static const value_type value = gcd<integer_type, Lhs, Rhs % Lhs>::type::value; }; template<long long Rhs> struct gcd<long long, Rhs, 0ll> { typedef long long integer_type; typedef gcd<integer_type, Rhs, 0ll> type; typedef integer_type value_type; static const value_type value = Rhs > 0ll ? Rhs : -Rhs; }; しかし,この方法だと考えられる整数全てに対して特殊化を定義せねばならず何のためにテンプレートを使っているのかわかりません. テンプレートのインスタンス化の順序を考えてみるとコンパイル時に再帰を停止するための条件が普通に考えたものとは異なるように思うのですが,どのようにすればもっと簡単に一般の整数型(short,long等)に対してメタ関数を定義できるでしょうか?
- 締切済み
- C・C++・C#
- C++文字配列ソート関数を教えてください
C++文字配列ソート関数を教えてください 配列に格納されている文字列をソートして完全一致するかを確認するロジックを作成したいのですが、上手くいきません。ネットなどでいろいろ調べたのですが>< 一応、以下に今の状態のソースを貼りました。 class StringSuzeLess { public; bool operator()( const std::string& Ihs, const std::string& rhs ) const { retrun ihs.size() < rhs.size(); } } int main() { // 文字列格納変数 chra str1[10][5+1]; char str2[10][5+1]; // 初期化 memset(str1, 0x00, sizeof(str1)); memset(str2, 0x00, sizeof(str2)); // 文字列設定 strcpy(str1[0], "AAAAA"); strcpy(str1[1], "BBBBB"); strcpy(str1[2], "CCCCC"); strcpy(str2[0], "CCCCC"); strcpy(str2[1], "BBBBB"); strcpy(str2[2], "AAAAA"); std::vector< std::string > vsmozi1; std::vector< std::string > vsmozi2; // ベクタに文字列設定 for(short LoopCnt = 0; LoopCnt < 3; LoopCnt++) { vsmozi1.push_back( std::string( str1[LoopCnt] ) ); } for(short LoopCnt = 0; LoopCnt < 3; LoopCnt++) { vsmozi2.push_back( std::string( str2[LoopCnt] ) ); } // ソート std::stable_sort( vsmozi1.begin(), vsmozi1.end(), StringSuzeLess()); std::stable_sort( vsmozi2.begin(), vsmozi2.end(), StringSuzeLess()); // ソート後の先頭から取得 for(short LoopCnt = 0; LoopCnt < 3; LoopCnt++) { // 不一致の場合 if(vsmozi1[LoopCnt] != vsmozi2[LoopCnt]) { return -1; } } return 0; }
- 締切済み
- C・C++・C#
- コンパイルエラー。間違ってるのは誰?(どこ?)
Effective C++の「型変換をさせたいなら、メンバでない関数をクラステンプレートの中で定義しよう」という項目に乗っていたコードを実験してみたのですが、コンパイルでエラーが出るようです。 ----- template<typename T> class Rational { T numerator_value; T denominator_value; public: Rational(const T& num=0, const T& den=1) :numerator_value(num), denominator_value(den){} const T numerator(){return numerator_value;} const T denominator(){return denominator_value;} void show() const { std::cout<<"numerator="<<numerator_value<<": denominator="<<denominator_value<<std::endl; } friend const Rational operator*(const Rational& lhs, const Rational& rhs) //←引数がおかしい? { return Rational(lhs.numerator()*rhs.numerator(), lhs.denominator()*rhs.denominator()); } }; int main() { Rational<int> obj1(1,10); Rational<int> obj2; obj2=obj1*10; obj2.show(); return 0; } ----- こういうコードを書いたのですが、friend関数の部分で「'const Rational<T>' から 'Rational<T> &' へ 'this' ポインタを変換できません」等と怒られます。 引数に取る二つの値のどちらもおかしいようで、コンパイルのエラーを出さないようにするためには、constと&を外さないといけないようです。 引数はEffectiveC++の掲載コードをそのまま使っています。 これは、私のコードがおかしいのか、本のコードがおかしいのかどちらでしょうか?
- ベストアンサー
- C・C++・C#
- STLでポインタのリストをsort()する方法を教えてください
STLのsort()の使い方が分からず困っています。 定義したクラスから生成したオブジェクト群を list で管理しています。 ↓こんな形です。 class cMyClass { int m_Attr; public: cMyClass(); ~cMyClass(); }; std :: list <cMyClass*> m_MyList; m_MyList.push_back(new cMyClass); m_MyList.push_back(new cMyClass); ... この、m_MyListを cMyClass内の要素 m_Attr の大小でソートしたいのですが、どうにもやり方が分りません。。。 教えていただけないでしょうか。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- ICPCの過去問
問題文↓ http://www.deqnotes.net/acmicpc/p0105/ja 答え↓ http://www.deqnotes.net/acmicpc/p0105/p0105-deq-sim.cpp です。 自分で調べたのですが、答えの中の int operator<(const Event &a) const { return time != a.time ? time < a.time : type > a.type; と、 ev.push_back(start); ev.push_back(end); の意味がよくわかりませんでした。 int operatorに関しては、sortの条件を作っているのかなとは思うのですが。 どなたか、上に挙げたふたつの部分の解説をしていただきたいです。
- 締切済み
- C・C++・C#
- なんでchar型なんでしょうか??
なぜここ(☆☆)で char型なのかが よく・・いやさっぱりわかりません。 他の型ではだめなんでしょーか? この関数自体は挿入ソートだとわ思われるんで なんとなくこの☆☆(から以下三行あたりまで) のところの動作の意味はわかるんですが なぜchar型でなくてはならないのかが。 知っている方いたら どうか教えてください。 typedef User* PUser; typedef int (*CFT)(const void*, const void*); void ssort(void* base, unsigned int n, unsigned int sz, CFT cmp) { for (int i = 0; i < n - 1; i++) for (int j = n - 1; i < j; j--) { char* pj = (char*)base + j * sz; //←ここ☆☆ char* pj1 = pj - sz; //とここ☆☆ if (cmp(pj, pj1) < 0) { for (int k = 0; k < sz; k++) { char temp = pj[k]; pj[k] = pj1[k]; pj1[k] = temp; } } } /* ssort関数の引数の関数ポインタで 利用される比較関数 */ int cmp1(const void* p, const void* q) { return strcmp(PUser(p)->name, PUser(q)->name); } int cmp2(const void* p, const void* q) { return PUser(p)->dept - PUser(q)->dept; }
- ベストアンサー
- C・C++・C#
- C++での戻り値について
C++で以下のソースを書きました。 どうしてaaaは問題ないのにbbbはだめなのかがわかりません。 どちらも、func1()、func2()で設定した文字列・vectorのポインタを返したいです。 int main() { const char* aaa = NULL; std::vector<const char*>* bbb = NULL; aaa = func1(); bbb = func2(); } const char* func1() { const char* str = NULL; str = "test"; return str; } std::vector<const char*>* func2() { std::vector<const char*>* str2 = NULL; str2->push_back("test2"); str2->push_back("test3"); return str2; } 現在必要に迫られてC++勉強中です。よろしくお願いいたします。
- 締切済み
- C・C++・C#
- const参照メンバを含む要素のvector
久しぶりに趣味でプログラミングしてます。 const参照のメンバを含むオブジェクトを要素に持つvector って使えます? 下記はbcc32でコンパイルするとエラーが出ます。 _algobase.h 145:コンパイラは 'operator=' クラスの hoge を作成できない(関数 _STL::hoge * __copy<hoge *,hoge *,int>(hoge *,hoge *,hoge *,const random_access_iterator_tag &,int *) ) ちなみにv.clear();をコメントアウトするとコンパイルは通り実行も問題なくできます。 clear()の替わりにpop_back()としてもコンパイルは通り実行も問題なくできます。 コンパイラーのバグ?そもそもこんなことをしてはダメ? よろしくお願いします。 class hoge { public: hoge(const int &i):_i(i){}; virtual ~hoge(){}; operator int () const {return _i;} const int &_i; }; int main() { int i1=1; int i2=2; hoge h1(i1); hoge h2(i2); std::vector<hoge > v; v.push_back(h1); v.push_back(h2); v.clear(); std::vector<hoge >::iterator iter = v.begin(); while( iter != v.end() ){ std::cout << *iter << "\n"; ++iter; } return 0; }
- ベストアンサー
- C・C++・C#
- qsortについて
qsort()で構造体をソートする時に、qsortの第3,4引数時の、「size t_t size, int (*cmp)(const void *a, const void *b)」の使い方が分かりません。 何故これを使ってソートが出来るのでしょうか?そもそも、構造体を送った時に、自作関数内での書き方にも疑問があります。 int main(void){ MAX dt[5]={・・・・}; //構造体変数宣言 ・・・・・ qsort(dt,5,sizeof(MAX),sum); //(*1) .... return 0; } int sum(const void *a, const void *b){ MAX *p1 = (MAX *)a; //(*2) MAX *p2 = (MAX *)b; //(*2) ・・・・ return ~; } ---------------------------------------------------- *1: 第3引数のsizeof(MAX)って何ですか? *2: 例えばint型が渡されてreturnする場合は、「return *(int *)a - *(int *)b 」でいいのに、 何故構造体の場合はこう書かないといけないのですか?
- ベストアンサー
- C・C++・C#
- shared_ptr クラスについて
shared_ptrクラスを使いたいのですが、使えません、どうしてでしょうか?ソースはこれです。 #include<iostream> #include <string> #include <fstream> #include<memory> using namespace std; class SMonster{ string name; int power; public: SMonster(); SMonster(int p); ~SMonster(){ }; void SetPower(int p); int GetPower(SMonster& t)const; void walk(const string& str); int GetPoint(void)const; }; class B {}; class D : public B {}; int main(void) { shared_ptr<D> sp0(new D); SMonster m(200); SMonster n(100); std::cout<<m.GetPower(m)<<std::endl; std::cout<<n.GetPower(n)<<std::endl; ShowWindow(10); }
- ベストアンサー
- C・C++・C#
お礼
申し訳ありません。 先ほど試したところ、確かに挿入したいところのイテレータが返ってきていました。 std::lower_boundが中でどのような処理をやっているのかいまいちわからず、他の作業にいっぱいいっぱいで頭で考えただけで手を動かすことをしなかったことは反省したいと思います。 第3引数でポインタを渡しているのでポインタで比較されてしまうと考えていたのですが内部比較は第4引数で渡された関数が使用されるのですね・・・。 ありがとうございました。