Discussion :

[gbdivers]

Bonjour à tous

J'ai posé un petit exercice sur le chat en pensant qu'il ne poserait pas de difficultés particulière. Et j'ai été surpris de voir une proposition de solution assez originale de germinolegrand (qu'il va garder pour lui, le temps que d'autres personnes proposent aussi des solutions). Voici l’annoncé, relativement simple, pour que d'autres puisse participer :

Vous avez un classe qui contient plusieurs conteneurs membres. Vous souhaitez écrire une fonction permettant de faire une transaction, c'est à dire insérer des éléments dans les conteneurs et que les insertions soient toutes réussies ou soient toutes annulées.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
class SafeTransaction {
   vector<int> v1, v2;
public:
   void push_back(int x1, int x2) { 
      v1.push_back(x1);
      v2.push_back(x2);
   }
};
 
SafeTransaction t;
t.push_back(1, 2);
// v1 et v2 contiennent 1 élément chacun, soit v1 et v2 ne contiennent rien

Pouvez-vous donner un exemple de classe(s) permettant de réaliser ça ?

Pensez en particulier aux exceptions, à pouvoir utiliser différents types de conteneurs et de contenant et plus de deux conteneurs membres. Essayez de proposer du code C++11 et non C++11 si possible.

C'est les vacances, prenez votre temps, fin de l'exercice à la fin du mois d'août.

[germinolegrand]

code C++11 et non C++11

le 2e c'est C++03 je suppose ? ^^

[Ekleog]

Euh... Je suppose que cette solution est jugée comme étant une forme de triche ?

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
class SafeTransaction {
   vector<int> v1, v2;
public:
   void push_back(int x1, int x2) {
      v1.push_back(x1);
      try { v2.push_back(x2); }
      catch (...) { v1.pop_back(); throw; }
   }
};

Bien sûr, si pop_back() throw aussi, ça ne fonctionnera pas.
Mais si le deuxième push_back ne fonctionne pas et que le pop_back ne veut pas s'exécuter, je suppose qu'on peut considérer que l'état du programme est suffisemment mauvais pour justifier un probable crash.

Soit dit en passant, selon IBM (?), pop_back est nothrow. J'ai du mal à comprendre comment c'est possible sachant que le destructeur peut lancer une exception. Oui, çaymal, mais ça reste possible.

Bref... Triche ou non ?

[Flob90]

Tu pourrais un peu préciser ce qu'il faut respecter ?

