Discussion :

[camboui]

Bonjour

Voici une implémentation possible du std::swap que nous connaissons tous.

Code :

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

1
2
3
4
5
6
template<class T>
void swap(T & l, T & r)
{	T tmp = std::move(l);
	l = std::move(r);
	r = std::move(tmp);
}

Et voici le principe de sa généralisation à n paramètres.

Code :

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

1
2
3
4
5
6
7
8
template<class T>
void multiple_swap(T & v0, T & v1, ..., T & vn)
{	T tmp = std::move(v0);
	v0 = std::move(v1);
	v1 = ...;
	... = vn;
	vn = std::move(tmp);
}

Existe-t-il en standard ? (pas à ma connaissance)
Une idée d'implémentation généralisée ?
Pour certains algos il serait utile je pense, car pour l'instant il m'arrive d'appeler le swap standard en cascade, ce qui induit des copies évitables.

Merci

[DarkinGoD]

Ce n'est plus vraiment un swap, mais plutôt une rotation.

Si tu peux mettre tes variables dans un container, tu faire appel à std::rotate qui fait le job : il utilise des swap en interne.

Sinon, ça doit pouvoir se faire avec du parameter-pack.

[DarkinGoD]

Voici avec le parameter-pack, enjoy.

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
 
#include <iostream>
#include <string>
 
template<typename T>
T & rotation_detail(T & elt, T & last)
{
    elt = std::move(last);
    return last;
}
 
template<typename T, typename ... Args>
T & rotation_detail(T & elt, T & elt2, Args & ... args)
{
    elt = std::move(elt2);
    return rotation_detail(elt2, args...);
}
 
template<typename T, typename ... Args>
void rotation(T & elt, Args & ... args)
{
    T tmp = elt;
    T & last = rotation_detail(elt, args...);
    last = std::move(tmp);
}
 
int main()
{
    std::string a = "a";
    std::string b = "b";
    std::string c = "c";
    std::string d = "d";
    std::string e = "e";
 
    std::cout << a << b << c << d << e << std::endl;
 
    rotation(a, b, c, d, e);
 
    std::cout << a << b << c << d << e << std::endl;
}

Le lien vers coliru.

Après, on pourrait déplacer les rotation_detail dans des namespaces details et ajouter un check sur les types pour éviter un message de compilation obscure, voir ce lien stackoverflow.

[jo_link_noir]

Je propose cette version:

Code :

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

1
2
3
4
5
6
7
8
9
10
template<class T, class... Ts>
void rotate(T& x, Ts& ... xs)
{
    T tmp = std::move(x);
    [&](auto&... lhs){
        [&lhs...](auto&... rhs){
            (void(lhs = std::move(rhs)), ...);
        }(xs..., tmp);
    }(x, xs...);
}

=> https://wandbox.org/permlink/ccEMBfqXOwmFysfK

Qui au passage soulève un bug dans clang: il faut mettre lhs... pour que cela compile, et avec il y a un avertissement comme quoi lhs n'est pas utilisé (mais tout passe bien).

[DarkinGoD]

Pas mal l'astuce du double lambda pour le décalage, je plussoie !

[jo_link_noir]

Je me suis rendu compte après coup qu'on peut faire simplement std::tie(x, xs...) = std::forward_as_tuple(std::move(xs)..., std::move(tmp));.

[camboui]

Merci à tous

