Optimisation qui ne marche pas comme il faut

Bonjour,

sur 3DS il y a un jeu "wakedas" qui est une sorte de rubik's cube mais avec une seule face, et la condition de victoire est que toutes les couleurs soient regroupées ensemble.

Donc au niveau de mon algo, je suis parti d'un bruteforce et j'optimise ce que je peux. Donc l'algo de départ est:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// la grille est dans un vector, pour mes tests je fais les grilles 4×4 (donc 16 valeurs dans mon vector)
bool check_solution(std::vector<unsigned char> board, int remaining_move)
{
    if(remaining_move < 1)
    {
        if(is_solution(board))
            return true;
        return false;
    }

    /* pour tous les coups possibles (il y en a 24 pour une grille 4×4) */ {
        /* effectuer ce coup */
        if(check_solution(board, remaining_move - 1))
            return true; // remonter l'info de victoire
    }
}

Ce code marche à la perfection (enfin je pense), mais il est assez lent car il y a 7,962,624 grilles à vérifier (je me limite à 5 coups pour cette grille, donc 24^5 possibilités).

1^re optimisation: ne pas jouer 2 fois de suite sur la même ligne ou même colonne. là encore, tout se passe bien et on tombe à 4,667,544 grilles vérifiées. Et il me trouve un peu plus de 300 solutions.

2^e optimisation: si on a déjà vérifié une grille, ne pas le refaire, donc j'ai rajouté ceci à ma fonction.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

std::set<std::vector<unsigned char>> cache;
bool check_solution(std::vector<unsigned char> board, int remaining_move)
{
    if(cache.find(board) != cache.end())
    {
        return false;
    }
    cache.insert(board);

    if(remaining_move < 1)
    {
        // comme avant
    }

    // comme avant
}

mais là, c'est le drame. il n'analyse que 9249 grilles et ne trouve aucune solution. Je vois vraiment pas pourquoi. je suis prêt à prendre toutes les idées.

merci.

p.s. si quelqu'un veut voir le 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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197

#include <iostream>
#include <tuple>
#include <vector>
#include <set>

#define YELLOW    1
#define BLUE  2
#define GREEN 4
#define ORANGE    8
#define RED       16
#define MAX_COLOURS 5

bool row_moved(std::vector<unsigned char> & board, int row, int move)
{
  using std::swap;
  // todo: renvoyer "false" si ligne d'une seule couleur
  int row_start = row * 4;
  while(move > 0)
  {
      swap(board[row_start + 3], board[row_start + 2]);
      swap(board[row_start + 2], board[row_start + 1]);
      swap(board[row_start + 1], board[row_start + 0]);
      --move;
  }
  
  return true;
}

bool col_moved(std::vector<unsigned char> & board, int col, int move)
{
  using std::swap;
  // todo: renvoyer "false" si colonne d'une seule couleur
  while(move > 0)
  {
      swap(board[col + 12], board[col + 8]);
      swap(board[col + 8], board[col + 4]);
      swap(board[col + 4], board[col + 0]);
      --move;
  }
  
  return true;
}

bool check_fill(std::vector<unsigned char> board, unsigned char value)
{
  std::vector<unsigned char> zeroes;
  for(int i = 0;i < 16;i++)
  {
      if(board[i] & value)
      {
          zeroes.push_back(i);
          break;
      }
  }
  
  while(zeroes.size() > 0)
  {
      int i = zeroes.back();
      zeroes.pop_back();
      
      int x = i % 4;
      int y = i / 4;
      
      board[i] = 0;
      
      // left
      if(x > 0 && (board[y * 4 + x - 1] & value))
          zeroes.push_back(y * 4 + x - 1);
      // right
      if(x < 3 && (board[y * 4 + x + 1] & value))
          zeroes.push_back(y * 4 + x + 1);
      // up
      if(y > 0 && (board[(y - 1) * 4 + x] & value))
          zeroes.push_back((y - 1) * 4 + x);
      // down
      if(y < 3 && (board[(y + 1) * 4 + x] & value))
          zeroes.push_back((y + 1) * 4 + x);
  }
  
  for(int i = 0;i < 16;i++)
  {
      if(board[i] & value)
      {
          return false;
      }
  }
  
  return true;
}

