[实习笔记] 字符串练习 （将大量的字符串用int值编码，然后通过int值二分快速查找某个字符串）

免责声明：
本文章是实习期间的C++练习题目，可能会存在大量错误，文章仅作为个人笔记供作者自己方便观看.

介绍

在一个游戏里，可能会出现大量的NPC, 这些NPC有很多都是相同的名字.
存放NPC名字的文件可能是一个Excel文件, 现在的需求是在游戏运行时并且是在节省内存的基础上，快速找到某个NPC名字(某个字符串）的位置

分析

为了节省内存，我们不能使用string类型来存储字符串，因为string类型占用内存消耗太大了

在32位下，string占28个字节，在64位下，string占用40个字节（VS）
（不同的编译环境是不一样的）

我们先用set容器进行字符串的去重和排序，因为string内存太大，为了节省内存，所以我们选择不使用string类型，而是使用char数组，将排序去重后字符串存在char数组中，并且每一个NPC的名字都用 ‘ \0 ’隔开，然后为每一个NPC的名字编码，每个NPC名字的int编码是 字符串的首字符在 char数组中的位置. 因为字符串已经排序了，并且编码也是递增的，所以此时我们可以通过int编码对字符串使用二分操作.

完整代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<fstream>
#include<algorithm>
#include<set>
using namespace std;string RandString()
{char ch[500] = { 0 };int len = rand() % 13 + 4;for (int i = 0; i <= len; i++){ch[i] = rand() % 26 + 'A';}return ch;
}void Init()
{std::string Result;std::vector<std::string> Seed;for (int i = 1; i <= 5000; ++i){Seed.emplace_back(RandString());}for (int i = 1; i <= 10000; ++i){Result.append(Seed[rand() % 5000]);Result.append("\r\n");}FILE* fl = fopen("data.txt", "wb");fwrite(Result.c_str(), sizeof(Result), 100, fl);fclose(fl);
}/上面都是准备阶段，创建一个有字符串的TXT文件.
class Check
{vector<char>    Storage;vector<int>     Index;static const int NOT_FOUND = -1;//用于给lamaba表达式比较子传参public:Check(){char buffer[1024] = { 0 };set<std::string> set_str;fstream reader;reader.open("data.txt");while (reader >> buffer){set_str.insert(buffer);}for (auto it : set_str){for (int i = 0; i < it.size(); ++i){Storage.emplace_back(it[i]);}       Storage.emplace_back('\0');}int id = 0;for (auto i : set_str){Index.push_back(id);id += i.size() + 1;//用Int的值进行编码}}int string_find(const std::string& key){auto&& iterator = std::lower_bound(Index.begin(), Index.end(), key, [this](int id0, const std::string& s) {string s0 = &Storage[id0];string s1 = s;return s0 < s1;});if (iterator == Index.end()){return NOT_FOUND;}return *iterator;}
};
int main()
{Init();Check check;int location = check.string_find("ANDTBBZEGQTZED");cout << "字符串的位置：" << location << endl;}