unordered_map avec quelque chose qui resemble à un indice

Version imprimable

16/02/2023, 07h55
emmesse

unordered_map avec quelque chose qui resemble à un indice

Bonjour,

comment fait-on pour accéder, par exemple, au troisième pair d'un unordered_multimap avec quelqque chose qui ressemblerai à un indice?

Code:

std::unordered_multimap< std::string , std::vector<std::string> >G;

une idée?
16/02/2023, 08h23
Bktero

Bonjour

Comment accéder au n-ième élément d'une collection dont les éléments ne sont pas numérotés ?

Hum....

C'est quoi le 3e élément si la map est "unordered" ?
16/02/2023, 08h35
emmesse
peut-être qu'il me faut autre chose qu'un unordered multimap.
j'ai ces productions:
Code:

1 2 3 4 5 S -> A a S -> b A -> A c A -> S d A-> epsilon
je voudrais accéder d'une manière simple à l'une de ces productions, et/ou en ajouter une entre deux autres, ou bien encore en modifier une
j'utilisais un vector, mais on m'a dit que je me compliquai le travail avec.
une idée?
16/02/2023, 09h23
dalfab
Si l'ordre des productions doit être conservé, la unordered_multimap<> n'est pas utilisable. Comme l'a indiqué @Bktero les éléments ne sont pas à une position donnée. Dans une unordered_multimap<> :
Code:

1 2 3 4 5 S -> A a S -> b A -> A c A -> S d A-> epsilon
est la même chose que:
Code:

1 2 3 4 5 A-> epsilon A -> A c A -> S d S -> b S -> A a
.Si tu ajoutes un élément (par exemple avec insert()) il se mettra quelque part dans la unordered_multimap<>. Précise mieux ton besoin. Il semble qu'il te faut utiliser la collection qui conserve l'ordre donc c'est plutôt std::vector<>8-)

voici comment je m'y suis pris:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#ifndef GRAMMAIRE_HPP
#define GRAMMAIRE_HPP
 
class grammaire{
public:
  std::vector<std::vector<std::string>>presencerecurs();
  int comptertete(std::string tete);
  int termine(std::string s);
  void parseur();
private:
  std::vector<std::vector<std::string>>grammaire_s;
  std::string axiome;
  std::vector<std::string>terminaux;
  std::vector<std::string>nonterminaux;
  std::vector<std::vector<std::string>>listesnonrecurs;
};
#endif

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include "grammaire.hpp"
 
int main(){
  std::vector<std::vector<std::string>>listerecurs;
  grammaire G;
  G.parseur();
  listerecurs =G.presencerecurs();
  for(auto p:listerecurs){
    for(auto s:p)
      std::cout<<s<<' ';
    std::cout<<std::endl;
  }
  return 0;
}
 
void grammaire::parseur(){
  terminaux={"a","b","c","d","epsilon"};
  nonterminaux={"S","A"};
  grammaire_s={
    {"S","A","a"},     // S -> A a
    {"S","b"},           // S -> b
    {"A","A","c"},     // A -> A c
    {"A","S","d"},     // A -> S d
    {"A","epsilon"}   // A -> epsilon
  };
  axiome="S";
}
 
 
std::vector<std::vector<std::string>>
grammaire::presencerecurs(){
  std::vector<std::vector<std::string>>temporaire,archive;
  std::vector<std::string> unelistenonrecurs;
  int n1,n2;
 
  n1=comptertete(axiome);
  for(int i=0;i<n1;i++){
    unelistenonrecurs.push_back(axiome);
    listesnonrecurs.push_back(unelistenonrecurs);
    unelistenonrecurs.clear();
  }
  for(auto p:grammaire_s){
    temporaire.clear();
    n2=termine(p[0]);//listenonrecursterminé par p[0]
    if(n2!=-1){
      unelistenonrecurs=listesnonrecurs[n2];
      if(std::find(nonterminaux.begin(),nonterminaux.end(),p[1])!=nonterminaux.end()){
	if(std::find(unelistenonrecurs.begin(),unelistenonrecurs.end(),p[1])!=unelistenonrecurs.end()){
	  while(unelistenonrecurs[0]!=p[1])
	    unelistenonrecurs.erase(unelistenonrecurs.begin());
	  archive.push_back(unelistenonrecurs);//recurs gauche détectée
	  listesnonrecurs.erase(listesnonrecurs.begin()+n2);
	  continue;
	}
	else{
	  unelistenonrecurs.push_back(p[1]);
	  n1=comptertete(p[1]);
	  for(int i=0;i<n1;i++)
	    temporaire.push_back(unelistenonrecurs);
	  listesnonrecurs.erase(listesnonrecurs.begin()+n2);
	  listesnonrecurs.insert(listesnonrecurs.end(),temporaire.begin(),temporaire.end());
	}
      }
      else
	listesnonrecurs.erase(listesnonrecurs.begin()+n2);
    }
  }
  return archive;
}
 
