Help us understand the problem. What is going on with this article?

識別子と順序付け

More than 1 year has passed since last update.

この記事はAltplus Advent Calendar 2017の6日目のエントリです。

こんにちは、職業Scalalian、C++愛好家の竹田です。

識別子は整数型で表現すること多いですが、整数型などをそのまま使用してしまうと、”順序付け可能である”や”配列のインデックスで使用できる”などの整数型の性質を前提にコーディングしてしまい危険です。

例えば、”順番通り”に並んでいて、ID番の要素にそのIDと関連付けられているデータを使用してコーディングをしてしまうと、様々なバグの温床になります。

#include <vector>
#include <iostream>

using ID = int;
using Probability = double;
using Image = int;

static std::vector<Probability> probabilityForEachID = {0.1, 0.2, 0.3, 0.4};
static std::vector<Image> imageForEachID = {10, 20, 30, 40};

Probability badProbability(ID id){
    return probabilityForEachID[id];
}

Image badImage(ID id) {
    return imageForEachID[id];
}

void displayImageAndProbability(Probability const& p, Image const& i){
    std::cout << "probability = " << p << " , image = " << i << std::endl;
}

int main(){
    displayImageAndProbability(badProbability(0), badImage(0));
}

このコードでは、probabilityForEachIDimageForEachIDの、i番目の要素がID iに関連するデータでなければいけないという暗黙のルールを守っている間は、想定通りに動作します。しかし、データの追加やコード中の操作でprobabilityForEachIDimageForEachIDの要素の並び順が変わってしまうと、インデックスとIDが対応しているという暗黙のルールが破られてしまい、IDに関連するデータが正確に引けなくなってしまいます。

識別子

問題の原点は、識別子に必要以上の性質を与えてしまったことにあります。Wikipediaで識別子の定義を引くと「識別子(しきべつし、英: identifier)とは、ある実体の集合の中で、特定の元を他の元から曖昧さ無く区別することを可能とする、その実体に関連する属性の集合のこと」(By Wikipedia)とあります。

識別子とは、集まりの中である個を他の個と区別するための情報です。"区別"をC++で表現するには、等価演算子が相応しいので、等価演算子をサポートして識別子を表現するクラスを導入して、どのようにコードが変わるか見てみます。

#include <unordered_map>
#include <iostream>

struct ID{
    int id;
};

bool operator==(ID lhs, ID rhs) {
    return lhs.id == rhs.id;
}

bool operator!=(ID lhs, ID rhs) {
    return !(lhs == rhs);
}

namespace std {
    // IDをunordered_mapで使用するための特殊化。
    template<>
    struct hash<ID>{
        size_t operator()(ID const& x) const
        {
            return hash<int>{}(x.id);
        }
    };
}

using Probability = double;
using Image = int;

static std::unordered_map<ID, Probability> probabilityForEachID 
= {{ID{0}, 0.1}, {ID{2}, 0.3}, {ID{1}, 0.2}, {ID{3},0.4}};
static std::unordered_map<ID, Image> imageForEachID 
= {{ID{1}, 20}, {ID{2}, 30}, {ID{3}, 40}, {ID{0}, 10}};

Probability betterProbability(ID id){
    return probabilityForEachID.at(id);
}

Image betterImage(ID id) {
    return imageForEachID.at(id);
}

void displayImageAndProbability(Probability const& p, Image const& i){
    std::cout << "probability = " << p << " , image = " << i << std::endl;
}

int main(){
    displayImageAndProbability(betterProbability(ID{0}), betterImage(ID{0}));
}

このコードでは、IDの同値関係(operator==)とHashを利用して、unordered_mapのキーにIDを利用しています。probabilityForEachIDimageForEachIDのデータの順番をシャッフルしていますが、意図通りに動作します。

unordered_mapは、Hashマップで実装されています。メモリ使用量やメモリ・アクセス速度が気になる場合は、以下のようにstd::vector<std::pair<ID, Data>>を使用することができます。ただしこの方法では、識別子の一意性などが保証できないため、同じIDに対するデータが複数ある状況になりえるので、データ用のコンテナを操作するところでは、事後条件のチェックやユニットテストを通じて、一意性を保証するようにしましょう。

またBoostが使える状況では、std::vector<std::pair>のような性質でmapのIFを提供しているflat_mapもあるので、flat_mapの使用も検討しましょう。

#include <vector>
#include <iostream>
#include <algorithm>

struct ID{
    int id;
};

bool operator==(ID lhs, ID rhs) {
    return lhs.id == rhs.id;
}

bool operator!=(ID lhs, ID rhs) {
    return !(lhs == rhs);
}

using Probability = double;
using Image = int;

static std::vector<std::pair<ID, Probability>> probabilityForEachID 
= {{ID{0}, 0.1}, {ID{2}, 0.3}, {ID{1}, 0.2}, {ID{3},0.4}};
static std::vector<std::pair<ID, Image>> imageForEachID 
= {{ID{1}, 20}, {ID{2}, 30}, {ID{3}, 40}, {ID{0}, 10}};

Probability betterProbability(ID id){
    auto const found = std::find_if(probabilityForEachID.begin(), probabilityForEachID.end(),
                [&](auto const& p){ return p.first == id; });
    if(found == probabilityForEachID.end()){
        throw std::out_of_range("Not found.");
    }
    return found->second;
}

Image betterImage(ID id) {
    auto const found = std::find_if(imageForEachID.begin(), imageForEachID.end(),
                [&](auto const& p){ return p.first == id; });
    if(found == imageForEachID.end()){
        throw std::out_of_range("Not found.");
    }
    return found->second;
}

void displayImageAndProbability(Probability const& p, Image const& i){
    std::cout << "probability = " << p << " , image = " << i << std::endl;
}

int main(){
    displayImageAndProbability(betterProbability(ID{0}), betterImage(ID{0}));
}

最後に

あるコンセプト(識別子)の表現に必要以上の性質(int型で表現して、順序付けやインデックスとしての使用できる性質)を与えてしまうと、バグの温床になることを見てきました。

自分で型を定義して適切な性質を与えることで、安全で見通し良いコードを書くことができます。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした