C++ 中的分层枚举

Question

我正在研究消息解析器/生成器子系统。我正在创建一个自动生成器，它使用包含有关该协议的所有信息（包括枚举列表）的数据库来生成代码。我遇到的一件事是需要分层枚举。

更新

（我试图通过不描述完整问题来简化事情，但下面的评论很明显地表明我因简化太多而犯了错误。）

正在使用的数据库将将事物存储为简化的字符串（客户决定），但协议只讲“字节三元组”（又名分层枚举）。完整的问题可以描述如下：

给定一组唯一字符串，每个字符串对应一个唯一的三元组，1) 查找任何给定字符串的三元组，和 2) 查找任何给定三元组的字符串。确保考虑“未定义”和“无声明”枚举（没有与之关联的字符串）。 [正如一位发帖者指出的那样，是的，这很疯狂。]

（警告：我已经研究 C++ 十多年了，但去年我一直在研究 Java - 我的 C++ 可能是“损坏”。）

因此，使用一个公认的人为示例，给出：

// There is only one category
// POP= "P", COUNTRY= "K", CLASSICAL= "C"
enum Category {POP, COUNTRY, CLASSICAL};

// There is one Type enum for each Category.
// ROCK= "R", BIG_BAND = "B", COUNTRY_POP= "C" 
enum PopType {ROCK, BIG_BAND, COUNTRY_POP};
enum CountryType {CLASSICAL_COUNTRY, MODERN_COUNTRY, BLUEGRASS, COUNTRY_AND_WESTERN};
// ...

// There is one Subtype for each Type
// EIGHTIES= "E", HEAVY_METAL= "H", SOFT_ROCK= "S"
enum RockSubType { EIGHTIES, HEAVY_METAL, SOFT_ROCK};
// ...

当我得到 0, 0, 0（流行、摇滚、八十年代）时，我需要将其翻译为“PRE”。相反，如果我在数据库中看到“PC”，则需要将其作为 0、2（Pop、Country、NULL）发送出去。

此时我公然忽略“未定义”和“无声明”。从字符串生成三元组似乎很简单（使用无序映射，字符串到三元组）。从三元组生成字符串（可能在我知道的大多数“枚举技巧”都不起作用：例如，类型重复值——每个类型枚举从零开始——所以我无法索引基于数组在 。

乍一看，它似乎是一个相当直接的“is-a”关系，但这是行不通的，因为这种情况是双向的 导航非常简单，并且适用于类层次结构；不幸的是，采用其他方式则不是那么简单

——我必须生成代码——因此这可能会消除任何 XML。它也必须是“合理的”解决方案。 “Java 解决方案”涉及使用受保护的静态变量、在构造时初始化以及抽象基类；但是，我不相信这在 C++ 中有效（初始化顺序等）。另外，从美学上来说，我觉得这应该......更“const”。我见过的其他解决此问题的代码使用联合，显式列出联合中的所有枚举类型。

我唯一能想到的就是使用模板专业化和显式专业化，但我不知所措。我对此进行了网络搜索，但没有发现任何内容可以告诉我它是否有效。不过，如果可以通过联合来完成，那么难道不能通过模板专业化来完成吗？

是否可以使用模板、专业化、显式专业化来做这样的事情？我是否缺少另一个更明显的解决方案（即我忘记的设计模式）？

哦，在我忘记之前——解决方案必须是可移植的。更具体地说，它必须在 Windows (Visual Studio 2010) 和 Redhat Enterprise 6/Centos 6 (GCC 4.4.4 IIRC) 上运行。

而且，免得我忘记，这个协议非常庞大。理论上的最大值约为 133,000 个条目；一旦我包含“未定义”和“无声明”，我可能会有那么多条目。

谢谢。

Answer 1

实际上，你现在有点手头了。

我的建议意味着首先使用 3 个枚举：

• 类别 类型
• 子
• 类型

各种类型或子类型之间（首先）没有区别（我们只是将它们全部放在同一个篮子中）。

然后，我将简单地使用一个结构：

struct MusicType {
  Category category;
  Type type;
  SubType subtype;
};

并定义一个简单的有效类型set：

struct MusicTypeLess {
  bool operator()(MusicType const& left, MusicType const& right) const {
    if (left.category < right.category) { return true; }
    if (left.category > right.category) { return false; }

    if (left.type < right.type) { return true; }
    if (left.type > right.type) { return false; }

    return left.subtype < right.subtype;
  }
};

MusicType MusicTypes[] = {
  { Category::Pop, Type::Rock, SubType::EightiesRock },
  ...
};

