Иерархические перечисления в С++

Ответ 1

Во-первых, спасибо всем за помощь. Я не мог использовать ни один из ответов "как есть" из-за характера этой проблемы:

• перечисления повторяют свои значения (каждое перечисление может иметь те же числовые значения, что и братья и сестры, но с другой меткой и "значением" )
• строки, связанные с перечислением, также могут быть повторены (данное перечисление может иметь ту же строку, что и родной брат, но с другим смыслом).

В итоге я нашел Boost bimaps, и получается, что иерархия bimap хорошо работает для этой проблемы. Для тех, кто их не видел, Boost `bimap 'является двунаправленным контейнером, который использует любую из пары в качестве ключа, а другой как значение.

Я могу сделать bimap из "integer, string" (uint8_t в этом случае, поскольку все перечисления здесь гарантированы как маленькие) и добавить "под-перечисление", errr, как информацию, связанную с bimap с помощью with_info.

Код иерархии выглядит примерно так:

// 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 (подтип почти идентичен):

    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 на struct, содержащей bimap, и любую информацию, которая может мне понадобиться.

Так как это все постоянные значения, я могу выполнить всю тяжелую работу "вперед" и спроектировать простые функции поиска - O (1) - чтобы получить то, что мне нужно.

Ответ 2

Эффективно, вы находитесь здесь в нескольких местах.

Мое предложение подразумевало бы сначала использование 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), поэтому он должен идти гладко.

Ответ 3

Я думаю, что класс Music должен содержать суб-жанры... (has-a) также называется агрегацией.

Ответ 4

Лист → коренная навигация очень проста и подходит для иерархии классов; к сожалению, идти в другую сторону не так прямо.

Я не уверен, какое значение вы получаете, используя перечисления в первую очередь. Есть ли веские причины не просто изобретать класс Category, а затем объединить экземпляры их для моделирования того, что вы пытаетесь достичь? (Мне напомнили Qt State Machine Framework...)

В моем сознании, хорошая вещь о том, насколько это просто, и легко адаптироваться по мере того, как ваши потребности меняются. Это скучный код. Вы не очень сильно нажимаете на язык компиляции. Но вы говорите, что это сгенерированный код, поэтому не нужно беспокоиться о том, что кто-то вводит ошибки с циклической категориальной иерархией. Просто убедитесь, что такие вещи не генерируются.

UPDATE Хорошо, я прочитал ваши обновления сценариев, и действительно кажется, что вы смотрите на задачу базы данных здесь. Слово "enum" даже не приходит на ум за это. Вы рассматривали SQLite?

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

И все же, отложив в сторону вопрос о том, где вы получаете этот безумный список из 133 000 музыкальных жанров, я изменил свой код, чтобы дать вам конкретный показатель производительности для того, как С++ может обрабатывать объекты времени выполнения этого масштаба. В конечном итоге вы получите максимальные результаты, но на большинстве машин он все равно может быть довольно быстрым... попробуйте:

#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 с каждой строкой, являющейся объявлением объекта, более удобен, чем кажется.

Ответ 5

Ваши поисковые запросы - это время выполнения, поэтому я действительно не думаю, что много статического ввода поможет вам многое. Я считаю, что вы могли бы написать их поверх нижнего, если вы действительно хотели их также.

Я не предполагаю, что программисты будут прямо указывать их в своей повседневной кодировке. Они будут принимать вовремя генерируемые значения и преобразовывать их?

Учитывая это предположение, я бы денормализовал перечисление. У этого могут быть некоторые компромиссы для получения предупреждений о том, когда оператор 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)");
    }
}

Огромная часть этого разделения заключается в том, что вы можете написать любые комбинаторные помощники, которые вы хотите для них, не беспокоясь о структуре слишком много.

Для обратной связи с графическим интерфейсом это должно быть достаточно быстро. Если вам это нужно быстрее, вы можете сделать некоторую инверсию управления, чтобы избежать нескольких копий. Я не думаю, что я бы начал там, хотя.

Вы можете добавить дополнительную функциональность, не меняя слишком много внутренне, что является основной причиной сгенерированного кода. Принцип open/closed чрезвычайно важен для сгенерированного кода.

Ответ 6

У меня возникли проблемы с пониманием ваших намерений, но здесь случайный выстрел в темноте. 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
}