后端系统开发之面试和工作中的map

map是C++ STL中的关联容器，存储的是键值对（Key-Value)，可以通过key快速索引到value。map容器中的数据是自动排序的，其排序方式是严格的弱排序（stick weak ordering），即在判断Key1和Key2的大小时，使用“<”而不是“<=”。map 使用二叉搜索树实现，STL map的底层实现是红黑树。

map有几个值得注意的地方：map的赋值运算是深拷贝，即调用map_a = map_b后，map_a中的元素拥有独立的内存空间。map[]运算比较有意思，当元素不存在的时候会插入新的元素；在map中查找key是否存在时可以用find或count方法，find查找成功返回的是迭代器，查找失败则返回mymap.end()，说明该key不存在；map中的key不允许重复，其count方法只能返回0或1。

map可以做什么？来看一个非常经典的算法面试题：有一个包含100万个整数的大文件，文件的每一行都是一个int型数字，那么如何找到其中出现次数最多的10个数？

从数据存储方面分析，通常一个int是4个字节，100万个int约为4MB字节。在处理这个问题时，需要记录每个整数出现的次数，次数也用一个int来存储，因此总共需要约8MB字节的内存。从数据处理方面分析，可以用一个Key和Value都为int的map容器来存储数据，通过逐行扫描文件，将文件中的整数作为key保存到map中，对应的value为其在文件中出现次数，这样就完成了数据输入。

对于求N个数中的最大K个数问题，是典型的top K问题，其解决方案是利用一个大小为K的数组构建小顶堆，然后依次对N个数中的元素和堆顶元素做比较，如果满足条件则替换堆顶元素，并重新构建小顶堆，否则处理下一个数据。待所有数据都处理完毕后，小顶堆中的数据集合即为最大的K个数，最后通过堆排序输出即可。

Talk is cheap，show me the code。

#include <string>
#include <vector>
#include <map>
#include <algorithm>   // make_heap算法
#include <cstdio>
#include <string.h>
#include <sys/time.h>

// 从文件中读取ID值，保存到map中
int ReadDataFile(const std::string &file_name, 
	             std::map<int, int> &map_result) {
  FILE *fp = fopen(file_name.c_str(), "r");
  if (fp == NULL) {
  	perror("Open file fail");
  	return -1;
  }
  map_result.clear();
  char buf[100];
  int id;
  while (true) {
  	memset(buf, 0, sizeof(buf));
  	if (fgets(buf, sizeof(buf), fp) == NULL) {
  	  break;
  	}
    id = atoi(buf);
    ++map_result[id];  // 记录ID出现次数
  }
  fclose(fp);
  return 0;
}

// 最终结果
typedef struct Result {
  int id;      // ID值
  int times;   // 该ID值出现的次数

  Result() {
  	id = 0;
  	times = 0;
  }
  // 根据ID出现次数比较大小
  bool operator>(const Result &other) const {
  	return times > other.times;
  }
}Result;

// 从map中获取top k的值，并保存到存储Result对象的vector容器中
void GetTopK(std::map<int, int> &map_result, 
	         std::vector<Result> *final_result, 
	         int k) {
  // k值可能比map_result中的元素个数要多
  size_t min_k = std::min((int)map_result.size(), k);
  std::vector<Result> heap;
  heap.resize(min_k);
  // 创建一个小顶堆，即出现次数最少的ID在堆顶位置
  // make_heap默认创建的是大顶堆，第三个参数是less
  std::make_heap(heap.begin(), heap.end(), std::greater<Result>());

  Result tmp;
  for (auto &it : map_result) {
    tmp.times = it.second;
    // 只需要处理ID出现次数大于堆顶位置元素的情况
    if (tmp.times < heap[0].times) {
      continue;
    }
    tmp.id = it.first;
    heap[0] = tmp;
    std::make_heap(heap.begin(), heap.end(), std::greater<Result>());
  }
  std::sort_heap(heap.begin(), heap.end(), std::greater<Result>());
  final_result->clear();
  final_result->swap(heap);
}

