mapでキーの有無を調べるには、find()よりcount()が便利

C++

このエントリーをはてなブックマークに追加

mapコンテナ(mとする)でキーの有無を調べる場合、今まではメンバ関数のm.find()を呼ぶ方法を使っていた。m.find()を使う方法では、「m.find()の戻り値がm.end()に等しければキーが存在しない、そうでなければキーが存在する」としてキーの有無を判別していた。

しかし、m.count()を使った方がより直感的である。m.count()を使う方法では、「m.count()の戻り値が0に等しければキーが存在しない、1に等しければキーが存在する」という簡単仕様なので分かりやすい。

以下のコードでは、find()を使う場合とcount()を使う場合とを比較した。どちらも結果は同じである。

#include <iostream>
#include <map>

using namespace std;

bool has_key_using_find(map<int, string> &m, int n){
    if (m.find(n) == m.end()){
        cout << "m doesn't have " << n << "." << endl;
        return false;
    }
    else{
        cout << "m has " << n << "." << endl;
        return true;
    }
}

bool has_key_using_count(map<int, string> &m, int n){
    if (m.count(n) == 0){
        cout << "m doesn't have " << n << "." << endl;
        return false;
    }
    else{
        cout << "m has " << n << "." << endl;
        return true;
    }
}

int main(void){
    map<int, string> m;
    m[1] = "a";
    m[3] = "bb";
    m[5] = "ccc";

    has_key_using_find(m, 3); // true
    has_key_using_find(m, 4); // false

    has_key_using_count(m, 3); // true
    has_key_using_count(m, 4); // false
    
    return 0;
}

出力はこんな感じ。

m has 3.
m doesn't have 4.
m has 3.
m doesn't have 4.

(追記1: 2018-05-14) 意外とこの記事の参照数が多いので注意喚起。multimapコンテナやmultisetコンテナを使う場合は、キーの有無を調べるのにcount()を使うのは基本的に避けるべき。multimapやmultisetは、mapと異なり、同じキーを何度も登録することができる。count()を使うとキーの登録数を調べるために木の走査が入ってしまうので、単にキーの有無を調べる用途にはオーバーキルである。

以下に、同じキーを20000回登録したmultimapに対して、キーの有無を先述の2種類の方法で問い合わせしたときの処理時間を測るコードを掲載する。

#include <chrono>
#include <iostream>
#include <map>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

bool has_key_using_find(multimap<int, string> &m, int n){
    if (m.find(n) == m.end()){
        return false;
    }
    else{
        return true;
    }
}

bool has_key_using_count(multimap<int, string> &m, int n){
    if (m.count(n) == 0){
        return false;
    }
    else{
        return true;
    }
}

int main(void)
{
    multimap<int, string> mm;
    for(int i = 0; i < 100000; ++i) {
        mm.insert(make_pair(i % 5, "value"));  // 0 ~ 4までの5種のキーがそれぞれ20000個ずつ登録される
    }

    int TRY_NUM = 10000;

    auto start1 = chrono::system_clock::now();
    for(int i = 0; i < TRY_NUM; ++i) {
        has_key_using_find(mm, 4); // true
        has_key_using_find(mm, 5); // false
    }
    auto end1 = chrono::system_clock::now();
    auto diff1 = end1 - start1;

    auto start2 = chrono::system_clock::now();
    for(int i = 0; i < TRY_NUM; ++i) {
        has_key_using_count(mm, 4); // true
        has_key_using_count(mm, 5); // false
    }
    auto end2 = chrono::system_clock::now();
    auto diff2 = end2 - start2;
    
    cout << "find: " << chrono::duration_cast<chrono::milliseconds>(diff1).count() << "msec" << endl;
    cout << "count: " << chrono::duration_cast<chrono::milliseconds>(diff2).count() << "msec" << endl;

    return 0;
}

CygwinのG++でビルドして実行した結果は以下のとおり。500倍ほど処理時間に差がついた。

find: 9msec
count: 4982msec


(追記2: 2018-05-14)
c++ - Checking for existence in std::map - count vs find - Stack Overflow にて、この記事で書いたのと同じ議論が展開されている。そのうちの一つの回答(c++ - Checking for existence in std::map - count vs find - Stack Overflow) では、mapの処理系のソースコードを読んで、findの方がcountよりよいと結論づけている。ただ、このコードを見ると、GCCの方はfindもcountもほぼ同等のコードなのできっと速度は誤差程度にしか変わらない。一方VSの方はコードが複雑で、コードを追う根性がない…。

私が個人でC++コードを書くときはきっとcountを使うだろうけど、もしかするとチームでコーディングする場合ではfindを使う方がよいのかもしれない。理由の一つは、findを使うのはよく知られたイディオムであること。もう一つは、mapからmultimapにコンテナを変更したときにcountを修正し忘れ、速度でペナルティを受ける可能性があること。


参考：