Exercice C++ : des push_back transactionnels

Version imprimable

Voir 40 message(s) de cette discussion en une page

28/07/2012, 03h24
JolyLoic

Citation:

Envoyé par gbdivers

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 ?

Bin... tous ! D'autant plus que régulier n'est pas défini clairement dans le langage... :)
Mais par exemple, rien n'interdit de mettre dans une list des objets qui ne sont ni copiables, ni movables, ou dit plus précisément qui ne respectent pas le sens habituel des opérations de copie/move.

Citation:

Envoyé par gbdivers

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 ?

On a :

Citation:

Envoyé par Le standard 23.2.1/10

— if an exception is thrown by an insert() function while inserting a single element, that function has no effects.
— if an exception is thrown by a push_back() or push_front() function, that function has no effects.
— no erase(), clear(), pop_back() or pop_front() function throws an exception.
— no copy constructor or assignment operator of a returned iterator throws an exception.
— no swap() function throws an exception.
— no swap() function invalidates any references, pointers, or iterators referring to the elements of the
containers being swapped. [ Note: The end() iterator does not refer to any element, so it may be
invalidated. —end note ]

Par contre, le move constructor du type contenu, c'est quelque-chose qui n'a rien d'évident. Et ça peut arriver très souvent dans la vraie vie.
En particulier, si j'implémente un move constructor pour une de mes classes, et que celle-ci possède une donnée membre d'un type qui n'a pas de move constructor (par exemple un type écrit avant C++11), je vais implémenter ce move constructor en faisant une copie pour cette donnée membre. Et donc mon move constructor ne sera pas noexcept...

Ou comment ecrire du code traitant les exceptions sans ecrire un seul try catch:

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
template< class OPERATION >
struct Transaction
{
    OPERATION operation;
    bool success;
 
    Transaction(OPERATION op)
        :   operation(op)
        ,   success(false)
    {
        operation.perform();
    }
 
    ~Transaction()
    {
        if (!success)
        {
            operation.undo();
        }
    }
};
 
 
template< class CONTAINER >
struct PushBackOperation
{
    friend class Transaction< PushBackOperation< CONTAINER > >;
    CONTAINER& container;
    typename CONTAINER::const_reference t;
    PushBackOperation(CONTAINER& container, typename CONTAINER::const_reference t)
        :   container(container)
        ,   t(t)
    {
    }
 
    Transaction< PushBackOperation<CONTAINER> > MakeTransaction()
    {
        return Transaction< PushBackOperation<CONTAINER> >(*this);
    }
private:
    void perform()
    {
        container.push_back(t);
    }
    void undo()
    {
        container.pop_back();
    }
};
 
 
 
#include <vector>
#include <list>
 
using namespace std;
 
int main()
{
    vector<int> integers;
    vector<float> floats;
    list<double> doubles;
 
    auto t1 = PushBackOperation< vector<int> >(integers, 1).MakeTransaction();
    auto t2 = PushBackOperation< vector<float> >(floats, 1.0f).MakeTransaction();
    auto t3 = PushBackOperation< list<double> >(doubles, 1.0).MakeTransaction();
    t1.success = t2.success = t3.success = true;
}

ca merite un peu de sucre syntaxique mais le pricipe est la je pense.

Citation:

Envoyé par screetch

ca merite un peu de sucre syntaxique mais le pricipe est la je pense.

Peut être qu'une lambda simplifierait l'écriture ?

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
 
template< class ROLLBACK >
struct Transaction
{
    ROLLBACK rollback;
    bool success;
 
    Transaction(ROLLBACK op)
        :   rollback(op)
        ,   success(false)
    {
    }
 
    ~Transaction()
    {
        if (!success)
        {
            rollback();
        }
    }
};
 
template <typename ROLLBACK>
Transaction<ROLLBACK> MakeTransaction(const ROLLBACK& rollback)
{
   return Transaction<ROLLBACK>(rollback);
}
 
class SafeTransaction {
   std::vector<int> v1, v2;
public:
   void push_back(int x1, int x2) 
   {
      int v1_old_size = v1.size();
      int v2_old_size = v2.size();
 
      auto transaction = MakeTransaction([&](){ v1.resize(v1_old_size); v2.resize(v2_old_size);});
 
      v1.push_back(x1);
      throw std::exception();
      v2.push_back(x2);
 
      transaction.success = true;
   }
};

@Loic Joly: Le paragraphe que tu cites commence quand même par : "Unless otherwise specified", et ca peut facilement devenir le cas pour erase(), clear(), pop_back() or pop_front() (vector<T> typiquement, pour erase()).