• Résistance fortes au exceptions (je suppose que oui) ?
• Doit marcher en multi-thread ? Si oui sous quels conditions ?
• Obliger d'utiliser plusieurs conteneurs ou on fait l'implémentation comme on veut tant que les services attendues (insérer plusieurs éléments en même temps) sont respectés.
• Les éléments insérés sont liés ou non ? Par exemple le retrait d'un élément entraîne le retrait de ceux inserés avec lui ? On doit pouvoir retrouver qui a été insérer avec un élément donné ?
• Les éléments ne peuvent s'insérer que par multitude, ou on peut insérer un élément tout seul ? Même questions pour le retrait ?
• Quels sont les autres services typique que doit fournir la classe ? (Ca peut jouer si on est libre de faire l'implémentation comme on veut)

Edit: Ou si tout ces paramètres sont libres, alors quel est l'utilisation typique attendue ? Savoir à quoi ca peut servir peut aider à définir ce que la classe doit faire et les différents degrés de liberté.

[germinolegrand]

Ekleogl : je ne pense pas que ce soit de la triche Toutefois il faudra l'étoffer.

[gbdivers]

@Ekleog
Non, c'est pas de la triche, c'est très bien. C'est la méthode simple et efficace
Par contre, tu vas être vite limité : si tu veux gérer plus de vecteurs, tu vas devoir faire des try-catch en cascade ; si tu veux pourvoir laisser à l'utilisateur la possiblité de faire les push qu'il veut (par exemple 2 dans v1 et 3 dans v2 dans une seule transaction), il faudra proposer plusieurs fonctions différentes

@Flob90
Trop de questions Le but est de s'amuser sur un exercice, trouver des solutions et voir quels sont les limites d'utilisation.

[Niark13]

Bonjour,

Je viens de lire le sujet et propose une première solution "C++11" (soyez cléments, je découvre les variadic templates en C++)...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
// Une classe generique de push_back transactionnels sur un nombre quelconque
// de conteneurs
// parametres:
// - Container: une classe de conteneur (qui doit gerer push_back()/pop_back()
// - ContainerCount: le nombre de conteneur a gerer.
template <class Container, size_t ContainerCount>
class SafeTransaction
{
    // nos conteneurs internes.
    Container m_containers[ContainerCount];
 
    // Insere des elements dans des conteneurs, de maniere recursive.
    // parametres:
    // - index: index du conteneur dans le tableau m_conteneur qui va etre modifie.
    // - value: valeur a inserer
    // - values: reste des arguments...
    template<typename T, typename... Ts>
    void push_back_impl(int index, T value, Ts... values)
    {
        // A-t-on bien ajoute l'element ?
        bool done = false;
        try
        {
            // on insere l'argument en cours dans le bon conteneur
            m_containers[index].push_back(value);
            done = true;
 
            // s'il reste des arguments, on le transfere au template recursif suivant.
            if (sizeof...(values) > 0)
            {
                push_back_impl(index+1, values...);
            }
        }
        catch (...)
        {
            // en cas d'erreur, on enleve le dernier element du conteneur et on
            // propage l'exception a l'appelant.
            if (done)
            {
                m_containers[index].pop_back();
            }
            throw;
        }
    }
 
public:
    // methode visible permettant d'insérer des elements dans un nombre quelconque de
    // conteneurs. Le premier argument est inséré dans le premier conteneur, le
    // deuxième argument dans le deuxieme conteneur, et ainsi de suite..
    template<typename... Ts>
    void push_back(Ts... parameters)
    {
        static_assert(sizeof...(parameters) <= ContainerCount, "Too many arguments.");
 
        if (sizeof...(parameters) > 0)
        {
                push_back_impl(0, parameters...);
 
        }
    }
};

[Davidbrcz]

Y'a un truc que je capte pas dans le code Ekleog. Si v1.push_back lance une exception, il n'a aucun moyen de la rattraper à l'intérieur de la fonction. Et donc son code n'est pas transactionnel.

Ou j'ai loupé un truc.

[germinolegrand]

@davidbrcz: si justement, si v1 throw, alors v1 et v2 restent dans le même état qu'au début de la fonction.
edit: disons que ce n'est qu'une partie sous-jacente d'une transaction qui est demandée ici.

[Ekleog]

Voilà pour des general-purpose transactions :

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#include <functional>
#include <vector>
 
using action_cb   = std::function<void ()>;
using rollback_cb = std::function<void ()>;
 
struct Transaction {
   action_cb    action;
   rollback_cb  rollback;
   Transaction* next;
 
   void execute() {
      action();
      if (next) {
         try {
            next->execute();
         } catch (...) {
            rollback();
            throw;
         }
      }
   }
};
 
void transaction(std::vector<std::pair<action_cb, rollback_cb>> const & actions) {
   // Build transaction array and linked-list
   std::vector<Transaction> transactions(actions.size());
   for (std::size_t i = 0 ; i < actions.size() ; ++i) {
      transactions[i].action   = actions[i].first;
      transactions[i].rollback = actions[i].second;
      transactions[i].next     = &transactions[i + 1];
   }
   // Fix last pointer
   transactions[actions.size() - 1].next = nullptr;
   // Execute
   transactions[0].execute();
}
 
#include <iostream>
 
int main() {
   try {
      transaction({
         { [] () { std::cout << "Running transaction\n"; },
           [] () { std::cout << "Rollbacked transaction\n"; }
         },
         { [] () { new int [999999999999999]; std::cout << "Unreachable.\n"; },
           [] () { std::cout << "Should never be called !\n"; }
         }
      });
   } catch (std::exception const & e) {
      std::cerr << "Exception caught : " << e.what() << " ; ignoring...\n";
   }
 
   std::vector<int> v1, v2, v3;
   transaction({
      { [&v1] () { v1.push_back(1); },
        [&v1] () { v1.pop_back(); }
      },
      { [&v2] () { v2.push_back(2); },
        [&v2] () { v2.pop_back(); }
      },
      { [&v3] () { v3.push_back(3); },
        [&v3] () { v3.pop_back(); }
      }
   });
   // Mériterait probablement un wrapper, mais ici c'est une transaction
   // générique, pas seulement orientée push_back !
 
   for (int i : v1) std::cout << i << " ";
   for (int i : v2) std::cout << i << " ";
   for (int i : v3) std::cout << i << " ";
   std::cout << "\n";
}

Alors, vous en pensez quoi ? (Note : chez moi, new int [999999999999999]; lance une out_of_memory. Je trouvais moche de simplement faire un throw, en fait. Sinon, vous pouvez remplacer par n'importe quel throw, en fait.)

[Edit suite à la lecture de Davidbrcz: Pour moi, il faut soit que tout fonctionne, soit que rien ne change et que l'exception soit remontée à l'appellant (potentiellement, si on utilise boost::exception, avec ajout d'informations sur le site spécifique de l'erreur). Est-ce que j'ai mal compris le sujet ?]

[Edit2: Ajouté à ma liste d'utilitaires divers et variés dont je ne me suis encore jamais servi : https://github.com/Ekleog/misc/blob/master/transaction.cpp ]

[Edit3: OMG l'horreur que j'ai écrit ! Pitié, dites moi que vous n'avez pas eu le temps de lire le code où j'avais laissé les new/delete très mal gérés.]

[gbdivers]

[Edit suite à la lecture de Davidbrcz: Pour moi, il faut soit que tout fonctionne, soit que rien ne change et que l'exception soit remontée à l'appellant (potentiellement, si on utilise boost::exception, avec ajout d'informations sur le site spécifique de l'erreur). Est-ce que j'ai mal compris le sujet ?]

Non non, tu as bien un transaction : tout est commit ou rien ne l'ai. L'utilisateur de ton code sait que si une exception survient, c'est que aucun vector n'a été modifié. Libre à lui ensuite de refaire le push complet ou autre chose

EDIT : pour répondre à une question de germinolegrand, pour tester si un paramètre est bien un conteneur : boost::spirit is_container
Peux aider pour avoir des messages d'erreurs template user-friendly...

[Davidbrcz]

germinolegrand >> Ouais ouais. J'avais juste mal lu le premier post. Dans ma tête, fallait être capable de continuer même si l'une plantait.

Mais à réfléchir, c'est déjà le cas, suffit d'attraper l'exception qui en sort.

[gbdivers]

Mais à réfléchir, c'est déjà le cas, suffit d'attraper l'exception qui en sort.

Oui bien sur, on peut catcher l'exception pour savoir quel push_back à planter et l'annuler ou le refaire. C'est ce que fait Ekleog.

Mais c'est alors la responsabilité de l'utilisateur de le faire, ce qui revient à dire que ça peut ne pas être fait.

Là, l'idée est de dire que la responsabilité de l'intégrité de la transaction est une responsabilité à part entière, qui doit donc être prise en charge par une structure spécifique et pas laissée à la bonne volonté de l'utilisateur.

[Ekleog]

Niark13> Je crois que, ligne 32, ce devrait plutôt être push_back_impl. Non ?

Sinon, aucun commentaire sur les quelques propositions déjà avancées ?

[Flob90]

Les codes proposés utilisent pour le moment tous le même méchanisme (en récursif et en itératif). La version itérative utilisant en plus un pattern Command.

Pour la version récursive, il est étrange de terminer la récursion avec un if alors que tout est connu à la compilation. On aurait pu la terminer en utilisant une surcharge avec un PP vide (ie pas de PP) pour push_back_impl. Le test de la positivité de la taille du PP est aussi étrange, elle est nécessairement positive et le cas nul devrait pouvoir être le cas terminal.

Les deux solutions, étant basées sur le même mécanisme, ne sont pas thread-safe. Si deux transactions sont faites en même temps sur les même conteneurs, alors si tout se passe bien rien ne garantit que l'ordre des éléments soit celui d'un des deux cas séquentiel associé, et si l'un des deux lance une exception, l'état peut devenir invalide.

[JolyLoic]

Dans la version du code présenté initialement, avec un objet contenu ne lançant pas d'exception à la copie, je ferais simplement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
void push_back(int x1, int x2) { 
 
      v1.reserve(v1.size()+1);
      v2.reserve(v2.size()+1);
      v1.push_back(x1);
      v2.push_back(x2);
   }

[gbdivers]

J'aime les solutions simples

Par contre, ton code est spécifique à vector

[JolyLoic]

En effet. Par contre, si on veut être plus générique, il va falloir préciser un peu tout de même (même si je comprends l'aspect ludique du problème, ce n'est pas évident d'y réfléchir si le cadre est trop flou)...

Déjà, côté conteneur, je suppose, vu l'énoncé, qu'il faut que ça marche pour toutes les séquences fournissant push_back ? Et comme dans le standard, elles fournissent aussi pop_back, il me semble raisonnable de supposer que l'on a aussi droit à ça (plus tout le reste de ce qui défini une séquence).

Maintenant, côté objet contenu, il y a d'autres questions qui se posent, à la réponse moins tranchée...
Le type est-il supposé régulier (en particulier, CopyConstructible et CopyAssignable) ?
Quelles sont les fonctions que l'on peut supposer noexcept(true) ? Le destructeur (sinon, c'est vraiment difficile de raisonner, et c'est imposé par le standard pour avoir le droit de mettre un objet dans un conteneur (ce qui répond à la question d'Ekleog sur pop_back)). Mais y en a-t-il d'autres ? le move constructor ? swap ?

Une solution qui marche avec les types réguliers (mais pas forcément optimale en terme de performances, c'est le moins qu'on puisse dire), et quel que soit le conteneur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Cont1 copy1 = cont1;
Cont2 copy2 = cont2;
copy1.push_back(x1);
copy2.push_back(x2);
copy1.swap(cont1);
copy2.swap(cont2);

Rem : On peut optimiser un peu en ne faisant pas de copie pour le dernier conteneur.

[gbdivers]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Cont1 copy1 = cont1;
Cont2 copy2 = cont2;
copy1.push_back(x1);
copy2.push_back(x2);
copy1.swap(cont1);
copy2.swap(cont2);

Oh la brute

Pour pusk_back et pop_back, comme tu veux. Mais par exemple map n'a pas ces fonctions. insert et erase est plus générique. L'idéal est peut être de pouvoir paramétrer ? (mais ça alourdi)

type régulier ? a priori, oui. Il faut au mois que le type passe dans un conteneur, tu penses à un conteneur particulier qui accepterait des types non réguliers ?

A priori, oui, pop_back, erase, move constructeur, swap sont noexept. Je sais pas si cette propriété est indiqué dans une référence ?

[Ekleog]

Allez, en réutilisant ma fonction transaction déjà postée, un helper pour push_back (non testé, et il doit y avoir un meilleur moyen pour alterner non const et const... tout comme il doit y avoir un meilleur moyen pour faire tout ce bout de code, en fait.) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
template <class C, typename T, typename... Args>
std::list<std::pair<action_cb, rollback_cb>> pb_trans_impl_impl(C & cont, T const & val, Args &... args) {
   auto sub = pb_trans_impl_impl(args...);
   sub.push_front({ [&cont, &val] () { cont.push_back(val); },
                    [&cont]       () { cont.pop_back(); }
                  });
   return sub;
}
 
template <>
std::list<std::pair<action_cb, rollback_cb>> pb_trans_impl_impl() {
   return {};
}
 
template <typename... Args>
std::vector<std::pair<action_cb, rollback_cb>> pb_trans_impl(Args &... args) {
   auto list = pb_trans_impl_impl(args...);
   return std::vector<std::pair<action_cb, rollback_cb>>(list.begin(), list.end());
}
 
template <typename... Args>
void pb_trans(Args &... args) {
   transaction(pb_trans_impl(args...));
}
 
// ...
int main() {
   std::vector<int> vi;
   std::vector<double> vd;
   std::vector<float> vf;
   pb_trans(vi, 42, vd, 3.14, vf, 1.f);
}

(Ca me fait penser que j'aurais dû rendre ma fonction transaction indépendante du type de conteneur...)