Иерархические перечисления в C ++ - PullRequest
13 голосов
/ 14 ноября 2011

Я работаю над подсистемой парсера / генератора сообщений. Я создаю автогенератор, который использует базу данных, которая содержит всю информацию об этом протоколе, включая списки enum, для генерации кода. Одна вещь, с которой я столкнулся, - это необходимость иерархических перечислений.

обновлен

(Я пытался упростить ситуацию, не описывая проблему full , но приведенные ниже комментарии дают понять, что я допустил ошибку, упрощая слишком много.)

Используемая база данных будет хранить вещи в виде упрощенных строк (решение клиента), но протокол говорит только о «байтовых триплетах» (или иерархическом перечислении). Полная проблема может быть описана так:

Учитывая набор уникальных строк, каждая из которых соответствует уникальному триплету, 1) найти триплет для любой заданной строки, и 2) найти строку для любого заданного триплета. Убедитесь, что учтены перечисления «Undefined» и «No Statement» (с которыми не связаны строки). [Как заметил один из авторов, да, это безумно.]

(Предостережение: я занимался 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». И наоборот, если я вижу «ПК» в базе данных, его нужно отправить по проводам как 0, 2 (Pop, Country, NULL).

Я явно игнорирую «Undefined» и «No Statement» на этом этапе. Генерация триплета из строки кажется простой (используйте неупорядоченную карту, строка для тройки). Генерация строки из триплета (которая может содержать NULL в последней записи) ... не так много. Большинство известных мне трюков enum не сработает: например, типы повторяют значения - каждое перечисление типов начинается с нуля, поэтому я не могу индексировать массив, основанный на значении Enum для захвата строки.

Что меня заинтересовало, так это отношения. На первый взгляд, это довольно прямолинейные отношения «есть», но это не работает, потому что этот случай двунаправленный. Листовая -> корневая навигация очень прямолинейна и подходит для иерархии классов; к сожалению, идти другим путем не так уж и просто.

Я не могу это «свернуть вручную» - мне нужно сгенерировать код - так что, вероятно, устраняются любые решения на основе XML. Это также должно быть "достаточно быстро". «Решение Java» включает использование защищенных статических переменных, инициализированных при построении, и абстрактных базовых классов; однако я не верю, что это будет работать в C ++ (порядок инициализации и т. д.). Плюс, эстетически, я чувствую, что это должно быть ... больше "const". Другой код, который я видел для решения этой проблемы, использует объединения, явно перечисляя все типы перечислений в объединении.

Единственное, что я могу придумать, это использовать специализацию шаблонов и явную специализацию, но я в растерянности. Я сделал поиск в Интернете по этому вопросу, но я не нашел ничего, что могло бы сказать мне, будет ли это вообще работать. Тем не менее, если это можно сделать с помощью объединения, не может ли это быть сделано с помощью специализации шаблонов?

Можно ли сделать что-то подобное, используя шаблоны, специализацию, явную специализацию? Есть ли другое, более очевидное, решение (то есть шаблон проектирования, который я забыл), которое мне не хватает?

О, прежде чем я забуду - решение должно быть портативным. В частности, он должен работать в Windows (Visual Studio 2010) и Redhat Enterprise 6 / Centos 6 (GCC 4.4.4 IIRC).

И, чтобы я не забыл, этот протокол огромен . Теоретический максимум на это составляет около 133 000 записей; как только я добавлю «Undefined» и «No Statement», у меня, вероятно, будет столько записей.

Спасибо.

Ответы [ 6 ]

9 голосов
/ 14 ноября 2011

По сути, вы немного в затруднении.

Мое предложение подразумевало бы сначала использование 3 перечислений:

  • Категория
  • Тип
  • SubType

Без различия (сначала) между различными типами или подтипами (мы просто бросаем их все в одну корзину).

Тогда я бы просто использовал структуру:

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);
}

Поскольку массив отсортирован, операции выполняются быстро (журнал N), поэтому он должен идти гладко.

1 голос
/ 14 ноября 2011

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

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

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

ОБНОВЛЕНИЕ Хорошо, я читаю обновления вашего сценария, и это действительно похоже на то, что вы смотрите на задачу базы данных здесь. Слово "перечисление" даже не приходит на ум для этого. Вы рассматривали 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
        // /4483972/generatsiya-sluchainogo-tselogo-chisla-iz-diapazona
        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, каждая строка которого является объявлением объекта, более удобна для восприятия, чем кажется.

1 голос
/ 14 ноября 2011

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

0 голосов
/ 18 ноября 2011

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

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

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

Я могу сделать bimap из" integer, string "(в данном случае uint8_t, поскольку все перечисленные здесь значения гарантированно будут небольшими) и добавьте, errr, «sub-enum» в качестве информации, связанной с 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 по соображениям производительности.Поскольку это строго «постоянная» иерархия, мне не нужно беспокоиться о времени вставки и удаления.И поскольку я никогда не буду сравнивать порядок, мне не нужно беспокоиться о сортировке.

Чтобы получить информацию о категориях по значению enum (получить строковые значения при наличии enum), я использую 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) - чтобы получить то, что мне нужно.

0 голосов
/ 15 ноября 2011

У меня проблемы с пониманием вашего намерения, но вот случайный выстрел в темноте.MusicCategory - это класс, который содержит значение в Enum value.PopTypes публично наследуется от MusicCategory, как и RockTypes от PopTypes.Пока программа хранит / передает только MusicCategory типы, вы можете назначать ей все типы из любого из производных типов классов.Таким образом, вы можете иметь MusicCategory Cat = RockTypes::SoftRock;, и если перечисления определены тщательно, он даже установит Pop / Rock соответственно.

0 голосов
/ 15 ноября 2011

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

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

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

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

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...