int checkedGrids = 0;
std::set<std::vector<unsigned char>> cache;
bool check_solution(std::vector<unsigned char> board, std::vector<std::tuple<char, int, int>> moves, int remaining_moves, int colours)
{
  if(cache.find(board) != cache.end())
  {
      return false;
  }
  cache.insert(board);
  
  if(remaining_moves < 1)
  {
      ++checkedGrids;
      if(checkedGrids % 100000 == 0)
          std::cout << checkedGrids << " checkedGrids" << std::endl;
      
      bool filled = true;
      for(int colour = 0;colour < MAX_COLOURS;colour++)
      {
          int colourShifted = 1 << colour;
          if(colourShifted & colours)
          {
              if(!check_fill(board, colourShifted))
              {
                  filled = false;
              }
          }
      }
      
      if(filled)
      {
          int i = 0;
          std::cout << "POTENTIAL SOLUTION FOUND :" << std::endl;
          for(auto & cell : board)
          {
              ++i;
              std::cout << (int)cell << " ";
              if(i % 4 == 0) std::cout << std::endl;
          }
          std::cout << std::endl;
          for(auto & move : moves)
          {
              std::cout << std::get<0>(move) << " " << std::get<1>(move) << " " << std::get<2>(move) << std::endl;
          }
          std::cout << std::endl;
      }
      
      return false;
  }
  
  for(int i = 0;i < 4;i++)
  {
      for(int move = 1;move < 4;move++)
      {
          if(moves.size() == 0 || std::get<0>(moves.back()) != 'r' || std::get<1>(moves.back()) != (i + 1))
          {
              auto gridR = board;
              if(row_moved(gridR, i, move))
              {
                  auto vec = moves;
                  vec.emplace_back('r', i + 1, move);
                  if(check_solution(gridR, vec, remaining_moves - 1, colours))
                  {
                      return true;
                  }
              }
          }
          
          if(moves.size() == 0 || std::get<0>(moves.back()) != 'c' || std::get<1>(moves.back()) != (i + 1))
          {
              auto gridC = board;
              if(col_moved(gridC, i, move))
              {
                  auto vec = moves;
                  vec.emplace_back('c', i + 1, move);
                  if(check_solution(gridC, vec, remaining_moves - 1, colours))
                  {
                      return true;
                  }
              }
          }
      }
  }
  
  return false;
}

int main()
{
  std::vector<unsigned char> board = {
      GREEN,  ORANGE, GREEN,  ORANGE,
      BLUE,   BLUE,   BLUE,   BLUE,
      BLUE,   YELLOW, RED,    BLUE,
      BLUE,   RED,    YELLOW, BLUE,
  };
  
  check_solution(board, std::vector<std::tuple<char, int, int>>(), 5, YELLOW | ORANGE | GREEN | RED | BLUE);
  std::cout << checkedGrids << " checkedGrids" << std::endl;
  
  // std::cout << check_fill({8, 4, 16, 16, 8, 4, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2}, YELLOW) << std::endl;
  // std::cout << check_fill({8, 4, 16, 16, 8, 4, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2}, ORANGE) << std::endl;
  // std::cout << check_fill({8, 4, 16, 16, 8, 4, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2}, GREEN) << std::endl;
  // std::cout << check_fill({8, 4, 16, 16, 8, 4, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2}, RED) << std::endl;
  // std::cout << check_fill({8, 4, 16, 16, 8, 4, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2}, BLUE) << std::endl;
  
  return 0;
}

ha ouais, je suis bête >__< merci.

Comme j'avais un peu de temps et quelques idées, j'ai micro-optimisé ton code pour le fun.

Au final, on gagne chez moi un facteur 5 sur la version avec cache (< 1s) et un facteur 4 sans cache (< 5s).

Au menu :

• gros refactoring
• minimise le nombre de copies de vecteurs
• mouvements "pas-à-pas" sur les axes
• usage de unordered_map au lieu de map pour le cache
• compression des grilles sur un uint64_t pour optimiser le cache

Le code modifié est ici.

Comme j'avais un peu de temps et quelques idées, j'ai micro-optimisé ton code pour le fun.

on s'amuse comme on peut merci

• minimise le nombre de copies de vecteurs

check_fill ne peut pas prendre la grille par référence, car dans cette version, je remets à 0 les cellules visitées et ensuite je vérifie si une des cellules contient la couleur "supprimée", et si oui, alors grille non terminée. Avec la référence, une grille comme « BLUE|GREEN, RED, RED|GREEN » sera considérée comme terminée si on vérifie le vert après le bleu ou le rouge.

