【C++容器和算法】容器综合应用：文本查询程序

在 C++ 编程中，容器是管理数据的重要工具。不同类型的容器（如vector、map、set等）适用于不同的场景，合理地组合使用它们能够高效解决复杂问题。文本查询程序是一个非常经典的 C++ 容器综合应用案例，通过实现这个程序，我们可以深入理解容器的特性与使用技巧。

一、容器选型：各展其能的STL兵器库

1.1 动态数组王者：vector

// 高效存储文档内容
std::vector<std::string> documents;
documents.reserve(10000); // 预分配内存优化性能

• 应用场景：存储有序文档列表，支持快速随机访问
• 优势：内存连续，缓存友好，尾部插入O(1)时间复杂度
• 注意：频繁中间插入需配合insert+erase使用

1.2 哈希表先锋：unordered_map

// 建立单词到文档ID的映射
std::unordered_map<std::string, std::vector<size_t>> inverted_index;

• 核心特性：平均O(1)复杂度查询，适合高频次查找场景
• 冲突处理：采用链地址法解决哈希碰撞
• 性能调优：通过reserve()预分配桶数量

1.3 有序集合双雄：set vs map

// 维护已索引文档集合
std::set<std::string> processed_files;

// 构建有序词频统计
std::map<std::string, size_t> word_counts;

• set特性：自动排序，唯一性保证，适合范围查询
• map优势：保持键值对有序，支持区间遍历
• 对比选择：需要有序遍历时选map，仅需存在性检查用unordered_set

1.4 链表容器：list的特定场景应用

// 实现LRU缓存淘汰机制
std::list<std::string> lru_cache;

• 适用场景：频繁插入删除的中间操作
• 性能特点：任意位置插入O(1)，但随机访问效率低

二、文本查询程序功能概述

2.1 基本功能

文本查询程序的核心功能是在给定的文本文件中查询特定单词出现的次数以及所在的行号。例如，当用户输入一个单词时，程序能够返回该单词在文本中出现的总次数，同时列出包含该单词的每一行文本内容及其行号。

2.2 扩展功能

在基本功能的基础上，还可以进一步实现单词出现位置的统计可视化（如绘制词频分布图）、支持通配符查询、区分大小写查询等扩展功能。本文先聚焦于基本功能的实现，后续可基于此进行扩展。

三、涉及的 C++ 容器及其作用

3.1 vector<string>

用于存储文本文件的每一行内容。vector是一个动态数组，它能够根据需要自动调整大小，方便逐行读取文本文件中的内容并进行存储。例如，可以通过循环将文件中的每一行读入到vector<string>容器中。

3.2 map<string, set<int>>

这个容器组合用于记录每个单词在哪些行中出现。其中，map的键是单词（string类型），值是一个set<int>，set中存储的是该单词出现的行号。map可以快速地根据单词查找对应的行号集合，而set能够自动对行号进行排序并去除重复项。

3.3 set<int>

除了作为map的值用于存储行号外，set还可以用于其他需要去重和排序的场景。在文本查询程序中，它确保每个行号只被记录一次，并且按照升序排列，便于后续展示。

四、文本查询程序实现步骤

4.1 读取文本文件

首先，需要打开并读取文本文件，将每一行内容存储到vector<string>中。以下是实现代码：

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <map>
#include <set>

using namespace std;

vector<string> readFile(const string& filename) {
    vector<string> lines;
    ifstream file(filename);
    if (file.is_open()) {
        string line;
        while (getline(file, line)) {
            lines.push_back(line);
        }
        file.close();
    } else {
        cerr << "无法打开文件: " << filename << endl;
    }
    return lines;
}

readFile函数接受文件名作为参数，尝试打开文件。如果文件打开成功，通过getline函数逐行读取文件内容，并将每行内容存入lines这个vector<string>容器中，最后关闭文件并返回lines。

4.2 构建单词索引

读取完文件后，需要对每一行中的单词进行处理，构建单词与行号的对应关系，存入map<string, set<int>>中。代码如下：

map<string, set<int>> buildIndex(const vector<string>& lines) {
    map<string, set<int>> wordIndex;
    for (size_t i = 0; i < lines.size(); ++i) {
        istringstream iss(lines[i]);
        string word;
        while (iss >> word) {
            wordIndex[word].insert(i + 1);  // 行号从1开始计数
        }
    }
    return wordIndex;
}

buildIndex函数遍历lines中的每一行，使用istringstream将每行拆分成单个单词。对于每个单词，将其作为键在wordIndex这个map中查找，如果键不存在则创建一个新的set<int>，然后将当前行号插入到对应的set中。

4.3 实现查询功能