int grammaire::termine(std::string fin){
  //retourne l'indice de liste tel que 'fin' soit son dernier symbole
  for(size_t i=0;i<listesnonrecurs.size();i++)
    if(listesnonrecurs[i].back()==fin)
      return i;
  return -1;
}
 
int grammaire::comptertete(std::string s){
  int c=0;
  for(auto &p:grammaire_s)
    if(s==p[0])
      c++;
  return c;
}

Salut,

Ce que tu décrit me fait fortement penser aux collections VB6.
C'est un conteneur qui associe une clef à une valeur.
Les items sont insérés dans l'ordre.
On peut accéder aux items par clef ou par indice.

Tu peux te faire une classe qui ressemble à ceci:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <string>
#include <vector>
#include <utility>
 
class Collection
{
private:
	std::vector<std::pair<std::string, std::string>> mData;
public:
	std::string get(size_t) const;
	std::string get(std::string const&);
	void insert(std::pair<std::string, std::string> const&);
        void remove(size_t);
	void remove(std::string const&);
        size_t size() const;
};
 
#include "Collection.h"
 
std::string Collection::get(size_t index) const
{
	// retourne le 2e element (la valeur) de la paire à l'indice index
}
 
std::string Collection::get(std::string const& key)
{
	// recherche dans mData quel premier element (la clef) des pairs stockées correspond à key
}
 
void Collection::insert(std::pair<std::string, std::string> const&)
{
	// une insertion bête et mechante
}
 
void Collection::remove(size_t index)
{
       // voir commentaire get(size_t index)
}
 
void Collection::remove(std::string const& key)
{
       // voir commentaire get(std::string const& key)
}
 
size_t Collection::size() const
{
	return mData.size();
}

A toi de voir si tu veux des intérateur.

comment récupère-t-on la taille d'un pair, pour utiliser insert?

Code:

1
2
3
4
5
void Collection::insert(std::pair<std::string, std::string> const& p)
{
   mData.insert(mData.end(),taille?,p)
	// une insertion bête et mechante
}

sinon, comme ça, ça compile bien (à part un petit warning):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <string>
#include <vector>
#include <utility>
 
class Collection
{
public:
  std::string get(size_t index) const;
  std::string get(std::string const &key)const;
  void insert(std::pair<std::string, std::string> const &p);
  void remove(size_t index);
  void remove(std::string const &key);
  size_t size() const;
private:
  std::vector<std::pair<std::string, std::string>> mData;
};

Code:

1
2
3
4
VB6.cpp: In member function ‘std::string Collection::get(const string&) const’:
VB6.cpp:17:1: warning: control reaches end of non-void function [-Wreturn-type]
   17 | }
      | ^

en fait, il y a des productions qui ont la même tête, alors je ne saurais pas très bien utiliser la clé

Code:

1
2
3
4
5
6
7
  grammaire_s={
    {"S","A","a"},     // S -> A a
    {"S","b"},           // S -> b
    {"A","A","c"},     // A -> A c
    {"A","S","d"},     // A -> S d
    {"A","epsilon"}   // A -> epsilon
  };

19/02/2023, 12h19
deedolith
Citation:
Envoyé par matser

comment récupère-t-on la taille d'un pair, pour utiliser insert?

Code:

1 2 3 4 5 void Collection::insert(std::pair<std::string, std::string> const& p) { mData.insert(mData.end(),taille?,p) // une insertion bête et mechante }
std::vector, pour inserer une element, c'est la fonction push_back().

Citation:

std::vector, pour inserer une element, c'est la fonction push_back().

oui c'est vrai, suis-je bête.

j'ai oublié collection.cpp dans mon dernier post:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#include "Collection.h"
 
std::string Collection::get(size_t index) const
{
  return mData[index].second;
  // retourne le 2e element (la valeur) de la paire à l'indice index
}
 
std::string Collection::get(std::string const& key)const
{
  size_t taille=size();
  for(size_t i=0;i<taille;i++)
    if(mData[i].first==key)
      return get(i);
  // recherche dans mData quel premier element (la clef) des pairs stockées correspond à key
}
 
void Collection::insert(std::pair<std::string, std::string> const& p)
{
  mData.push_back(p);
  // une insertion bête et mechante
}
 
void Collection::remove(size_t index)
{
  mData.erase(mData.begin()+index);
  // voir commentaire get(size_t index)
}
 
void Collection::remove(std::string const& key)
{
  size_t taille=size();
  for(size_t i=0;i<taille;i++)
    if(mData[i].first==key){
      remove(i);
      break;
    }
  // voir commentaire get(std::string const& key)
}
 
size_t Collection::size() const
{
  return mData.size();
}

je rappelle qu'il y a des productions qui partage la même tête.:

Code:

1
2
3
4
5
6
7
  grammaire_s={
    {"S","A","a"},    // S -> A a
    {"S","b"},        // S -> b
    {"A","A","c"},    // A -> A c
    {"A","S","d"},    // A -> S d
    {"A","epsilon"}   // A -> epsilon
  };

Code:

1
2
3
VB6.cpp:17:1: warning: control reaches end of non-void function [-Wreturn-type]
   17 | }
      | ^

en fait dans mon premier post, je parlais du multi-map tout simplement parce que quelqu'un me l'a conseillé. Mais je m'en sort avec les vector.

19/02/2023, 17h49
deedolith

Tu as oublié les cas défavorable:
- indice supérieur à la taille.
- clef inexistante.
- clef dupliquée.

J'ai oublié de préciser que dans une collection, la clef doit être unique.
Du coup, je ne suis pas sûre que ca corresponde à ton besoin.
Peut-être que ca peut te donner une piste.

Citation:

Du coup, je ne suis pas sûre que ca corresponde à ton besoin.

c'est bien ce que je n'arrête pas de dire. Je m'en sort avec les vector
je redonne le programme présenté à l'un de mes précédent post:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#ifndef GRAMMAIRE_HPP
#define GRAMMAIRE_HPP
 
class grammaire{
public:
  std::vector<std::vector<std::string>>presencerecurs();
  int comptertete(std::string tete);
  int termine(std::string s);
  void parseur();
  void emettre();
private:
  std::vector<std::vector<std::string>>grammaire_s;
  std::vector<std::string>terminaux;
  std::vector<std::string>nonterminaux;
  std::vector<std::vector<std::string>>listesnonrecurs;
};
#endif
 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include "grammaire.hpp"
 
int main(){
  std::vector<std::vector<std::string>>listerecurs;
  grammaire G;
  G.parseur();
  listerecurs =G.presencerecurs();
  for(auto p:listerecurs){
    for(auto s:p)
      std::cout<<s<<' ';
    std::cout<<std::endl;
  }
  return 0;
}
 