• mouvements "pas-à-pas" sur les axes

c'est-à-dire ?

• usage de unordered_map au lieu de map pour le cache

pas con, j'oublie souvent l'existence des unordered_* (et vu l'utilisation, map n'est pas vraiment le meilleur conteneur)

• compression des grilles sur un uint64_t pour optimiser le cache

j'avais commencé avec du crc32 au début, mais collision oblige, j'ai viré et pas pensé à un remplacement. Mais j'ai modifié la grille de 2 façons:

• gérer les grilles de tailles arbitraires (le jeu ne contient que de 3×3 à 5×5), donc on dépasse les 64 bits (à voir si je peux m'amuser __int128_t ou simplement uint64_t[2])
• les cellules sont maintenant 4 uchar (top, left, bottom, right) + un 5è qui contient le | des 4 autres (notamment pour simplifier has(int colour))

petite optimisation que j'ai aussi rajoutée, si une ligne/colonne est d'une seule couleur, on fait pas d'appel récursif à check_solution qui élimine un appel à set<>::find.

le code actuel, qui est sûrement refactorable, mais il est relativement rapide même sur des grilles 5×5 avec 10 coups. (même si je pourrais allouer d'avance une partie de la mémoire, notamment des coups comme tu l'as fait)

  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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324

#include <iostream>
#include <tuple>
#include <vector>
#include <set>
#include <unordered_map>
#include <cmath>

#define YELLOW    1
#define BLUE  2
#define GREEN 4
#define ORANGE    8
#define RED       16
#define MAX_COLOURS 5

using uchar = unsigned char;
using uint = unsigned int;

struct Block
{
  Block(uchar c) : Block(c, c, c, c)
  {}
  
  Block(uchar a, uchar b, uchar c, uchar d) : top(a), right(b), bottom(c), left(d)
  {
      full = (a | b | c | d);
  }
  
  bool has(int colour)
  {
      return (full & colour);
  }
  
  void clear()
  {
      top = 0;
      right = 0;
      bottom = 0;
      left = 0;
  }
  
  uchar top;
  uchar right;
  uchar bottom;
  uchar left;
  uchar full;
};

bool operator<(const Block& lhs, const Block& rhs)
{
  if(lhs.top != rhs.top)
      return lhs.top < rhs.top;
  if(lhs.left != rhs.left)
      return lhs.left < rhs.left;
  if(lhs.bottom != rhs.bottom)
      return lhs.bottom < rhs.bottom;
  return lhs.right < rhs.right;
}

bool operator==(const Block& lhs, const Block& rhs)
{
  return (lhs.top == rhs.top)
      && (lhs.left == rhs.left)
      && (lhs.bottom == rhs.bottom)
      && (lhs.right == rhs.right);
}

class Board : public std::vector<Block>
{
public:
  using std::vector<Block>::vector;
  
  uint side() const
  {
      if(mSide < 1)
          mSide = std::sqrt(size());
      return mSide;
  }

  bool row_moved(int row, int move)
  {
      using std::swap;
      
      if(rows.find(row) != rows.end())
          return false;
      
      Board & b = *this;
      
      int row_start = row * side();
      
      Block check = b[row_start + side() - 1];
      bool are_equals = true;
      
      while(move > 0)
      {
          int x = side() - 1;
          while(x > 0)
          {
              if(are_equals)
              {
                  are_equals = (check == b[row_start + x - 1]);
              }
              
              swap(b[row_start + x], b[row_start + x - 1]);
              --x;
          }
          
          --move;
      }
      
      return !are_equals;
  }
  
  bool col_moved(int col, int move)
  {
      using std::swap;
      
      if(columns.find(col) != columns.end())
          return false;
      
      Board & b = *this;
      
      Block check = b[col + size() - side()];
      bool are_equals = true;
      
      while(move > 0)
      {
          int x = size() - side();
          while(x > 0)
          {
              if(are_equals)
              {
                  are_equals = (check == b[col + x - side()]);
              }
              
              swap(b[col + x], b[col + x - side()]);
              x -= side();
          }
          --move;
      }
      
      return !are_equals;
  }
  
  void blockRows(std::set<int> rs)
  {
      for(int elem : rs)
          rows.insert(elem - 1);
  }
  
  void blockColumns(std::set<int> cols)
  {
      for(int elem : cols)
          columns.insert(elem - 1);
  }

private:
  mutable uint mSide = 0;
  std::set<int> columns;
  std::set<int> rows;
};

void debug_block(const Block & b)
{
  std::cout << "(" << (int)b.top << " " << (int)b.right << " " << (int)b.bottom << " " << (int)b.left << ")";
}

void debug_board(const Board & board)
{
  for(uint i = 0;i < board.size();i++)
  {
      const Block & b = board[i];
      debug_block(b);
      if((i+1) % board.side() == 0) std::cout << std::endl;
  }
  std::cout << std::endl;
}

bool check_fill(Board board, uchar value)
{
  const uint bSize = board.size();
  const uint bSide = board.side();
  
  std::vector<uint> zeroes;
  for(uint i = 0;i < bSize;i++)
  {
      if(board[i].has(value))
      {
          zeroes.push_back(i);
          break;
      }
  }
  
  while(zeroes.size() > 0)
  {
      const uint i = zeroes.back();
      zeroes.pop_back();
      
      const uint x = i % bSide;
      const uint y = i / bSide;
      
      // left
      if(x > 0 && board[i].left == value && board[i - 1].right == value)
          zeroes.push_back(i - 1);
      // right
      if(x < bSide - 1 && board[i].right == value && board[i + 1].left == value)
          zeroes.push_back(i + 1);
      // up
      if(y > 0 && board[i].top == value && board[i - bSide].bottom == value)
          zeroes.push_back(i - bSide);
      // down
      if(y < bSide - 1 && board[i].bottom == value && board[i + bSide].top == value)
          zeroes.push_back(i + bSide);
      
      board[i].clear();
  }
  
  for(uint i = 0;i < bSize;i++)
  {
      if(board[i].has(value))
      {
          return false;
      }
  }
  
  return true;
}

int checkedGrids = 0;
std::unordered_map<int, std::set<Board>> cache;
using MoveCache = std::tuple<char, uint, uint>;

bool check_solution(Board board, std::vector<MoveCache> moves, int remaining_moves, int colours)
{
  if(cache[remaining_moves].find(board) != cache[remaining_moves].end())
  {
      return false;
  }
  cache[remaining_moves].insert(board);
  
  if(remaining_moves < 1)
  {
      ++checkedGrids;
      
      bool filled = true;
      for(int colour = 0;colour < MAX_COLOURS && filled;colour++)
      {
          int colourShifted = 1 << colour;
          if(colourShifted & colours)
          {
              if(!check_fill(board, colourShifted))
              {
                  filled = false;
              }
          }
      }
      
      if(filled)
      {
          std::cout << "SOLUTION FOUND :" << std::endl;
          debug_board(board);
          std::cout << std::endl;
          for(auto & move : moves)
          {
              std::cout << std::get<0>(move) << " " << std::get<1>(move) << " " << std::get<2>(move) << std::endl;
          }
          std::cout << std::endl;
          cache.clear(); // car sinon le programme met un temps fou à se fermer
          return true;
      }
      
      return false;
  }
  
  for(uint i = 0;i < board.side();i++)
  {
      for(uint move = 1;move < board.side();move++)
      {
          if(moves.size() == 0 || std::get<0>(moves.back()) != 'r' || std::get<1>(moves.back()) != (i + 1))
          {
              auto gridR = board;
              if(gridR.row_moved(i, move))
              {
                  auto vec = moves;
                  vec.emplace_back('r', i + 1, move);
                  if(check_solution(gridR, vec, remaining_moves - 1, colours))
                      return true;
              }
          }
          
          if(moves.size() == 0 || std::get<0>(moves.back()) != 'c' || std::get<1>(moves.back()) != (i + 1))
          {
              auto gridC = board;
              if(gridC.col_moved(i, move))
              {
                  auto vec = moves;
                  vec.emplace_back('c', i + 1, move);
                  if(check_solution(gridC, vec, remaining_moves - 1, colours))
                      return true;
              }
          }
      }
  }
  
  return false;
}

int main()
{
  Board board = {
      Block(GREEN),   Block(RED),     Block(GREEN),   Block(RED),     Block(GREEN),
      Block(RED),     Block(GREEN),   Block(BLUE),    Block(GREEN),   Block(RED),
      Block(GREEN),   Block(BLUE),    Block(GREEN),   Block(BLUE),    Block(GREEN),
      Block(RED),     Block(GREEN),   Block(BLUE),    Block(GREEN),   Block(RED),
      Block(GREEN),   Block(RED),     Block(GREEN),   Block(RED),     Block(GREEN),
  };
  
  board.blockColumns({ 1, 5 });
  board.blockRows({ 1, 5 });
  
  check_solution(board, std::vector<MoveCache>(), 6, GREEN | RED | BLUE);
  std::cout << checkedGrids << " checkedGrids" << std::endl;
  
  return 0;
}

check_fill ne peut pas prendre la grille par référence, car dans cette version, je remets à 0 les cellules visitées et ensuite je vérifie si une des cellules contient la couleur "supprimée", et si oui, alors grille non terminée. Avec la référence, une grille comme « BLUE|GREEN, RED, RED|GREEN » sera considérée comme terminée si on vérifie le vert après le bleu ou le rouge.

Comment une case de la grille peut-elle avoir deux couleurs à la fois (BLUE|GREEN) ? J'ai dû louper un truc dans les règles du jeu.

Dans tous les cas, tu pourrais effacer uniquement la couleur actuelle, avec quelque chose comme board[i].full &= ~color, et te contenter d'une seule copie pour le check.

• mouvements "pas-à-pas" sur les axes

c'est-à-dire ?

Au lieu de faire un pas, puis deux pas, puis trois pas sur 3 copies différentes, on garde la même grille et on fait un pas, puis encore un pas, puis encore un pas. Il faut juste faire attention à ne pas toucher la grille entre temps.

j'avais commencé avec du crc32 au début, mais collision oblige, j'ai viré et pas pensé à un remplacement. Mais j'ai modifié la grille de 2 façons:

• gérer les grilles de tailles arbitraires (le jeu ne contient que de 3×3 à 5×5), donc on dépasse les 64 bits (à voir si je peux m'amuser __int128_t ou simplement uint64_t[2])

Oui, si on a plus de 4 couleurs dans une grille de 5x5, ça ne tient plus dans 64 bits (même en supposant qu'il n'y a qu'une couleur par case).

• les cellules sont maintenant 4 uchar (top, left, bottom, right) + un 5è qui contient le | des 4 autres (notamment pour simplifier has(int colour))

Donc il est bel et bien possible d'avoir plusieurs couleurs sur une seule case, c'est bien ça ?

Re-bonjour,

Seconde version de ton code micro optimisé. Je cherche toutes les solutions différentes à une profondeur bornée, donc ça prend forcément du temps sur les grandes grilles ou avec une certaine profondeur (si on veut une seule solution, je pense que le mieux est de faire de l'iterative deepening).

La recette est la même, sauf pour la compression en uint64_t. Cette fois, j'utilise directement un cache std::unordered_map<Board, int> avec une fonction de hash prise de Boost. (la valeur est le niveau sur lequel la grille a été vue: si c'est supérieur ou égal on passe, sinon on cherche à nouveau).

J'ai désactivé le blocage des mouvements sur certains axes (à quoi ça sert ?), et supprimé le check en cas de rotation inutile (je ne sais pas si ça arrive suffisamment souvent pour qu'on y gagne grand chose).

Ah, et puis j'ai aussi "templatisé" la classe Board, on doit y gagner un peu à l’exécution, mais c'est plus chiant à utiliser.

Voila voila.

EDIT : encore un truc intéressant, ne pas cacher les grilles pour remaining_moves == 0, ça apporte un gain appréciable (en espace comme en temps).

Comment une case de la grille peut-elle avoir deux couleurs à la fois (BLUE|GREEN) ? J'ai dû louper un truc dans les règles du jeu.

au début on a effectivement des cases pleines, mais par la suite ça se corse de plusieurs façon.

• des cases ayant plusieurs couleurs (au début j'avais un simple |, mais ça ne disait pas quelle direction avait quelle couleur, d'où le "potential solution").
• des cases étant fixes (donc on ne peut pas bouger leur colonne/ligne)
• des cases qui pivotent quand on les bouge (je ne compte pas gérer ce cas là, je préfère tester toutes les positions possibles vu qu'il y en a pas plus de 2 par grille)

merci pour les idées

@yoch : Si je peux me permettre une remarque sur ton code, pourquoi utilises-tu des constantes de préprocesseur ? En C++, on préférera les constantes du type const int Yellow = 1 par exemple, ou encore mieux une enumération. Ou encore encore mieux, une énumération fortement typée (enum class…). Dans ton cas, une énumération fortement typée semble s'imposer d'elle-même.

Comme je viens du C, et que ça fait un bon moment que je n'ai pas touché au C++, faut m'excuser pour ce genre de chose…

(et aussi, j'ai surtout repris le code de minirop, la seule constante que j'ai ajouté c'est MAX_DEPTH, ça se discute un peu plus)

Ok, tu es pardonné pour cette fois. Mais maintenant je vais te stalker et à la moindre utilisation illégitime de define…

Lu'!

Quelques notes purement C++ concernant le code le plus récent (en lien "micro-optimisé") :

• (important) ne pas hériter publiquement de vector, il n'a pas de destructeur virtuel* (et n'est donc pas voué à être dérivé),
• (léger) inline est inutile dans une définition de fonction membre si elle est dans la classe (car inline par défaut si c'est possible),
• (accessoire) bonne pratique possible : quand on veut manipuler un index sur un conteneur, prendre le type "conteneur::size_type".

Sinon je trouve le code plutôt cool et clair.

(*) EDIT : Pour être plus précis, ne jamais hériter publiquement d'un conteneur de la SL.

(*) EDIT : Pour être plus précis, ne jamais hériter publiquement d'un conteneur de la SL.

Donc ce genre de code n'est pas une bonne idée ?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <array>
class Vector3D : public std::array<float, 3> {
public:
    Vector3D() : Vector3D(0, 0, 0) {}
    Vector3D(float x, float y, float z){
        (*this)[0] = x;
        (*this)[1] = y;
        (*this)[2] = z;
    }

    Vector3D(const Vector3D&) = default;
    Vector3D(Vector3D&&) = default;

    Vector3D& operator=(const Vector3D&) = default;
    Vector3D& operator=(Vector3D&&) = default;

    ~Vector3D() = default;
};

Je trouvais ça utile pourtant de récupérer toutes les fonctions publiques de std::array sans rien avoir à faire. L'alternative étant un typedef, mais là je me retrouvais à définir des macros à la place du constructeur.

L'héritage public, c'est l'héritage "est-un" la plus forte relation possible entre deux classes. Grosso-modo, toute opération possible sur un objet de la classe de base doit avoir un sens sur la classe dérivée. En gros, on prend un vector, on met pêle-mêle des bases et des dérivés, on fait n'importe quelle opération de leur interface dessus : ça doit avoir un sens.

Est ce que, pour toi, cette opération à un sens :

1
2

Vector3D v(42.7, 21.3, 89.8);
std::sort(v.begin(), v.end());

Après, si on prend les opérations de array, je ne vois pas trop pourquoi tu aurais besoin de tout ça :

• at (une aberration qui n'aurait jamais du voir le jour, ni dans array, ni dans vector),
• operator[] : celle là éventuellement,
• front/back : ?
• data : beurk,
• les iterators je viens de montrer un exemple embêtant,
• empty : ben on connaît déjà la réponse, non,
• max_size/size : c'est dans le nom du type,
• fill : pas convaincu, Vector3D à clairement une sémantique de valeur, on ferait une affectation,
• swap : implémentable en une ligne (voir mieux, on laisse le std::swap par défaut faire son travail),
• les opérateurs lexicographique, ils n'ont pas franchement le sens voulu pour des vecteur à part == et != .

Un héritage privé avec une interface pour Vector donnant exactement ce qui est nécessaire serait bien plus indiqué.

Est ce que, pour toi, cette opération à un sens :

1 2	Vector3D v(42.7, 21.3, 89.8); std::sort(v.begin(), v.end());

Oui, elle a un sens, mais pas vraiment de pertinence.

Après, si on prend les opérations de array, je ne vois pas trop pourquoi tu aurais besoin de tout ça :

• at (une aberration qui n'aurait jamais du voir le jour, ni dans array, ni dans vector),
• operator[] : celle là éventuellement,
• front/back : ?
• data : beurk,
• les iterators je viens de montrer un exemple embêtant,
• empty : ben on connaît déjà la réponse, non,
• max_size/size : c'est dans le nom du type,
• fill : pas convaincu, Vector3D à clairement une sémantique de valeur, on ferait une affectation,
• swap : implémentable en une ligne (voir mieux, on laisse le std::swap par défaut faire son travail),

Tu as un lien pour le fonctionnement par défaut du std::swap ? Et pour l'explication des différentes sémantiques ? Ou bien cppreference est le mieux pour ce genre de questions ?

Ok, je vois l'idée. Du coup, y-a-t-il un avantage quelconque à utiliser std::array<float, 3> par rapport à float[3] comme type interne ?

(1) De mémoire, l'implémentation par défaut doit être :

1
2
3
4
5
6

template<class T>
void swap(T& a, T& b){
  auto&& tmp = std::move(a);
  a = std::move(b);
  b = std::move(tmp);
}

(2) FaQ développez - C++.

Oui. D'abord garder un code le plus homogène possible, comme ici on n'a pas non plus de raison de préférer float[3], et que de manière générale, on préfère std::array. Ensuite, pour certaines opérations que tu voudrais pouvoir ajouter à des Vector3D (colinéarité, transformation, etc), les algos de la SL pourront être utiles en interne std::array nous file l'accès aux itérateurs *.

* Note : avec cet argument je triche, on a std::begin/std::end qui savent traiter les tableaux C de taille statiquement déterminée.

EDIT : Il y a également un argument encore bien plus simple pour ne pas autoriser l'héritage public des éléments de la SL : ce sont toutes des classes à sémantique de valeur, elles n'ont pas de destructeur virtuel et ne sont pas destinées à être dérivées.

Bonjour,

JE n'ai absolument pas suivi le début de la discussion, mais je voudrais réagir à ça :

• (important) ne pas hériter publiquement de vector, il n'a pas de destructeur virtuel* (et n'est donc pas voué à être dérivé),

En quoi le fait que les conteneurs de la SL n'ont pas de destructeurs virtuels est un problème, si on n'utilise pas la sous-classe qu'on a créé de façon polymorphe ?

Je demande ça parce que de mon côté, je suis parti de unordered_map<std::string,std::string> pour créer une classe de gestion de fichiers ini, et je n'avais pas envie de me retaper find, erase, operator[], … entres autres

L'héritage public n'est pas indiqué pour ton cas. Soit tu fais un héritage privé, soit tu encapsules ta map en tant qu'attribut. Dans ce cas, ta classe se comporterait comme un adapteur de conteneur de la STL (*)(ma traduction est bidon) comme std::queue par exemple.

@Ksass'Peuk : Ta mémoire est bonne ; j'ai vu l'implémentation de swap il n'y a pas longtemps, je ne sais plus pourquoi, mais en tout cas c'était bien ça.

(*) La généricité en moins.

Qu'est ce qui le garantit ? Rien. La définition de ta classe doit se suffire à elle-même et ne permettre aucun usage qui provoquerait une rupture de son contrat. De manière générale, ça passe par l'établissement et le maintient d'un invariant. Mais rien ne permet de garantir que tu n'auras jamais une utilisation polymorphe de ta classe.

D'autres avis :

• (@lmghs) : http://forum.ubuntu-fr.org/viewtopic.php?pid=8242081#p8242081
• (@Freedom) : http://openclassrooms.com/forum/sujet/probleme-avec-les-templates-et-l-heritage-67480#message-7130188
• un article très complet : https://punchlet.wordpress.com/2009/12/29/letter-the-fifth/

Et bien sûr, un héritage public doit toujours respecter le LSP.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
#include <vector>

//notons l'héritage privé
class MyVectorInt : private std::vector<int>{
public:
  using std::vector<int>::vector;
  using std::vector<int>::operator[];
  using std::vector<int>::size;
  using std::vector<int>::begin;
  using std::vector<int>::end;

  //etc ...
};

int main()
{
    MyVectorInt mvi(42);

    for(int v : mvi)
      std::cout<<v<<" ";
}

C'est donc à ça que sert l'héritage en private ! Je n'avais jamais compris l'utilité du truc en fait

Mais rien ne permet de garantir que tu n'auras jamais une utilisation polymorphe de ta classe.

Si, si je suis le seul à l'utiliser… mais dans l'absolu tu as raison effectivement.

Je ne comprends pas en quoi la dérivation privée change quelque chose pour le destructeur non virtuel alors