// Sort it on initialization or define in sorted during generation

然后你可以定义简单的查询：

typedef std::pair<MusicType const*, MusicType const*> MusicTypeRange;

MusicTypeRange listAll() {
  return MusicTypeRange(MusicTypes, MusicTypes + size(MusicTypes));
}

namespace {
  struct MusicTypeCategorySearch {
    bool operator()(MusicType const& left, MusicType const& right) const {
      return left.category < right.category;
    }
  };
}

MusicTypeRange searchByCategory(Category cat) {
  MusicType const search = { cat, /* doesn't matter */ };
  return std::equal_range(MusicTypes,
                          MusicTypes + size(MusicTypes),
                          search,
                          MusicTypeCategorySearch());
}

namespace {
  struct MusicTypeTypeSearch {
    bool operator()(MusicType const& left, MusicType const& right) const {
      if (left.category < right.category) { return true; }
      if (left.category > right.category) { return false; }

      return left.type < right.type;
    }
  };
}

MusicTypeRange searchByType(Category cat, Type type) {
  MusicType const search = { cat, type, /* doesn't matter */ };
  return std::equal_range(MusicTypes,
                          MusicTypes + size(MusicTypes),
                          search,
                          MusicTypeTypeSearch ());
}

// little supplement :)
bool exists(MusicType const& mt) {
  return std::binary_search(MusicTypes, MusicTypes + size(MusicTypes), mt);
}

因为数组是排序的，所以操作很快（log N），所以它应该顺利。

Answer 2

我认为音乐类应该包含子流派...（has-a）也称为聚合。

Answer 3

叶子 ->根导航非常简单，适合类层次结构；不幸的是，走另一条路并不是那么直截了当。

我不太确定首先使用枚举会获得什么价值。是否有令人信服的理由不只是发明一个 Category 类，然后将它们的实例连接在一起来模拟您想要实现的目标？ （我想起了 Qt 状态机框架...）

在我看来，它的好处在于它非常简单，并且易于根据您的需求变化进行调整。这是无聊的代码。您并没有真正推动该语言的编译时功能。但你说这是生成的代码，所以不必担心有人引入具有循环类别层次结构的错误。只要确保不会生成这样的东西即可。

更新好的，我阅读了您的场景更新，听起来您确实正在此处查看数据库任务。为此，我什至没有想到“枚举”这个词。你考虑过 SQLite 吗？

http://en.wikipedia.org/wiki/SQLite

不过，抛开在哪里的问题你得到了 133,000 种音乐流派的疯狂列表，我修改了我的代码，为你提供了 C++ 如何处理这种规模的运行时对象的具体性能指标。你最终会最大限度地发挥作用，但在大多数机器上它仍然可以相当快...尝试一下：

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cstdlib>
using namespace std;

class Category {
private:
    string name;
    Category* parent;
    set<Category*> children;
private:
    static set<Category*> allCategories;
    static vector<Category*>* allCategoriesVector;
public:
    Category (string name, Category* parent) :
        name (name), parent (NULL)
    {
        resetParent(parent);
    }
    void resetParent(Category* newParent) {
        if (parent) {
            parent->children.erase(this);
            if (newParent == NULL) {
                allCategories.erase(this);
                if (allCategoriesVector != NULL) {
                    delete allCategoriesVector;
                    allCategoriesVector = NULL;
                }
            }
        } else {
            if (newParent != NULL) {
                allCategories.insert(this);
                if (allCategoriesVector != NULL) {
                    allCategoriesVector->push_back(this);
                }
            }
        }
        set<Category*>::iterator i = children.begin();
        while (i != children.end()) {
            (*i)->parent = NULL;
            i++;
        } 

        if (newParent) {
            newParent->children.insert(this);
        }

        parent = newParent;
    }
    Category* getRoot() {
       Category* result = this;
       while (result->parent != NULL) {
           result = result->parent;
       }
       return result;
    }
    const string& getNamePart() const {
        return name;
    }
    string getNamePath() const {
        if (parent) {
            return parent->getNamePath() + ":" + getNamePart();
        } else {
            return getNamePart();
        }
    }
    static const vector<Category*>& getAllCategoriesVector() {
        if (allCategoriesVector == NULL) {
           allCategoriesVector = new vector<Category*> (
               allCategories.begin(), allCategories.end()
           );
        }
        return *allCategoriesVector;
    }
    static Category* randomCategory() {
        if (allCategories.empty())
            return NULL;

        // kids: don't try this at home if you want a uniform distribution
        // http://stackoverflow.com/questions/5008804/generating-random-integer-from-a-range
        return getAllCategoriesVector()[rand() % allCategories.size()];
    }
    virtual ~Category() {
        resetParent(NULL);
    }
};
set<Category*> Category::allCategories;
vector<Category*>* Category::allCategoriesVector = NULL;

