lower_boundを使用してソートされたベクトルに値を挿入する方法

Question

STLを使用してintキーでソートしたいクラスAへのポインタのベクトルがあります。これを行うには、私は、定義されたクラスでoperator <

bool operator< (const A &lhs, const A &rhs){ 
    return (lhs.key < rhs.key); 
}; 

と私の挿入機能では、私は新しい要素を配置することができます最初の場所を返すようにlower_boundを期待

vector<A*>::iterator it = lower_bound(vec.begin(), vec.end(), element); 
vec.insert(it, element); 

ように見えますが、それはありませんうまくいかない。キー0,1,2,3のオブジェクトを挿入すると、ベクトルが不正確な順番（2,3,1,0）になります。何故ですか ？

たぶん私はまた、このオブジェクトのためのコンパレータを使用することができます。

compare function for upper_bound/lower_bound

が、どのような私のコードが悪いですの？

Answer 1

あなたの例では、ポインタのベクトル：std::vector<A*>を使用しています。したがって、あなたはstd::lower_boundに渡し、ポインタのための比較を定義する必要があります。

bool less_A_pointer (const A* lhs, const A* rhs) 
{ 
    return (lhs->key < rhs->key); 
} 

auto it = std::lower_bound(vec.begin(), vec.end(), element, less_A_pointer); 
//... 

もちろん、質問はなぜあなたは最初の場所でポインタを使用しているされて - あなたが本当にする必要がない限り、単にAオブジェクトを格納します。あなたはポインタを格納する必要がない場合は、あなたのためにこれを処理するどのstd::shared_ptrに見て：あなたの場合は本当に

auto it = std::lower_bound(v.begin(), v.end(), 
          [](const A* lhs, const A* rhs) 
          { return lhs->key < rhs->key; }); 

Answer 2

：あなたはまた、代わりに無料の機能を記述することのラムダを使用することができます

std::vector<std::shared_ptr<A>> v; 
std::shared_ptr<A> element(new A(...)); 
auto it = std::lower_bound(v.begin(), v.end(), element); //Will work properly 

std::vectorのポインタが必要な場合は スマートポインタを std::shared_ptrのように使用することを検討してください。
生ポインタ彼らは ポインタを観察しているが、一般的にあなたが （いくつかの特別な条件でない限り）ポインタをowining 生を使用していない 必要がある場合はOKです。

ラムダをstd::lower_bound()に渡して、ソート基準を指定することができます（この場合、キーデータメンバーを比較します）。

また、代わりに明示的std::lower_bound()の戻り値をstd::vector<std::shared_ptr<A>>::iteratorを書くのは、あなただけ、この場合は、コードをより読みやすくなりますC++ 11のautoキーワードを使用することができます。 （G ++ 4.8.0でコンパイルされた）

コンパイルコードサンプルは、次のとおりです。

#include <algorithm> // for std::lower_bound 
#include <iostream>  // for console output 
#include <memory>  // for std::make_shared, std::shared_ptr 
#include <string>  // for std::string 
#include <vector>  // for std::vector 
using namespace std; 

// Test data structure 
struct A 
{ 
    int Key; 
    string Data; 

    A() 
     : Key(0) 
    {} 

    A(int key, const string& data) 
     : Key(key), Data(data) 
    {} 
}; 

ostream& operator<<(ostream& os, const A& a) 
{ 
    os << "(key=" << a.Key << ", data=\"" << a.Data << "\")"; 
    return os; 
} 

void Print(const vector<shared_ptr<A>> & v) 
{ 
    cout << "[ "; 
    for (const auto & p : v) 
    { 
     cout << *p << " "; 
    } 
    cout << " ]\n"; 
} 

int main() 
{ 
    // Test container 
    vector<shared_ptr<A>> v; 

    // Test data 
    const char* data[] = { 
     "hello", 
     "world", 
     "hi", 
     nullptr 
    }; 

    // Index in data array 
    int i = 0; 

    // Insertion loop 
    while (data[i] != nullptr) 
    { 
     // Create new element on the heap 
     auto elem = make_shared<A>(i, data[i]); 

     // Find ordered insertion position 
     auto it = lower_bound(v.begin(), v.end(), elem, 
      [](const shared_ptr<A>& lhs, const shared_ptr<A>& rhs) 
      { 
       return lhs->Key < lhs->Key; 
      } 
     ); 

     // Insert in vector 
     v.insert(it, elem); 

     // Move to next data 
     i++; 
    } 

    // Show the result 
    Print(v); 
} 

ここでは出力です：

ポインタのベクトルを使用して

[ (key=2, data="hi") (key=1, data="world") (key=0, data="hello") ]