c++ - 如何使用 C++ 中的堆栈、队列或 BST 对文件中的记录进行排序？

Question

如果您有一个包含以下记录的 .dat 文件：

805816899 Andrew
803975268 Bob
912684297 Jeff
123546789 Louis
751354687 Kevin

为了按 ID 号对列表进行排序然后写入屏幕，最简单的数据结构是什么？我认为 BST 最有意义并且最有效，但是在处理这样的小文件时，堆栈会更容易和更快。

另外，你将如何实现它？

Answer 1

最简单的方法是使用 BST 对它们进行排序，将它们放在std::map<int, std::string>. 这是一个内部使用 BST 的自排序数据结构（尽管标准没有明确指定）。如果您不想查找，则可以使用std::set用户定义的类型来代替（请参阅下一段）。

如果要将它们存储在类似数组的平面结构中，可以创建一个小结构来保存信息，将其实例存储在 中std::vector，并结合使用合适的比较函数进行std::sort排序。

英国夏令时：

#include <string>
#include <map>
std::map<int, std::string> m;
m[805816899] = "Andrew";
m[803975268] = "Bob";

等等。

类似数组的解决方案：

struct Foo 
{ 
  Foo(int ID, const std::string& name) : ID(ID), name(name) {}
  int ID; 
  std::string name;
};
// comparison for sorting
bool comp(const Foo& lhs, const Foo& rhs) { return lhs.ID < rhs.ID; }

#include <vector>
#include <algorithm>
....
std::vector<Foo> v;
v.push_back(Foo(805816899, "Andrew"));
v.push_back(Foo(803975268, "Bob"));
// add more entries
std::sort(v.begin(), v.end(), comp);

Answer 2

我认为，trie是实现整个排序的最简单方法，如果 id 的长度是恒定的，它是 O(n)。

#include <iostream>
#include <cassert>
#include <string>

class node {
  bool final;
  union {
    node *next[10];
    char *name;
  };
  node *get_at(int index)
  {
    assert(!final);
    return next[index] ? next[index] : (next[index] = new node);
  }

public:
  node() : final(false) { std::fill(next, next+10, (node*)0); }
  ~node() {
    if (final)
      delete name;
    else
      for (int i=0; i<10; ++i)
        delete next[i];
  }

  void insert(const char *id, std::string const& s)
  {
    if (*id) {
      get_at(*id - '0')->insert(id+1, s);
    } else {
      final=true;
      name = new char[s.size()+1]();
      std::copy(s.begin(), s.end(), name);
    }
  }

  void print_all(std::ostream& os) const
  {
    if (final)
      os << name << '\n';
    else
      for (int i = 0; i < 10; ++i)
        if (next[i])
          next[i]->print_all(os);
  }
};

int main()
{
  node top;
  for (std::string id, name; std::cin >> id >> name;)
    top.insert(id.c_str(), name);
  top.print_all(std::cout);
}