class CategoryManager {
public:
    Category Root;
        Category Pop;
            Category Rock;
                Category EightiesRock;
                Category HeavyMetal;
                Category SoftRock;
            Category CountryPop;
            Category BigBand;
        Category Country;
        Category Classical;
        Category Jazz;

private:
    set<Category*> moreCategories;
public:
    CategoryManager (int numRandomCategories = 0) :
        Root ("Category", NULL),
            Pop ("Pop", &Root),
                Rock ("Rock", &Pop),
                    EightiesRock ("EightiesRock", &Rock),
                    HeavyMetal ("HeavyMetal", &Rock),
                    SoftRock ("SoftRock", &Rock),
                CountryPop ("CountryPop", &Pop),
                BigBand ("BigBand", &Pop),
            Country ("Country", &Root),
            Classical ("Classical", &Root),
            Jazz ("Jazz", &Root)
    {
        // claim is that there are "hundreds" of these
        // lets make a bunch of them starting with no parent
        for (int i = 0; i < numRandomCategories; i++) {
            stringstream nameStream;
            nameStream << "RandomCategory" << i;
            moreCategories.insert(new Category(nameStream.str(), NULL));
        }

        // now that we have all the categories created, let's
        // reset their parents to something chosen randomly but
        // keep looking until we find one whose path goes up to Root
        set<Category*>::iterator i (moreCategories.begin());
        while (i != moreCategories.end()) {
            (*i)->resetParent(Category::randomCategory());
            i++;
        }
    }
    virtual ~CategoryManager () {
        set<Category*>::iterator i = moreCategories.begin();
        while (i != moreCategories.end()) {
            delete *i;
            i++;
        }
    }
};

int main() {
    CategoryManager cm (133000);

    // how to get to a named category
    cout << cm.EightiesRock.getNamePath() << "\n" << "\n";

    // pick some random categories to output
    for (int i = 0; i < 5; i++) {
        cout << Category::randomCategory()->getNamePath() << "\n";
    }

    return 0;
}

在我的机器上，这很快就吐出来了：

Category:Pop:Rock:EightiesRock

Category:Pop:Rock:HeavyMetal:RandomCategory0:RandomCategory6:RandomCategory12:RandomCategory95:RandomCategory116:RandomCategory320:RandomCategory358:RandomCategory1728:RandomCategory6206:RandomCategory126075
Category:Country:RandomCategory80:RandomCategory766:RandomCategory2174
Category:Country:RandomCategory22:RandomCategory45:RandomCategory52:RandomCategory83:RandomCategory430:RandomCategory790:RandomCategory860:RandomCategory1628:RandomCategory1774:RandomCategory4136:RandomCategory10710:RandomCategory13124:RandomCategory19856:RandomCategory20810:RandomCategory43133
Category:Pop:Rock:HeavyMetal:RandomCategory0:RandomCategory5:RandomCategory138:RandomCategory142:RandomCategory752:RandomCategory2914:RandomCategory9516:RandomCategory13211:RandomCategory97800
Category:Pop:CountryPop:RandomCategory25:RandomCategory63:RandomCategory89:RandomCategory2895:RandomCategory3842:RandomCategory5735:RandomCategory48119:RandomCategory76663

我仍然会说数据库是你在这里寻找的答案，但与此同时，您会惊讶地发现如今编译器的滥用程度如此之大。每行都是一个对象声明的 133K 文件比听起来更容易处理。

Answer 4

你的查找是运行时的，所以我真的不认为很多静态类型会对你有多大帮助。我相信如果您也确实想要它们，您可以将它们写在下面的上面。

我不认为程序员会在日常编码中直接指定这些。他们将接受运行时生成的值并对其进行转换？

鉴于这个假设，我将对枚举进行非规范化。当 switch 语句缺少其中一个值时，这可能需要一些权衡才能获得警告。