(Je ne sais trop qui a résolu à ma place, mais ce n'est pas important )

J'ai vu en effet que std::rotate utilise std::swap en interne, ce qui n'est pas efficace AMA.

Donc remerci, je vais pouvoir trouver une solution sur base de vos réponses exhaustives

[koala01]

Salut,

J'ai vu en effet que std::rotate utilise std::swap en interne, ce qui n'est pas efficace AMA.

Pourquoi ne le serait-ce pas Après tout, std::swap et std::rotate sont des fonctions templates, c'est à dire, forcément inlne dont le code binaire peut être fortement optimisé en fonction du type des données à manpuler:

• pour les type primitifs, trois XOR suffisent
• pour les types personnalisé, l'opérateur d'affectation par déplacement en évite la copie

Et, surtout, comment voudrais tu t'y prendre autrement

Il n'y a guère que pour les listes que l'on peut trouver "plus efficace" et pour lesquelles une spécialisation pourrait s'avérer avantageuse

[jo_link_noir]

Si tu as un std::array<T, 3>, l'algorithme efficace est de faire

Code :

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

1
2
3
4
5
 
auto tmp = std::move(a[0]);
a[0] = std::move(a[1]);
a[1] = std::move(a[2]);
a[2] = std::move(tmp);

(Pas de std::swap).

Or, avec std::swap, même s'il utilise 2 std::move en interne, il y a potentiellement des copies (pour les objets non-déplaçable, mais copiable) et quelques opérations en plus dans les autres cas (par exemple, un swap de unique_ptr va faire 2 copies de pointeur).

[koala01]

Je n'avais, je l'avoue, pas envisagé cette possibilité.

Mais elle ne résout que la moitié du problème de la rotation, car elle implique que l'on puisse savoir à la compilation le nombre d'élément qui devront être déplacés.

Tu me diras que c'est déjà un grand pas dans la bonne direction, mais std::rotate doit aussi pouvoir fonctionner avec ... un nombre d'éléments qui ne serait connu qu'à l'exécution, et, du coup, je ne vois pas bien comment nous pourrions nous y prendre autrement qu'en effectuant un swap (mais je suis un peu fatigué pour le moment )

[camboui]

Résonnons du point de vue théorique.

La rotation de 3 éléments c'est 4 opérations (copies ou déplacements ou XOR, à ta guise).
Cette même rotation, si faite avec deux std::swap successifs, c'est 2x3=6 opérations.

En généralisant à n, une rotation directe de n éléments c'est (n+1) opérations.
Via des std::swap ce serait (3xn) opérations (chaque std::swap fait bien 3 opérations, n'est-ce-pas ?).
En bref, (n+1) < (3n)

Suposons même que le compilateur soit si malin qu'il "voit" et optimise les std::swap successifs pour se restreindre à (n+1) opérations. Ça restera de la spéculation, le doute subsistera. Utiliser le bon algo dès le départ reste la meilleure garantie pour obtenir la bonne performance.

De toutes façons je vais tester, et je verrai bien en pratique

(EDIT: entre temps jo_link_noir est intervenu)

[camboui]

... mais std::rotate doit aussi pouvoir fonctionner avec ... un nombre d'éléments qui ne serait connu qu'à l'exécution, et, du coup, je ne vois pas bien comment nous pourrions nous y prendre autrement qu'en effectuant un swap (mais je suis un peu fatigué pour le moment )

Et bien voici une solution testée rapidement.

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
template<class IT>
void iter_rotate(IT first, IT last)
{
	--last; // check range [first,last[ has at least 2 elements !
	typename IT::value_type tmp = std::move(*first);
	for (;first != last ; ++first)
		*first = std::move(*(first + 1));
	*last = std::move(tmp);
}
 
int main()
{
	std::vector<unsigned> v{ 0,1,2,3,4,5,6,7,8,9 };
	iter_rotate(v.begin(), v.end());
	return 0;
}

[jo_link_noir]

J'ai vérifié les implémentations de libstdc++ et libc++/rangev3, et en fait il y a usage de std::move quand cela est possible: càd quand les itérateurs n'appartiennent pas à ForwardIterator. Avec un cas particulier si std::next(first) == middle qui utilise une variable temporaire + std::move(std::next(first), last, first).

[camboui]

Voici une ébauche de ce dont j'ai besoin, un accumulateur d'objets à déplacer.

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
template<class IT>
void iteriter_rotate_right(IT first, IT last)
{
	--last; // check range [first,last[ has at least 2 elements !
	typename IT::value_type::value_type tmp = std::move(**last);
	do
	{
		**last = std::move(**(last - 1));
	} while (--last != first);
	**first = std::move(tmp);
}
 
template<unsigned D, class It>
class delayed_mover
{
	std::array<It, D> vi;
	unsigned vicnt{};
	void rotate_unchecked()
	{
		iteriter_rotate_right(vi.begin(), vi.begin() + vicnt);
	}
public:
	void push_unchecked(It i) noexcept
	{
		vi[vicnt++] = i;
	}
	void rotate()
	{
		if (vicnt > 1)
			rotate_unchecked();
		vicnt = 0;
	}
	void push(It i)
	{
		if (D == vicnt)
		{
			rotate_unchecked();
			vicnt = 1;
		}
		vi[vicnt++] = i;
	}
};
 
int main()
{
	std::vector<std::string> v{ "zéro","un","deux","trois","quatre","cinq","six","sept","huit","neuf" };
	delayed_mover<5, std::vector<std::string>::iterator> dr;
	std::vector<std::string>::iterator it = v.begin();
	dr.push_unchecked(++it);
	dr.push(++it);
	dr.push(++it);
	dr.push(++it);
	dr.push(++it);
	dr.push(++it);
	dr.push(++it);
	dr.push(++it);
	dr.rotate();
	return 0;
}

J'ai des objets à déplacer, en fonction de la progression d'un algo.
Soit je les déplace au fur et à mesure via un std::swap, soit je les accumule et les déplace en une fois. Mais comme je ne peux pas prédire combien il y en aura, au lieu d'utiliser un container dynamique (qui risque de tuer les perfs avec ses allocations intempestives) j'utilise un std::array<> qui déplacera les objets par paquets si nécessaire.