如何保持multimap中元素的插入顺序？词法分析场景求助

你遇到的问题本质是std::multimap的特性导致的：它会自动按照键（也就是你的Token类型）进行排序，所以不管你按什么顺序插入Token，最终输出时都会把同类型的元素归为一组，完全打乱了词法扫描的原始顺序。

要解决这个问题，最直接且符合词法分析需求的方案是放弃multimap，改用顺序容器存储Token，具体来说就是用std::vector——它会严格保留元素的插入顺序，完美匹配你需要的Token序列顺序。

具体实现步骤： #

1. 先定义一个Token结构体，用来存储每个Token的类型和值：

#include <vector>
#include <string>
#include <iostream>

// 定义Token类型枚举
enum class TokenType {
    Keyword,
    Name,
    Symbol,
    Number
};

// 定义Token结构体，存储类型和对应的值
struct Token {
    TokenType type;
    std::string value; // 如果需要区分数字和字符串，可以用C++17的std::variant
};

2. 扫描代码时，将识别出的Token依次插入vector：

int main() {
    std::vector<Token> tokens;

    // 模拟你的扫描过程，按顺序插入Token
    tokens.push_back({TokenType::Keyword, "let"});
    tokens.push_back({TokenType::Name, "main"});
    tokens.push_back({TokenType::Symbol, "="});
    tokens.push_back({TokenType::Keyword, "let"});
    tokens.push_back({TokenType::Name, "value"});
    tokens.push_back({TokenType::Symbol, "="});
    tokens.push_back({TokenType::Number, "8"});
    tokens.push_back({TokenType::Symbol, "+"});
    tokens.push_back({TokenType::Number, "2"});

    // 按插入顺序输出Token
    for (const auto& token : tokens) {
        // 把TokenType转换成对应的字符串
        std::string typeStr;
        switch(token.type) {
            case TokenType::Keyword: typeStr = "keyword"; break;
            case TokenType::Name: typeStr = "name"; break;
            case TokenType::Symbol: typeStr = "symbol"; break;
            case TokenType::Number: typeStr = "number"; break;
        }
        std::cout << "Type: " << typeStr << " Value: \"" << token.value << "\"\n";
    }

    return 0;
}

为什么这个方案可行？ #

词法分析器输出的Token序列顺序是核心属性——后续的语法分析完全依赖Token的出现顺序，所以顺序容器（vector）是最适合的存储方式。而multimap这类关联容器的设计目标是快速按键查找，天生不适合需要保留插入顺序的场景。

备选方案（如果有特殊需求） #

如果你因为某些原因必须使用关联容器，同时还要保留插入顺序，可以考虑使用Boost.MultiIndex库。它允许你创建一个同时支持多种索引的容器：比如一个索引按插入顺序（序列索引），另一个索引按Token类型。不过这个方案需要引入Boost库，适合有特殊查询需求的场景，对于普通的词法分析来说，vector已经足够。

内容的提问来源于stack exchange，提问作者JCN