有了单词索引后，就可以实现查询功能了。用户输入一个单词，程序根据索引返回查询结果。代码如下：

void queryWord(const string& word, const map<string, set<int>>& wordIndex, const vector<string>& lines) {
    auto it = wordIndex.find(word);
    if (it != wordIndex.end()) {
        const set<int>& lineNumbers = it->second;
        cout << "单词 \"" << word << "\" 共出现 " << lineNumbers.size() << " 次。" << endl;
        for (int lineNum : lineNumbers) {
            cout << "第 " << lineNum << " 行: " << lines[lineNum - 1] << endl;
        }
    } else {
        cout << "单词 \"" << word << "\" 未在文本中出现。" << endl;
    }
}

queryWord函数接受要查询的单词、单词索引wordIndex以及存储文本行的lines作为参数。通过在wordIndex中查找单词，如果找到则输出单词出现的次数以及包含该单词的每一行内容和行号；如果未找到则提示单词未在文本中出现。

4.4 主函数调用

最后，在主函数中调用上述函数，实现完整的文本查询流程。代码如下：

int main() {
    string filename = "test.txt";  // 替换为实际文件名
    vector<string> lines = readFile(filename);
    if (lines.empty()) return 1;

    map<string, set<int>> wordIndex = buildIndex(lines);

    string query;
    cout << "请输入要查询的单词（输入q退出）: ";
    while (cin >> query && query != "q") {
        queryWord(query, wordIndex, lines);
        cout << "请输入要查询的单词（输入q退出）: ";
    }

    return 0;
}

在main函数中，首先指定要读取的文件名，调用readFile读取文件内容，然后调用buildIndex构建单词索引。接着通过循环让用户输入要查询的单词，调用queryWord进行查询，直到用户输入q退出程序。

五、程序运行示例

5.1 准备测试文本

假设我们有一个名为test.txt的文本文件，内容如下：

5.2 运行程序

编译并运行上述代码，按照提示输入要查询的单词：

六、知识点深度解析

6.1 vector容器

• 动态内存管理：vector在内存不足时会自动分配更大的内存空间，并将原有元素拷贝过去，实现动态扩容。例如，在readFile函数中不断向vector<string>中push_back新的行内容时，vector会根据需要调整自身大小。
• 随机访问：vector支持通过下标运算符[]快速访问元素，时间复杂度为 O (1)。使得在queryWord函数中根据行号获取对应行文本非常高效。

6.2 map容器

• 键值对存储：map以键值对的形式存储数据，并且按键进行排序（默认使用<运算符比较键）。在文本查询程序中，以单词作为键，行号集合作为值，方便根据单词快速查找其出现的行号。
• 查找效率：map的查找操作时间复杂度为 O (log n)，其中 n 是map中元素的个数。这保证了即使在较大的文本中查询单词也能快速得到结果。

6.3 set容器

• 自动排序与去重：set中的元素会自动按照升序排列，并且不允许有重复元素。在文本查询程序中，set<int>用于存储行号，确保每个行号只记录一次且有序展示。
• 集合操作：set还支持交集、并集、差集等集合操作，虽然在基本文本查询程序中未用到，但在扩展功能（如查询多个单词共同出现的行）中可能会用到。

6.4 文件操作

• 文件打开与关闭：使用ifstream打开文件，通过is_open判断文件是否成功打开，最后使用close关闭文件。在readFile函数中展示了这一完整流程。
• 逐行读取：getline函数用于从文件流中逐行读取内容，结合vector可以方便地存储整个文本文件的每一行。

6.5 字符串流操作

istringstream用于将字符串拆分成单个单词。在buildIndex函数中，通过istringstream将每一行文本拆分成单词，以便构建单词索引。

七、可能遇到的问题及解决方案

7.1 文件打开失败

如果指定的文件名不存在或没有读取权限，ifstream打开文件会失败。可以通过检查is_open的返回值来判断，并在失败时输出错误信息，如readFile函数中所示。

7.2 内存占用问题

当处理非常大的文本文件时，vector和map可能会占用大量内存。可以考虑使用更节省内存的数据结构，如unordered_map（牺牲有序性换取更快的查找速度和更低的内存占用），或者分块处理文本文件。

7.3 单词大小写敏感问题

当前程序默认是大小写敏感的查询。如果需要实现不区分大小写的查询，可以在构建索引和查询时将单词统一转换为大写或小写，例如使用std::transform函数结合std::tolower或std::toupper来实现。

八、总结

通过实现文本查询程序，我们综合运用了vector、map、set等 C++ 容器，深入理解了它们的特性和使用场景。从文件读取、单词索引构建到查询功能实现，每个环节都展示了容器在数据管理和处理中的重要作用。