Modulo l'utilisation d'un type transaction<T> à la place de T, on peut avoir :
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 #include<iostream> #include<functional> #include<memory> #include<tuple> #include<vector> template<class T, class... Args> std::unique_ptr<T> make_unique(Args&&... args) { return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); } struct commited { virtual bool is() const =0; protected: ~commited(){} }; template<class T> struct transaction_handler : virtual protected commited { using commited::is; template<class F> transaction_handler(F&& f) : value(f) {} std::function<T& ()> value; }; template<class T1, class T2> struct transaction_value : transaction_handler<T1>, transaction_handler<T2> { transaction_value() : transaction_handler<T1>(std::bind(&transaction_value::get<0>,this)) , transaction_handler<T2>(std::bind(&transaction_value::get<1>,this)) { } bool is () const { return (bool)tuple; } std::unique_ptr<std::tuple<T1,T2> > tuple; private: typedef std::tuple<T1,T2> T; template<size_t I> typename std::tuple_element<I,T>::type& get() { return std::get<I>(*tuple); } }; template<class T> struct transaction { typedef T type; template<class U> transaction(U u) : handler(u) { } bool is() const { return handler->is(); } T& value() { return handler->value(); } private: std::shared_ptr<transaction_handler<T> > handler; }; template<class C1, class C2> void make_transaction(C1& c1, typename C1::value_type::type v1, C2& c2, typename C2::value_type::type v2) { typedef typename C1::value_type::type T1; typedef typename C2::value_type::type T2; auto p = std::make_shared<transaction_value<T1,T2> >(); auto t = make_unique<std::tuple<T1,T2> >(v1,v2); c1.push_back(p); c2.push_back(p); swap(p->tuple,t); } struct A { int i;}; struct B { int i; }; int main() { std::vector<transaction<A> > v1; std::vector<transaction<B> > v2; A a; a.i = 10; B b; b.i = 20; make_transaction(v1,a,v2,b); std::cout << v1.back().value().i << v2.back().value().i; }
transaction<T> se comporte un peu comme boost::optional. Si is() retourne false alors il n'y a pas de valeur, et sinon la valeur peut être retournée par value(). Ainsi si le second push_back échoue, alors la première transaction n'aura aucune valeur. Et l'utilisation d'un swap permet d'activer une valeur pour les deux conteneurs en même temps.

Pour les exceptions :

Si l'un des deux make_ lance, alors les conteneurs ne sont pas modifiés et le tuple et/ou la transaction sont détruits.
Si l'un des deux push lance, alors les éventuelles transactions qui auront été insérées n'auront aucune valeur, et le tuple sera détruit.

Pour les threads (en supposant que les opérations d'insertion sur le conteneur soient thread-safe) :

Lorsqu'un transaction devient active (ie qu'elle a une valeur) alors tout les conteneurs le savent en même temps. Ainsi soit une transaction n'est pas active, soit elle l'est totalement.
L'ordre des éléments dans le conteneur peut être "permuté", mais ça n'a pas forcément d'importance : l'on peut récupérer l'ensemble des informations d'une transaction depuis un seul conteneur (pas implémenté, mais ça doit être faisable).

Pour la généralisation :

Le code actuel ne fonctionne que si les deux types sont différents, il faudrait ajouter une indirection pour rendre cela possible.
Le rendre fonctionnel pour utiliser plus de deux types n'en probablement pas le plus évident. Utiliser boost::mpl et boost::pp sera surement nécessaire.

Quelques défauts, qui peuvent en être selon le contexte :

De nombreuses indirections (à voir si elles ont un coût trop important ou pas).
Un ensemble de transactions potentiellement inactives en cas de trop nombreuses exceptions.
L'ordre non conservé.
Le besoin d'utiliser une capsule.
Des allocations dynamiques qui peuvent être problématiques.

30/07/2012, 09h37
Niark13

@Ekleog : Oui, en copiant/collant, j'ai voulu renommer ma méthode privée (qui s'appellait aussi push_back) pour plus de clarté, et j'avais oublié cet appel. J'ai corrigé, merci.
30/07/2012, 11h38
gbdivers

Déjà pas mal de réponses. Pour vous aider, voici une petite liste de critères de jugement pour l'exercice. Ce n'est pas moi qui vais juger votre travail, mais chacun est libre de juger le travail des autres. Par contre, je donne des critères pour que vous puissiez juger par vous même de la qualité de votre code et que l'on puisse discuter des critères. Par contre, il faut attendre au moins le 20 août avant de commencer à juger les autres codes. Merci

Les basiques
* permet de faire un push_back d'une valeur sur un vecteur ?
* permet de faire un push_back de plusieurs valeurs sur un vecteur ?
* permet de faire un push_back d'une valeur sur plusieurs vecteurs ?
* permet de faire un push_back de plusieurs valeurs sur plusieurs vecteurs ?

