8

私はこのベクトルを持っています:

using namespace std;

vector< pair<short, string> > vec = {};

<a, b>とのペアが存在するかどうかを調べたいと思いますb == X。

std::findfromについて<algorithm>は知っていますが、ここで適用する方法がわかりません。

それを行うには、独自の関数を作成する必要がありますか?

bool is_in_vec(X)
{
    for (auto& e : vec)
        if (e.second == X)
            return true;
    return false;
}

それは効率的ですか？

4

4 に答える 4

11

基準を満たす要素が存在するかどうかだけを知りたい場合、ソリューションは問題ないように見えます。constループはベクトルの要素を変更してはならないため、ループ内で参照を使用します。

for (const auto& e : vec) ....

標準ライブラリのアルゴリズムを使用したい場合は、以下を試すことができますstd::find_if:

const std::string X{"foobar"};

auto it = std::find_if(vec.begin(), 
                       vec.end(), 
                      [&X](const pair<short, string>& p)
                      { return p.second == X; });

ここで、itは条件を満たす最初の要素への反復子であり、vec.end()要素が見つからない場合は と等しくなります。

于 2014-04-19T19:36:30.570 に答える
4

vector実際、フィールドに基づいてペアを自由に並べ替えることができれば、ケーキを持って食べることができますsecond。

この場合、Boost が呼び出すものを再発明することになりますflat_(multi_)map。明らかな利点は、検索を線形時間ではなく O(log(n)) で実行できることです。

Coliruでライブを見る

using namespace std;

#include <utility>
#include <vector>
#include <string>
#include <algorithm>

typedef std::pair<short, std::string> Pair;

struct Cmp 
{
    bool operator()(Pair const& a, Pair const& b) const { return a.second < b.second; };
    bool operator()(Pair const& a, std::string const& b) const { return a.second < b; };
    bool operator()(std::string const& a, Pair const& b) const { return a < b.second; };
};

int main()
{
    std::vector<Pair> vec = { 
        { 1, "aap" }, 
        { 2, "zus" }, 
        { 3, "broer" }
    };

    Cmp cmp;
    std::sort(vec.begin(), vec.end(), cmp);

    auto it = std::binary_search(vec.begin(), vec.end(), std::string("zus"), cmp);

    std::cout << it->first << ": " << it->second << "\n";
}

版画

2: zus
42: zus
于 2014-04-19T19:54:49.863 に答える
3

C++11では、あなたも使うことができますstd::any_of

std::string X{"foobar"};
return std::any_of(vec.begin(), vec.end(),
                   [&X](const pair<short, string>& p)
                   { return p.second == X; });
于 2016-01-22T23:09:39.287 に答える
2

std::map代わりに、かなり効率的なstd::map::findメンバー関数を提供するを使用する必要があると思います。

std::map<std::string, short>
// …
auto it = map.find(X);

これは、この種のルックアップと同じくらい効率的です (これは であることが保証されていますO(log(N)))。

于 2014-04-19T19:36:58.660 に答える