C++ STL map 自動排序問題與解決方案：保持插入順序的替代方案

問題現象

std::map 內部為紅黑樹實現，鍵值自動按升序排序，而非保持插入順序：

map m = {{3,"s3"}, {2,"s2"}, {1,"s1"}};
for (auto& p : m) cout << p.first << " " << p.second << endl;
// 輸出：
// 1 s1
// 2 s2
// 3 s3  ← 自動排序，非插入順序

標準庫說明

「Internally, the elements in a map are always sorted by its key following a specific strict weak ordering criterion...」

解決方案對比

方案 1：vector + struct（保持插入順序，O(1) 追加，O(n) 查找）

struct KeyValue { int key; string value; };
vector vec = {{3,"s3"}, {2,"s2"}, {1,"s1"}};
// 遍歷即插入順序
// 查找需線性掃描

方案 2：std::unordered_map (C++11)（哈希表，無序，O(1) 平均查找/插入）

#include 
unordered_map um = {{3,"s3"}, {2,"s2"}, {1,"s1"}};
for (auto& p : um) cout << p.first << " " << p.second << endl;
// 輸出順序不確定（取決於哈希分佈），但非鍵值排序
// 查找/插入 O(1) 平均

方案 3：boost::multi_index（多索引容器，同時支援有序/無序訪問）

#include 
#include 
#include 

using namespace boost::multi_index;
struct Record { int id; string data; };

typedef multi_index_container<
    Record,
    indexed_by<
        sequenced<>,           // 保持插入順序
        ordered_unique>  // 按 id 有序
    >
> Container;

VS2015 Debug 模式鏈接錯誤補充

原文提到的 __calloc_dbg 等未解析外部符號，通常是運行時庫不匹配：

• 項目屬性 → C/C++ → 代碼生成 → 運行時庫
• Debug 選 Multi-threaded Debug (/MTd) 或 Multi-threaded Debug DLL (/MDd)
• 所有項目（含靜態庫）必須一致
• Release 同理選 /MT 或 /MD

選擇建議

總結

std::map 保證鍵值有序，不保持插入順序。需保持插入順序時：

1. 查找頻繁 → unordered_map + vector 記錄順序
2. 查找稀少 → vector<pair> 簡單直接
3. 複雜多視圖需求 → boost::multi_index

同時注意編譯器運行時庫一致性，避免 Debug/Release 混用導致鏈接錯誤。