Nested std :: maps

Question

Предположим, у меня есть тип, который я назову NamedNestedMap

std::map<std::string, std::map<std::string, NamedNestedMap> >

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

Тип Value совпадает с родительским типом, который в момент, когда мне нужно сослаться на него, не полностью объявлен.

Как вы объявляете что-то вроде этого вложенного ...

Я даже не могу напечатать первый, чтобы я мог включить его во второй, потому что он неполный

Рекурсия будет искать что-то на карте, когда она найдет это, рекурсивно оценивать значение этого объекта. Часть алгоритма кажется довольно простой, часть объявления здесь более тупая. Я не пытаюсь перебрать карту карт, просто используй map.find, рекурсируй и используй map.find снова.

Answer 1

Вам придется использовать указатели (естественно, поскольку в противном случае рекурсия никогда не прекратится - вам всегда понадобится еще одна пустая карта):

struct NestedMap;
struct NestedMap : std::map<std::string, NestedMap*> {};

Естественно, вы, вероятно, захотите использовать shared_ptr или что-то подобное для управления памятью, а не необработанные указатели.

Answer 2

Создать структуру, представляющую узел.

struct Node {
    std::map<std::string, Node *> children;
};

Конечно, вы можете сделать его классом и скрыть данные и тому подобное.

Answer 3

Полагаю, вы хотите иметь вложенную карту глубины n:

template<class key_type, class val_type, int nest_depth>
struct nest
{
typedef std::map<key_type, typename nest<key_type, val_type, 
                nest_depth-1>::map_type> map_type;
};

template<class key_type, class val_type>
struct nest<key_type, val_type, 0>
{
    typedef std::map<key_type, val_type> map_type;
};

Используйте это так:

nest<std::string, std::string, 2> nested_map;

Answer 4

Вы не можете объявить рекурсивную структуру.

Лучшее, что вы, вероятно, могли бы сделать, это иметь карту карты указателя.

Answer 5

Похоже, вы хотите сделать что-то вроде этого:

class Node {
    ...

    std::map<std::string, Node*> children;
}

Здесь у каждого Node есть карта «детей» на карте, и у этих детей могут быть дети и т. Д.

Answer 6

Проблема в том, что у вашего определения типа для NamedNestedMap нет конца в его рекурсивной структуре. Расширение шаблона для NamedNestedMap будет бесконечным, и поэтому нет способа представить его в коде.

Answer 7

Я думаю, что создание рекурсивной структуры может принести вам проблемы. Просто используйте карты нормалей, например так:

#include <map>
#include <string>

using namespace std;

int main() {
    map<string, map<string, string> > nest;
    nest["first"]["second"] = "Hello nest!";
    printf("%s\n", nest["first"]["second"].c_str());
    return 0;
}

А вот и исполнение:

$ g++ ./nest.cpp -o nest.out -ansi -pedantic -std=c++98
$ ./nest.out
Hello nest!
$

Answer 8

Это, кажется, компилируется для меня:

#include <map>
#include <string>

struct RecMap
{
    std::map<std::string, RecMap> m;
};

int main()
{
    RecMap rec;
    rec.m["first"] = RecMap();
    rec.m["first"].m["second"] = RecMap();
}

Не уверен на 100%, является ли это законным (например, можете ли вы иметь класс X, который содержит vector<X> в качестве члена?). Здесь рекурсия на самом деле не бесконечна, поскольку в конечном итоге вы столкнетесь с RecMap, содержащим пустую карту.

Редактировать: эта статья обсуждает ситуацию. Вывод: не определено. К сожалению.

Answer 9

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