Les conteneurs
* permet d'utiliser d'autres conteneurs que vector ?
* permet d'utiliser en même temps des conteneurs de types différents ?
* permet de paramétrer les fonctions à appeler (push_back, insert, append, etc) ?

Évolutivité du code
* facilité de changer la transaction ?
* facilité pour ajouter beaucoup de push dans une transaction
* possibilité d'écrit la transaction sur plusieurs lignes ?
* transaction déterminée à l'exécution ?

Divers
* intégrité de la transaction en cas d'exception ?
* intégrité de la transaction dans un contexte multi thread ?
* intégrité de la transaction dans un contexte multi processus ou distribué ?

avec des lambdas comme suggere par Arzar:

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 <iostream>
#include <functional>
 
struct Transaction
{
    typedef std::function<void()>   Operation;
    Operation perform;
    Operation undo;
    bool success;
 
    Transaction(Operation perform, Operation undo)
        :   perform(perform)
        ,   undo(undo)
        ,   success(false)
    {
        perform();
    }
 
    ~Transaction()
    {
        if (!success)
        {
            std::cerr << "Rollback" << std::endl;
            undo();
        }
    }
};
 
#include <vector>
#include <list>
 
using namespace std;
 
int main()
{
    vector<int> integers;
    vector<float> floats;
    list<double> doubles;
 
    Transaction t1 ([&](){ integers.push_back(1); }, [&](){ integers.pop_back(); });
    Transaction t2 ([&](){ floats.push_back(1.0f); }, [&](){ floats.pop_back(); });
    throw 0;
    Transaction t3 ([&](){ doubles.push_back(1.0); }, [&](){ doubles.pop_back(); });
    t1.success = t2.success = t3.success = true;
}

plus compact ca commence a etre difficile. Mais sans lambda, c'est pas aussi simple :(

30/07/2012, 12h47
Ekleog

Citation:

Envoyé par screetch

avec des lambdas comme suggere par Arzar

Mais... mais... c'était moi le premier à avoir utilisé des lambdas. :cry:
30/07/2012, 13h04
screetch

bah oui mais c'est Arzar qui m'a conseille directement les lambdas :)

Je propose d'utiliser Boost.ScopeExit de la manière suivante:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 template<typename C> class SafeTransaction { C v1, v2; public: template <typename T> void push_back(T x1, T x2) { bool commit = false; v1.push_back(x1); BOOST_SCOPE_EXIT((&commit)(&v1)) { if (!commit) v1.pop_back(); } BOOST_SCOPE_EXIT_END v2.push_back(x2); commit = true; } };
Bien sur ce n'est pas parfait mais ça à l'avantage d'être simple et donc ça ne mérite pas forcement une classe dédiée. Il suffit de mettre un scope exit avec le code de rollback après chaque opération et c'est bon.

12/08/2012, 21h30
Klaim

Ca donne une bonne idée de l'interet d'avoir un scope_exit dans le langage, comme en D.
12/08/2012, 21h51
Kalith

Citation:

Envoyé par piemur2000

Je propose d'utiliser Boost.ScopeExit de la manière suivante:

Je ne connais pas Boost.ScopeExit, mais ne manque-t-il pas un commit = true; juste après le second push_back() ?
13/08/2012, 10h58
piemur2000

Citation:

Envoyé par Kalith

Je ne connais pas Boost.ScopeExit, mais ne manque-t-il pas un commit = true; juste après le second push_back() ?

Oui bien sur, c'est corrigé.

Citation:

Envoyé par Klaim

Ca donne une bonne idée de l'interet d'avoir un scope_exit dans le langage, comme en D.

En effet, ça évite les try catch imbriquée et je trouve que ça clarifie les choses en mettant le code de rollback au niveau de l'opération. Malheureusement, comme ce n'est pas une fonctionnalité du langage c'est un peu moins clair qu'en D.
14/08/2012, 00h24
Klaim

Ils me semble qu'Alexandrescu et Bright l'on proposé pour le prochain standard C++, a coté de "static if". Ou alors je confonds avec une autre feature.
27/08/2012, 09h52
Niark13

Citation:

Envoyé par Klaim

Ils me semble qu'Alexandrescu et Bright l'on proposé pour le prochain standard C++, a coté de "static if". Ou alors je confonds avec une autre feature.