struct MusicType {
  enum EnumValue {
    ROOT = 0
    ,Pop
    ,Pop_Rock
    ,Pop_Rock_EightiesRock
    ,Pop_Rock_HeavyMetal
    ,Pop_Rock_SoftRock
    ,Pop_CountryPop
    ,Pop_BigBand
    ,Country
    ,Classical
    ,Jazz
  };
  std::string getLeafString(EnumValue ev) {
    case (ev) {
      case Pop:         return "Pop";
      case Pop_Rock:    return "Rock";
      // ...
      default:
        throw std::runtime_error("Invalid MusicType (getLeafString)");
    }
  }
  // you could write code to do this easily without generating it too
  std::string getFullString(EnumValue ev) {
    case (ev) {
      case Pop:         return "Pop";
      case Pop_Rock:    return "Pop::Rock";
      // ...
      default:
        throw std::runtime_error("Invalid MusicType (getFullString)");
    }
  }

};

那么你需要绘制你的关系图。听起来关卡的数量是固定的，但是当这种假设被打破时，修复起来的成本就非常昂贵。

有几种方法可以解决这个问题。我认为数据结构是最容易实现的，尽管你可以做一个巨大的转换。我认为对于类似的性能来说这会更麻烦。实际上，switch 语句只是代码段中的一个映射，不过，请选择你的毒药。

我喜欢解决这样的问题，一次只能解决一个级别。这使您可以拥有任意数量的级别。它使最低抽象级别变得更加简单。它确实让您编写更多的“中间件”，但这应该更容易实现。

void getChildren(MusicType::EnumValue ev, std::vector<MusicType::EnumValue> &children) {
  typedef std::multimap<MusicType::EnumValue, MusicType::EnumValue> relationships_t;
  typedef std::pair<MusicType::EnumValue, MusicType::EnumValue> mpair_t;
  static relationships_t relationships;
  static bool loaded = false;
  if (!loaded) {
    relationships.insert(mpair_t(MusicType::Pop, MusicType::Pop_Rock));
    relationships.insert(mpair_t(MusicType::Pop_Rock, MusicType::Pop_Rock_EightiesRock));
    // ..
  }
  // returning these iterators as a pair might be a more general interface
  relationships::iterator cur = relationships.lower_bound(ev);
  relationships::iterator end = relationships.upper_bound(ev);
  for (; cur != end; cur++) {
    children.push_back(cur->second);
  }
} 

MusicType::EnumValue getParent(MusicType::EnumValue ev) {
  case (ev) {
    case Pop:         return MusicType::ROOT;
    case Pop_Rock:    return MusicType::Pop;
    // ...
    default:
      throw std::runtime_error("Invalid MusicType (getParent)");
    }
}

像这样分离它的一个重要部分是，您可以为它们编写任何您想要的组合助手，而不必过多担心结构。

对于 GUI 反馈，这应该足够快。如果您需要更快，那么您也许可以进行一些控制反转以避免一些副本。但我不认为我会从那里开始。

您可以添加额外的功能，而无需在内部进行太多更改，这通常是我对生成代码的主要关注点。开放/封闭原则对于生成的代码极其重要。

Answer 5

我无法理解你的意图，但这是在黑暗中随机拍摄的。 MusicCategory 是一个保存 Enum value 中的值的类。 PopTypes 公开继承自 MusicCategory，RockTypes 也继承自 PopTypes。只要程序仅存储/传递 MusicCategory 类型，您就可以将任何派生类类型的所有类型分配给它。因此，您可以拥有 MusicCategory Cat = RockTypes::SoftRock;，并且如果仔细定义枚举，它甚至会适当地设置 Pop/Rock 。

struct MusicCategory{
   enum Enum {
              NoCategory = 0 | (0<<12),  //"0 |" isn't needed, but shows pattern
              Pop        = 0 | (1<<12), 
              Country    = 0 | (2<<12), 
              Classical  = 0 | (3<<12), 
              Jazz       = 0 | (4<<12),
              All        = INT_MAX} value; 
  //"ALL" forces enum to be big enough for subtypes
   MusicCategory(Enum e) :value(e) {} //this makes the magic work
   operator Enum&() {return value;}
   operator const Enum&() const {return value;}
   operator const int() const {return value;}
   const std::string & getString(MusicCategory::Enum category);
};

// Begin types
// This one is a subtype of MusicCategory::Pop
struct PopTypes : public MusicCategory {
   enum Enum { 
       NoType     = MusicCategory::Pop | (0<<6), 
       Rock       = MusicCategory::Pop | (1<<6), 
       CountryPop = MusicCategory::Pop | (2<<6), 
       BigBand    = MusicCategory::Pop | (3<<6),
       All        = INT_MAX};
   const std::string & getString(PopTypes::Enum category);
};
// ...

