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
*/

回答No.2

επιστημη（@episteme） · ベストアンサー

> 上記のように使用すればこの場合だと変数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;
　 }
}

お礼

申し訳ありません。
先ほど試したところ、確かに挿入したいところのイテレータが返ってきていました。

std::lower_boundが中でどのような処理をやっているのかいまいちわからず、他の作業にいっぱいいっぱいで頭で考えただけで手を動かすことをしなかったことは反省したいと思います。

第3引数でポインタを渡しているのでポインタで比較されてしまうと考えていたのですが内部比較は第4引数で渡された関数が使用されるのですね・・・。

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

回答No.1

Tacosan

おおざっぱにいえば lower_bound で返ってくるのは
指定した値より小さくない最初の位置
だから, これでいけるはずです. lower_bound で返ってきたところにいれて, それ以降をうしろにずらせばいいと思う.

お礼

ありがとうございます。

No2さんの回答をもとに実行してみたところ期待通りの動作をいたしました。
今回の件で頭で考えただけで作った気になっていた自分を戒めたいと思います。

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