Tu ne confondrais pas avec les template constraints (qu'ils ont effectivement groupées avec static if) ?
02/09/2012, 18h36
screetch

alors la solution de germinolegrand qui etait assez originale, c'etait quoi?

sinon, on devait voter ou commenter le code posté?

une solution

Arf, oui, je l'ai pas postée du coup :D
Voila donc :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
template <class C, class T>
static inline void safePushBack(C& cont, const T& i)
{
    cont.insert(std::end(cont), i);
}
 
template <class C, class T, class ... Args>
static inline void safePushBack(C& cont, const T& i, Args &... args)
{
    cont.insert(std::end(cont), i);
    try
    {
        safePushBack(args...);
    }
    catch(...)
    {
        cont.erase(std::end(cont));
        throw;
    }
}

et une utilisation possible :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
std::vector<unsigned int> v1, v2;
std::set<float> s1;
unsigned int a(1), b(2), c(3), d(4), e(5);
float f(2.4);
 
try
{
    safePushBack(v1, a, v2, d, v1, b, v2, c, v1, e, s1, f);
}
catch(...)
{
    //transaction échouée
}

A vos commentaires ;)

edit : oh, je vois que j'ai oublié les static_assert... je vais les ajouter...
edit 2: bah en fait non, mon compilo est pas très coopératif avec les decltype sur pointeur de fonction membre...

02/09/2012, 20h26
germinolegrand

Voilà, code posté, désolé, pas possible d'ajouter des static asserts.

J'aime vraiment beaucoup les templates variadiques :) J'ai quand même une suggestion d'amélioration : sans changer la manière de l'utiliser, on peut profiter de la sémantique de mouvement et éviter quelques copies :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class C, class T>
static inline void safePushBack(C& cont, T&& i)
{
    cont.insert(std::end(cont), std::move(i));
}
 
template <class C, class T, class ... Args>
static inline void safePushBack(C& cont, T&& i, Args&&... args)
{
    cont.insert(std::end(cont), std::move(i));
    try
    {
        safePushBack(std::forward<Args>(args)...);
    }
    catch(...)
    {
        cont.erase(std::end(cont));
        throw;
    }
}

Et puis, juste pour s'amuser :
Si on considère une version où seul un conteneur est rempli, on peut faire en sorte d'appeler automatiquement reserve sur les conteneurs le supportant (seulement std::vector à ma connaissance ?) :

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
 
// Vérifier si le conteneur dispose de la fonction 'reserve' :
template <class C>
struct hasReserve
{
    template <typename U>
    static std::true_type  dummy(decltype(((U*)0)->reserve(1))*);
 
    template <typename U>
    static std::false_type dummy(...);
 
    static const bool value = decltype(dummy<C>(0))::value;
};
 
// Appeler 'reserve' si le conteneur le supporte : 
// (je suppose que tout conteneur qui dispose de 'reserve' dispose aussi de 'capacity' et 'size')
template <class, bool>
struct doReserve;
 
template <class C>
struct doReserve<C, true>
{
    static void reserve(C& cont, size_t n)
    {
        size_t tmpSize = cont.size() + n;
        if (tmpSize > cont.capacity())
            cont.reserve(tmpSize);
    }
};
 
template <class C>
struct doReserve<C, false>
{
    static void reserve(C& cont, size_t n)
    {
    }
};
 
template <class C>
void reserve_more(C& cont, size_t n)
{
    doReserve<C, hasReserve<C>::value>::reserve(cont, n);
}
 
// Compter le nombre d'arguments d'un template variadique :
template<typename ... Args>
struct countArgs;
 
template<typename T, typename ... Args>
struct countArgs<T, Args...>
{
    static const size_t value = countArgs<Args...>::value + 1;
};
 
template<>
struct countArgs<>
{
    static const size_t value = 0;
};
 
// Enfin, la fonction 'safePushBack' :
template <class C, class T>
static inline void safePushBack_(C& cont, T&& i)
{
    cont.insert(std::end(cont), std::move(i));
}
 
template <class C, class T, class ... Args>
static inline void safePushBack_(C& cont, T&& i, Args&&... args)
{
    cont.insert(std::end(cont), std::move(i));
    try
    {
        safePushBack_(cont, std::forward<Args>(args)...);
    }
    catch(...)
    {
        cont.erase(std::end(cont));
        throw;
    }
}
 
template <class C, class ... Args>
static inline void safePushBack(C& cont, Args&&... args)
{
    reserve_more(cont, countArgs<Args...>::value);
    safePushBack_(cont, std::forward<Args>(args)...);
}

03/09/2012, 01h31
germinolegrand

Voyons voir... :)
pour compter la taille d'un variadic, il y a l'operateur sizeof...()
pour la move sémantique, j'y avais pensé, mais le problème c'est qu'on ne peut pas distinguer les conteneurs des données dans les variadics, ce qui fait que là tes conteneurs sont aussi déplacés (vous confirmez ?).

Voir 40 message(s) de cette discussion en une page