// Begin subtypes
struct RockTypes : public PopType {
   enum Enum { 
       NoSubType    = PopTypes::Rock | (0<<0),  //"<<0)" isn't needed, but shows pattern
       EightiesRock = PopTypes::Rock | (1<<0),
       HeavyMetal   = PopTypes::Rock | (2<<0), 
       SoftRock     = PopTypes::Rock | (3<<0),
       All          = INT_MAX};
   const std::string & getString(RockTypes::Enum category);
};

int main() {
    MusicCategory Cat; 
    // convertable to and from an int
    Cat = RockTypes::HeavyMetal;
    //automatically sets MusicCategory::Pop and PopTypes::Rock
    bool is_pop = (Cat & MusicCategory::Pop == MusicCategory::Pop);
    //returns true
    std:string str = MusicCategory::getString(Cat);
    //returns Pop
    str = PopTypes::getString(Cat);
    //returns Rock
    str = RockTypes::getString(Cat);
    //returns HeavyMetal
}

Answer 6

首先，感谢大家的帮助。由于这个问题的本质，我实际上无法“按原样”使用任何答案：

• 枚举重复它们的值（每个枚举可以具有与其兄弟姐妹相同的数值，但具有不同的标签和“含义” ）
• 与枚举关联的字符串也可以重复（给定的枚举可以与同级枚举具有相同的字符串，但具有不同的含义）。

我最终找到了 Boost bimaps 和它事实证明，bimap 层次结构可以很好地解决这个问题。对于那些还没有见过它们的人来说，Boost“bimap”是一个双向容器，它使用一对作为键，另一个作为值。

我可以制作一个“整数，字符串”的bimap（在本例中为uint8_t，因为这里的枚举都保证很小），并添加错误的“子枚举”作为相关信息使用 with_info 与 bimap 一起使用。

层次结构代码如下所示：

// Tags
struct category_enum_value {};
struct type_enum_value {};
struct subtype_enum_value {};
struct category_string {};
struct music_type_string {};
struct music_subtype_string {};
struct music_type_info {};
struct music_subtype_info {};

// Typedefs
typedef bimap<
    unordered_set_of< tagged<uint8_t, subtype_enum_value> >,
    unordered_set_of< tagged<std::string, music_subtype_string> >
> music_subtype;
typedef music_subtype::value_type music_subtype_value;

typedef bimap<
    unordered_set_of< tagged<uint8_t, type_enum_value> >,
    unordered_set_of< tagged<std::string, music_type_string> >,
    with_info< tagged<music_subtype, music_subtype_info> >
> music_type_type;
typedef music_type_type::value_type music_type_value;

typedef bimap<
    unordered_set_of< tagged<uint8_t, category_enum_value> >,
    unordered_set_of< tagged<std::string, category_string> >,
    with_info< tagged<music_type_type, music_type_info> > 
> category_type;
typedef category_type::value_type category_value;

出于性能原因，我选择了 unordered_set。由于这严格来说是一个“常量”层次结构，因此我不必担心插入和删除时间。而且因为我永远不会比较顺序，所以我不必担心排序。

要通过枚举值获取类别信息（给定枚举时获取字符串值），我使用 category_enum_value 标签：

    category_type::map_by<category_enum_value>::iterator cat_it = categories.by<category_enum_value>().find(category);
if(cat_it != categories.by<category_enum_value>().end())
{
    const std::string &categoryString = cat_it->get_right();
            // ...

通过使用 type_enum_value< /code> 标记（子类型几乎相同）：

    music_type_type &music_type_reference = cat_it->get<music_type_info>();
    music_type_type::map_by<type_enum_value>::iterator type_it = music_type_reference.by<type_enum_value>().find(type);
    if(type_it != music_type_reference.by<type_enum_value>().end())
    {
               // ... second verse, same as the first ...

要获取给定字符串的枚举值，请将标记更改为 category_string 并使用与以前类似的方法：

    std::string charToFind = stringToFind.substr(0, 1);
    category_type::map_by<category_string>::iterator cat_it = categories.by<category_string>().find(charToFind);
    if(cat_it != categories.by<category_string>().end())
    {
        retval.first = cat_it->get_left();
                    // ... and the beat goes on ...

任何给定级别所需的任何其他信息（例如，菜单项字符串）可以通过将信息类型从 bimap 更改为包含 bimap 的 struct 以及我可能的任何信息来添加需要。

由于这些都是常量值，因此我可以“预先”完成所有艰苦的工作并设计简单的查找函数 - O(1) - 以获得我需要的东西。