// 直接排序
void DirectSort(std::map<int, int> &map_result, 
	            std::vector<Result> *final_result,
	            int k) {
  std::vector<Result> result;
  Result tmp;
  for (auto &it : map_result) {
    tmp.id = it.first;
    tmp.times = it.second;
    result.push_back(tmp);
  }
  std::sort(result.begin(), result.end(), std::greater<Result>());
  final_result->clear();
  final_result->swap(result);
  // k值可能比map_result中的元素个数要多
  size_t min_k = std::min((int)map_result.size(), k);
  final_result->resize(min_k);
}

// 获取微秒时间
long GetUsTime() {
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_sec * 1000000 + tv.tv_usec;
}

int main(int argc, char **argv) {
  // 读取文件数据并保存到map
  const std::string file_name = "test.data";
  std::map<int, int> map_result;
  int ret = ReadDataFile(file_name, map_result);
  if (ret < 0) {
  	printf("ERROR: ReadDataFile fail\n");
  	return -1;
  }
  printf("map_result size:%lu\n", map_result.size());

  // 获取出现次数最多的10个ID值
  std::vector<Result> final_result;
  long start = GetUsTime();
  GetTopK(map_result, &final_result, 10);
  long end = GetUsTime();
  printf("GetTopK used time: %ldms\n", (end - start)/1000);
  for (auto &it : final_result) {
  	printf("id: %6d, times: %d\n", it.id, it.times);
  }

  // 直接排序
  final_result.clear();
  start = GetUsTime();
  DirectSort(map_result, &final_result, 10);
  end = GetUsTime();
  printf("DirectSort used time: %ldms\n", (end - start)/1000); 
  for (auto &it : final_result) {
  	printf("id: %6d, times: %d\n", it.id, it.times);
  }
  return 0;
}

#include <iostream>
#include <cstdio>
#include <unistd.h>

int WriteDataFile() {
  const int MAX_ID = 999999;
  const int MAX_LINES = 2000000;
  FILE *fp = fopen("test.data", "w");
  if (fp == NULL) {
  	perror("fopen test.data");
  	return -1;
  }	
  srand(time(NULL));
  for (int i = 0; i < MAX_LINES; ++i) {
  	fprintf(fp, "%ld\n", random() * random() % MAX_ID);
  }
  fclose(fp);
  return 0;
}

int main(int argc, char **argv) {
  WriteDataFile();
  return 0;
}

map中的元素是按key排序的，这个题目中其实不需要对key进行排序，C++11提供了基于哈希实现的map容器unordered_map，其访问元素的效率比map要高一些，来看一下将map替换为unordered_map后的性能比较。

另外，这个面试题目有非常多的玩法和变种，例如将数字总数100万改成20个亿，同时限制内存使用不超过2GB，大家可以思考一下解决思路。

map功能强大，它的作用当然不只在于解决面试题目，在一个大型后端系统中，几乎到处都能看到map的身影。例如，面试题中的出现次数最多的数字可以想象为频繁非法访问的黑名单ID，可以用一个map来保存黑名单ID和其访问次数，那么如何使用这个map呢？假如有一个保存了很多ID的vector，里面可能有黑名单ID，在处理数据的时候需要将黑名单ID剔除，代码可以这么写：

void FilterBlackID(const std::map<int, int> &black_list,
	               std::vector<int> *ids) {
  if (black_list.empty()) {
  	return;
  }
  auto it = ids->begin();
  while (it != ids->end()) {
  	if (black_list.find(*it) != black_list.end()) {
  	  ids->erase(it);
  	} else {
  	  ++it;
  	}
  }
}

想要掌握更多的map原理和使用技巧，推荐大家阅读《C++ Primer》或者网上搜索“C++ map”相关的博客文章，然后主动练习，不断丰富自己的开发武器库。