С++ Элементы теряются при сохранении на карте

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

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

#include <iostream>
#include <map>
#include <utility>
#include <iterator> // for ostream_iterator

using namespace std;

int main (){

    freopen ("testMap.in", "r", stdin);
    int testCases;
    int i, j;

    int stateOrigin, stateDestination;
    char transitionCharacter ;
    int numberTransitions=8;

        typedef map<pair<int, char>, int> transitions;
        transitions trans;

          for (j=0; j<numberTransitions;j++){
             cin>> stateOrigin>>stateDestination>>transitionCharacter;
             trans.insert(transitions::value_type(std::make_pair(stateOrigin,transitionCharacter), stateDestination ));
        }

        map<pair<int, char>, int>::iterator p = trans.begin();

       for( p = trans.begin(); p != trans.end(); p++ ){
         cout << p->first.first<< " "<<p->first.second<<" "<<p->second<<endl;
       }

return 0;
}

Когда я печатаю все содержимое карты, это говорит мне:

0 a 0
1 b 1
1 c 2
3 d 4
4 d 4

и ожидаемый результат:

0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5 d

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

Удобно менять структуру карты? то есть:

typedef map<pair<int, int>, char> transitions;

c++ map stl dfa
person novaKid    schedule 16.05.2012    source источник
comment
Все ли ключи в вашем наборе данных уникальны? Если нет, попробуйте использовать мультикарту.   -  person alexm    schedule 16.05.2012
comment
Каков ожидаемый результат? std::map не допускает дублирования ключей, поэтому у вас не может быть f.ex. ((0,a),0) и ((0,a),1) в нем одновременно.   -  person jrok    schedule 16.05.2012
comment
@jrok Я редактирую вопрос с ожидаемым результатом.   -  person novaKid    schedule 16.05.2012

Ответы (3)


arrow_upward
2
arrow_downward

Карта — это отношение 1-to-1 между ключом и значением, поэтому она может представлять детерминированный автомат.

Недетерминированный автомат может быть представлен 1-to-many ассоциативным контейнером.

т.е. вам нужен std::multimap или вы можете продолжать использовать std::map с типом значения другого контейнера:

 typedef map<pair<int, int>, vector<char> > transitions;

поэтому вы можете иметь несколько значений char для каждой пары int.

person Luchian Grigore    schedule 16.05.2012
comment
В чем разница между: typedef map <pair <int, int>, char> transitions; и: typedef map<pair<int, int>, vector<char> > transitions; - person novaKid; 16.05.2012
comment
@novaKid Прочитайте последнее предложение ответа. - person Luchian Grigore; 16.05.2012

arrow_upward
1
arrow_downward

Вы можете использовать typedef, это законно.

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

Изменить: Хорошо, проблема в следующем:

map<pair<int, char>, int>::iterator p = trans.begin();

у тебя есть пара. Вы ожидаете увидеть:

0 0 a
0 1 a

Однако ключи: (0, a) и (0, a), поэтому карта игнорирует один.

Вы можете избежать этого, сделав карту как: (изменив порядок int и char)

typedef map<pair<int, int>, char> transitions;
person phantasmagoria    schedule 16.05.2012

arrow_upward
0
arrow_downward

Поскольку карта представляет собой пару, ваша вставка всегда ищет пару‹>, поскольку ваш первый элемент на карте является парой, попробуйте этот код

 trans.insert(std::make_pair(std::make_pair(stateOrigin,transitionCharacter), stateDestination ));
person AwesomeNix    schedule 16.05.2012