void grammaire::parseur(){
  terminaux={"a","b","c","d"};
  nonterminaux={"X","Y","A","B","C","D"};
  grammaire_s={
    {"X","Y"},       // X -> Y
    {"Y","Y","D"},   // Y -> Y D
    {"Y","Y","a"},   // Y -> Y a
    {"Y","b"},       // Y -> b
    {"A","B"},       // A -> B
    {"B","d"},       // B -> d
    {"C","c"},       // C -> c
    {"D","D","c"}    // D -> D C
  };
}
 
 
std::vector<std::vector<std::string>> grammaire::presencerecurs(){
  std::vector<std::vector<std::string>>temporaire,archive;
  std::vector<std::string> unelistenonrecurs;
  int n1,n2;
 
  for(auto p:grammaire_s){
    temporaire.clear();
    n2=termine(p[0]);//indice d'élément de listenonrecurs terminé par p[0]
    if(n2==-1){//si p[0] est absent
      n1=comptertete(p[0]);
      for(int i=0;i<n1;i++){
	unelistenonrecurs.clear();
	unelistenonrecurs.push_back(p[0]);
	listesnonrecurs.push_back(unelistenonrecurs);
      }
      n2=termine(p[0]);
    }
    else
      unelistenonrecurs=listesnonrecurs[n2];
    if(std::find(nonterminaux.begin(),nonterminaux.end(),p[1])!=nonterminaux.end()){
      if(std::find(unelistenonrecurs.begin(),unelistenonrecurs.end(),p[1])!=unelistenonrecurs.end()){
	while(unelistenonrecurs[0]!=p[1])
	  unelistenonrecurs.erase(unelistenonrecurs.begin());
	archive.push_back(unelistenonrecurs);//recurs gauche détectée
	listesnonrecurs.erase(listesnonrecurs.begin()+n2);
	continue;
      }
      else{
	unelistenonrecurs.push_back(p[1]);
	n1=comptertete(p[1]);
	for(int i=0;i<n1;i++)
	  temporaire.push_back(unelistenonrecurs);
	listesnonrecurs.erase(listesnonrecurs.begin()+n2);
	listesnonrecurs.insert(listesnonrecurs.end(),temporaire.begin(),temporaire.end());
      }
    }
    else{
      listesnonrecurs.erase(listesnonrecurs.begin()+n2);
    }
  }
  return archive;
}
 
int grammaire::termine(std::string fin){
  //retourne l'indice de liste tel que 'fin' soit son dernier symbole
  for(size_t i=0;i<listesnonrecurs.size();i++)
    if(listesnonrecurs[i].back()==fin)
      return i;
  return -1;//en cas d'échec
}
 
int grammaire::comptertete(std::string s){
  int c=0;
  for(auto &p:grammaire_s)
    if(s==p[0])
      c++;
  return c;
}

19/02/2023, 21h56
deedolith

Elle représente quoi ta classe grammaire ?
Tu peux nous faire un topo ?
20/02/2023, 02h23
emmesse

j'ai pas encore terminé mais voilà: la grammaire est lue dans un fichier, puis on détecte les récursivités à gauche, on les supprime, on vérifie la factorisation à gauche, puis on vérifie que dans les productions annulables n'aie pas un terminal dans premiers et dans suivant de ce non-terminal
Pour les récursivités à gauche, tout est expliqué ici: https://www.developpez.net/forums/blogs/116855-matser/
21/02/2023, 19h00
deedolith

Si j'ai bien compris le sujet:
Une grammaire est composée de N productions.
Une production a une tête, et 1-N symboles.

On devrait voir ces 3 notions apparaitre dans ton code source, et ce n'est pas le cas.
Revoit ta conception.

A mon avis, 2 classes et des vector devraient suffir.
21/02/2023, 19h19
emmesse

Je vous montrerai quand j'aurai fini.