この記事のポイント

  • C++におけるmap・multimapの構造と設計意図を整理
  • ユースケースごとの使い分け基準をレビューアー視点で理解
  • 重複許容・挿入コスト・探索性能などのレビュー観点を学べる

そもそもmap・multimapとは

C++標準ライブラリにおけるmapとmultimapはいずれも連想配列（辞書型コンテナ）です。共通点も多いですが、設計意図は大きく異なります。

特徴 map multimap
キーの重複 不可 可
内部構造 平衡二分探索木 (通常はRed-Black Tree) 同左
検索性能 O(log N) O(log N)
挿入性能 O(log N) O(log N)
ユースケース 一意マッピング 複数紐付け

map

  • 同じキーは1回しか格納できない
  • insert時に既存キーがあれば無視or更新（用途に応じる）
  • データはソート状態で保持

multimap

  • 同じキーに対して複数の値を格納可能
  • insertは常に挿入成功
  • 内部ソート順は保持

なぜこれをレビューするのか

レビューアー視点

map・multimapは極めて日常的に利用される分、無意識選択の温床になりやすいです。

  • 重複が発生し得るのか？
    → 仕様設計の確認

  • 上書き禁止・許可は設計責務か？
    → API契約に現れる設計意図

  • 探索中心か、挿入中心か？
    → 性能特性が分岐

  • 順序保持が必要か？
    → unordered_mapとの違い

  • std::pair<const Key, T> の設計負荷認識
    → 書き換え意図との整合性確認

開発者視点

  • mapのinsertが上書きしない仕様を意外と知らない
  • mapにとりあえずpushして意図せず上書きが起きる
  • multimapを知らず「map<key, vector>」を手動実装
  • パフォーマンス差を理解しないまま選択

こうしたケースをレビューアーは事前に発見し、手戻りを減らします。

良い実装例

ユースケース：APIログにおけるrequestId単位のユニークな登録

良い実装例：map活用によるユニーク保証 
#include <map>
#include <string>
#include <cstdint>

struct ApiRequestLog {
    std::string requestId;
    std::string endpoint;
    std::string clientIp;
    int responseCode;
    int64_t requestedAt;
};

class RequestLogIndex {
public:
    bool addLog(const ApiRequestLog& log) {
        auto [iter, inserted] = logs_.insert({ log.requestId, log });
        return inserted; // 既存キーならfalse
    }

    const ApiRequestLog* find(const std::string& requestId) const {
        auto iter = logs_.find(requestId);
        if (iter != logs_.end()) {
            return &(iter->second);
        }
        return nullptr;
    }

private:
    std::map<std::string, ApiRequestLog> logs_;
};
  • requestIdは一意である
  • 挿入時に重複可否を戻り値で通知
  • 重複仕様がAPI契約に現れている

レビュー観点

  • 重複発生は業務ロジック上どう定義されているか
  • 重複発生時の挙動はAPI契約で明文化されているか
  • mapのinsert戻り値を正しく確認しているか
  • 不要にerase→insertをしていないか（性能劣化）
  • find後のイテレータ生存期間を正しく管理しているか
  • ソート順利用有無は確認済みか

良くない実装例: ケース1

以下はmapにvectorを埋め込んで重複許容を独自実装してしまった例です。

map内vector誤用例 
#include <map>
#include <vector>
#include <string>
#include <cstdint>

struct ApiRequestLog {
    std::string requestId;
    std::string endpoint;
    std::string clientIp;
    int responseCode;
    int64_t requestedAt;
};

class RequestLogIndex {
public:
    void addLog(const ApiRequestLog& log) {
        logs_[log.requestId].push_back(log);
    }

    const std::vector<ApiRequestLog>* find(const std::string& requestId) const {
        auto iter = logs_.find(requestId);
        if (iter != logs_.end()) {
            return &(iter->second);
        }
        return nullptr;
    }

private:
    std::map<std::string, std::vector<ApiRequestLog>> logs_;
};

@Reviewer
重複キーの許容要件であればmultimapを使用してください。map<key, vector<value>>は不要な二重管理・性能低下を招きます。

問題点

  • 無駄なvectorのヒープ確保が都度発生
  • map+vectorの2重管理負荷
  • multimapに対する構造的利点が無い

改善例

修正例：multimap活用による簡潔化 
#include <map>
#include <string>
#include <cstdint>

struct ApiRequestLog {
    std::string requestId;
    std::string endpoint;
    std::string clientIp;
    int responseCode;
    int64_t requestedAt;
};

class RequestLogIndex {
public:
    void addLog(const ApiRequestLog& log) {
        logs_.insert({ log.requestId, log });
    }

    std::pair<std::multimap<std::string, ApiRequestLog>::const_iterator,
              std::multimap<std::string, ApiRequestLog>::const_iterator>
    find(const std::string& requestId) const {
        return logs_.equal_range(requestId);
    }

private:
    std::multimap<std::string, ApiRequestLog> logs_;
};
multimapのequal_range
  • 同一キーに紐づく全件取得に適している
  • 不要なvector管理が消える
  • 既存の木構造内で安定動作

良くない実装例: ケース2

次はinsertではなくoperator[]で安易に上書きしてしまうケースです。

operator[]誤用例 
#include <map>
#include <string>
#include <cstdint>

struct ApiRequestLog {
    std::string requestId;
    std::string endpoint;
    std::string clientIp;
    int responseCode;
    int64_t requestedAt;
};

class RequestLogIndex {
public:
    void addLog(const ApiRequestLog& log) {
        logs_[log.requestId] = log;
    }

    const ApiRequestLog* find(const std::string& requestId) const {
        auto iter = logs_.find(requestId);
        if (iter != logs_.end()) {
            return &(iter->second);
        }
        return nullptr;
    }

private:
    std::map<std::string, ApiRequestLog> logs_;
};

@Reviewer
operator[]は既存キーに対し無条件上書きします。重複検知要件があるならinsertで挿入可否を明示的に確認しましょう。

問題点

  • 重複が意図せず上書きになる
  • insertとの差異を開発者が混同しやすい
  • 意図した重複検出ロジックが実装できていない

改善例

修正例：insertによる重複検出 
void addLog(const ApiRequestLog& log) {
    auto [iter, inserted] = logs_.insert({ log.requestId, log });
    if (!inserted) {
        // 重複検知処理（例：ログ出力、例外投げ等）
    }
}

PlantUMLで構造比較

UML Diagram

観点チェックリスト

まとめ

mapとmultimapは見た目以上に設計意図の表現媒体となるコンテナです。
重複を許すか否か、その検出責任は誰に持たせるか、上書き可能性をどの層で制御するか——これらがコンテナ選定に如実に現れます。
レビューアーは単なるパフォーマンス比較を超えて、API契約と仕様の整合性観点から選定理由を読み解きましょう。