Discussion :

[ramislebob]

bonjour,
j'utilise un set de pair d'unsigned int avec une function comparative sur le deuxième élément de ma pair.

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
 
#include <set>
typedef unsigned short ushort;
 
struct compPairBySecond {
  bool operator() (const std::pair<ushort,ushort>& lhs, const std::pair<ushort,ushort>& rhs) const
  {return lhs.second < rhs.second;}
};
 
typedef std::set<std::pair<ushort,ushort> , compPairBySecond> mySet;
 
int main(){
	mySet set;
	for (int i=0; i<2 ; ++i){
		auto res = set.insert(std::pair<ushort,ushort>(i,1));
		cout << "Insertion result: " << res.second << "\n";
	}
 
	for (auto it = set.cbegin(); it != set.cend(); ++it)
		cout << "(" << it->first << ", " << it->second << ")\n";
 
        return 0;	
}

Pourquoi la deuxième insertion pair<1,1> ne marche pas?

Si je change ma fonction de comparaison pour utiliser un inférieur ou égal cela marche...
Je ne comprend pourquoi...
j'imaginais qu'avec < j'aurai en résultat le set suivant: { (0,1) , (1, 1) }
et avec un <= dans l'autre sens: { (1, 1), (0, 1) }

Pourquoi ça ne marche pas et ne puis je pas obtenir le premier cas?
Dans l'example sur sur cplusplus.com ils utilisent un inférieur strict... (http://www.cplusplus.com/reference/set/set/set/)

[jo_link_noir]

Si la comparaison se fait sur le second élément, la valeur du premier n'a aucune importance, donc {0,1} et {1,1} sont identique du point de vue du set. Et comme set ne garde qu'un ensemble unique, seule la dernière paire est présente.

http://cpp.developpez.com/faq/cpp/?p...l-operateur-lt
Simplifié avec std::tie: http://en.cppreference.com/w/cpp/utility/tuple/tie

[Iradrille]

Simplifié avec std::tie: http://en.cppreference.com/w/cpp/utility/tuple/tie

Je connaissais pas, c'est pratique.

std::tie(a, b) est bien l'équivalent de std::make_tuple(std::ref(a), std::ref(b)); ?

[ramislebob]

Si la comparaison se fait sur le second élément, la valeur du premier n'a aucune importance, donc {0,1} et {1,1} sont identique du point de vue du set. Et comme set ne garde qu'un ensemble unique, seule la dernière paire est présente.

http://cpp.developpez.com/faq/cpp/?p...l-operateur-lt
Simplifié avec std::tie: http://en.cppreference.com/w/cpp/utility/tuple/tie

Ok je vois, le test d'unicité est fait comme ça:

Pour tout a et b, si a<b est faux et b<a est faux, on dit que a et b sont équivalents (cette relation doit être une relation d'équivalence, comme précisée dans la question sur l' opérateur==.

En utilisant un <= dans ma fonction de comparaison, les deux paires sont insérées dans le set mais dans l'ordre (1,1) (0,1). En gros je contourne un peu le problème d'uncité et en devient presque un multi set puisque à aucun éléments ne seront jamais égaux...

En terme de performance, qu'est il mieux? Utiliser un multi-set avec ma comparaison stricte ou bien un set avec un <=?
(J'utilise mon set de pair afin de trier une map par valeur, je sais donc que tous les éléments seront différents.)

[Iradrille]

je ne comprends pas trop comment est fait le test d'égalité. Ma fonction de comparaison entre (0,1) et (1,1) renvoit false comme elle le ferait pour (0,1) et (0,2)... Quelle est la différence? En aucun cas je ne dit au set de ne considérer que la seconde valeur de ma paire pour vérifier l'unicité...

Code :

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

1
2
3
4
5
6
struct compPairBySecond {
  bool operator() (const std::pair<ushort,ushort>& lhs, const std::pair<ushort,ushort>& rhs) const
  {return lhs.second < rhs.second;} // comparaison sur le second élément, on ignore complètement le premier.
};
 
typedef std::set<std::pair<ushort,ushort> , compPairBySecond> mySet;

Autre question: En utilisant un <= dans ma fonction de comparaison, les deux paires sont insérées dans le set mais dans l'ordre (1,1) (0,1). Est ce que cela veut dire que l'uncité du set est contournée et qu'il devient un multi-set? Ça me parait un peu louche...

Çà risque surtout de faire des trucs très bizarre

Code :

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

1
2
3
4
mySet set;
set.insert(std::pair<ushort,ushort>(0, 1)); // set = [ {0,1} ]
set.insert(std::pair<ushort,ushort>(1, 1)); // set = [ {0,1}, {1,1} ]; ordre dépendant de l'implémentation
set.remove(std::pair<ushort,ushort>(2, 1)); // set = [ ] ou [ {0,1} ] ou [ {1,1} ] en fonction de l'implémentation

(J'utilise mon set afin de trier une map par valeur. Je sais que tous les éléments sont donc différents)

Une map est triée, pourquoi utiliser un set ?
Et si tes éléments sont différents, comment tu peux te retrouver dans le cas [ {0,1}, {1,1} ] où tu as deux éléments identiques ?

[ramislebob]

Çà risque surtout de faire des trucs très bizarre

Code :

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

1
2
3
4
mySet set;
set.insert(std::pair<ushort,ushort>(0, 1)); // set = [ {0,1} ]
set.insert(std::pair<ushort,ushort>(1, 1)); // set = [ {0,1}, {1,1} ]; ordre dépendant de l'implémentation
set.remove(std::pair<ushort,ushort>(2, 1)); // set = [ ] ou [ {0,1} ] ou [ {1,1} ] en fonction de l'implémentation

Une map est triée, pourquoi utiliser un set ?
Et si tes éléments sont différents, comment tu peux te retrouver dans le cas [ {0,1}, {1,1} ] où tu as deux éléments identiques ?

mince, tu as répondu pendant que je modifiais mon post précédent car j'avais compris comment ce passait le test d'égalité (négation du test d'infériorité dans les deux sens)...

Je réponds quand même à la question que tu soulèves et explique mon utilisation de ce set de pair.
En fait j'ai une map triée par key. map: (k1, v1), (k2, v2) (k3, v3) ...
et j'ai besoin de l'avoir triée en fonction des valeurs.
dans la map les k1, k2, k3... sont uniques. Les valeurs elles peuvent être identiques.
j'utilise un set de pair pour obtenir (v2, k2) (v1, k1) (v3, k3) si v2 <= v1 <= v3

mais bon je pensais qu'en cas d'égalité des valeurs, la première insérée resterai avant l'autre...

J'en reviens à ma nouvelle question dans mon post précédent que j'ai modifié...
Qu'est il préférable en terme de performance?
un set avec ma comparaison <=
ou un multi-set avec comparaison <

Je suppose le multi-set? Dans ce cas j'obtiendrai bien mon (0, 1) (1, 1) et le test d'égalité (comparaison inverse) est évité

[ramislebob]

PS: ce set de paire est juste utilisé pour un parcours de ma map en ordre de valeur, il n'y aura aucune suppression.

[Iradrille]

J'en reviens à ma nouvelle question dans mon post précédent que j'ai modifié...
Qu'est il préférable en terme de performance?
un set avec ma comparaison <=
ou un multi-set avec comparaison <

Je suppose le multi-set? Dans ce cas j'obtiendrai bien mon (0, 1) (1, 1) et le test d'égalité (comparaison inverse) est évité

Ok pour le set, ça à du sens.

la meilleure solution : soit ce que propose @jo_link_noir avec tie, soit la solution que tu avais dans ton post avant d'edit (basiquement c'est la même chose que tie, sauf que tu le fais à la main).

Code :

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

1
2
3
4
5
6
7
8
struct compPairBySecond {
  bool operator() (const std::pair<ushort,ushort>& lhs, const std::pair<ushort,ushort>& rhs) const
  {
     return std::tie(lhs.second, lhs.first) < std::tie(rhs.second, rhs.first);
     // ou
     return (lhs.second == rhs.second) ? (lhs.first < rhs.first): (lhs.second < rhs.second);
  }
};

edit : un set avec '<=', c'est faux.

[ramislebob]

oui c'est clair qu'un set avec un <= ce n'est pas beau...
j'hésite quand même entre ta deuxième option

Code :

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

return (lhs.second == rhs.second) ? (lhs.first < rhs.first): (lhs.second < rhs.second);

ou bien utiliser un multi-set avec un simple <
Le résultat sera le même.
En terme de performance je suppose que le multiset est peut être plus adapté car il n'y a besoin de faire qu'une seule comparaison (le test d'uncité n'étant pas requis).
J'hésite... je crois que je vais prendre le multiset

[ramislebob]

Merci pour votre aide

[Bousk]

PS: ce set de paire est juste utilisé pour un parcours de ma map en ordre de valeur, il n'y aura aucune suppression.

Mais une map c'est pas déjà triée ?!
Et ça possède des itérateurs pour le parcours.

[ramislebob]

Mais une map c'est pas déjà triée ?!
Et ça possède des itérateurs pour le parcours.

Si mais la map est triée par clefs.
Et j'ai besoin d'avoir un tri par valeurs. Ma méthode est donc d'utiliser un multiset de pair<key,val> ordonné par le second élément de la paire.
Y a t'il une meilleure méthode?

[Bousk]

Perso j'utiliserais un simple vector où je mets toutes les valeurs qui m'intéressent puis je les trie.
Je suis pas convaincu qu'un set soit top pour ça, le tri est réalisé à chaque insertion, avec autant de remaniement de la mémoire. Alors que reserve permettra de consommer exactement ce qui est nécessaire et le sort se fait "in place".

[ramislebob]

Perso j'utiliserais un simple vector où je mets toutes les valeurs qui m'intéressent puis je les trie.
Je suis pas convaincu qu'un set soit top pour ça, le tri est réalisé à chaque insertion, avec autant de remaniement de la mémoire. Alors que reserve permettra de consommer exactement ce qui est nécessaire et le sort se fait "in place".

Oui c'est vrai, dommage qu'il n'y ait pas de reserve pour un set...
Ma map n'a pas beaucoup d'éléments, pour l'instant qu'un ou deux et potentiellement pas plus d'une dizaine. Du coup le set est plus pratique. Je pense que vais rester sur cette option de multiset mais c'est clair que si j'avais plus d'éléments je passerais par un vector.

[white_tentacle]

Perso j'utiliserais un simple vector où je mets toutes les valeurs qui m'intéressent puis je les trie.
Je suis pas convaincu qu'un set soit top pour ça, le tri est réalisé à chaque insertion, avec autant de remaniement de la mémoire. Alors que reserve permettra de consommer exactement ce qui est nécessaire et le sort se fait "in place".

C’est même surtout ce qu’il faut faire. De manière générale, un set ne doit être utilisé que si tu ne maîtrises pas le moment où seront faites tes insertions, et que tu dois garantir que la collection est triée en toute circonstances. Dans pratiquement tous les autres cas, un vector trié « au moment approprié » sera meilleur aussi bien en terme d’utilisation mémoire que de performances.

[stendhal666]

Oui c'est vrai, dommage qu'il n'y ait pas de reserve pour un set...
Ma map n'a pas beaucoup d'éléments, pour l'instant qu'un ou deux et potentiellement pas plus d'une dizaine. Du coup le set est plus pratique. Je pense que vais rester sur cette option de multiset mais c'est clair que si j'avais plus d'éléments je passerais par un vector.

La discussion est résolue et tu as certainement avancé dans ton programme mais si je peux me permettre un ou deux conseils:

• si tu reviens sur cette portion de ton code un peu plus tard et que tu vois un multiset, tu penseras en priorité qu'il peut y avoir deux éléments semblables, pas que tu as réussi à éliminer une comparaison;
• rechercher un élément dans un multiset est plus long que dans un set puisqu'il faut parcourir les éléments égaux le cas échéant;
• pour une dizaine d'éléments au maximum, deux situations: 1) tu accèdes à ces éléments extrêmement fréquemment et tout le long de ton programme: alors trier est une option intéressante 2) tu y accèdes plus rarement ou seulement pendant une courte période de ton programme: tu peux laisser les données non triées, un find tout bête dans la map d'origine prendrait n/2 en moyenne (où n est le nombre d'éléments, voire moins selon les propriétés des paires); trouver dans un multiset prend lg n + (s/2) où s est le nombre d'éléments égaux mais il faut y ajouter la constitution du multiset;
• l'allocation de mémoire pour le contenu d'un vecteur de petite taille peut être fait sur la pile, je ne crois pas que ce soit le cas pour un set: cela pourrait militer pour la solution du vector

En bref, éviter une comparaison ne justifie à mon avis presque jamais une perte de précision sémantique et une recherche pas toujours un tri.

[ramislebob]

La discussion est résolue et tu as certainement avancé dans ton programme mais si je peux me permettre un ou deux conseils:

• si tu reviens sur cette portion de ton code un peu plus tard et que tu vois un multiset, tu penseras en priorité qu'il peut y avoir deux éléments semblables, pas que tu as réussi à éliminer une comparaison;
• rechercher un élément dans un multiset est plus long que dans un set puisqu'il faut parcourir les éléments égaux le cas échéant;
• pour une dizaine d'éléments au maximum, deux situations: 1) tu accèdes à ces éléments extrêmement fréquemment et tout le long de ton programme: alors trier est une option intéressante 2) tu y accèdes plus rarement ou seulement pendant une courte période de ton programme: tu peux laisser les données non triées, un find tout bête dans la map d'origine prendrait n/2 en moyenne (où n est le nombre d'éléments, voire moins selon les propriétés des paires); trouver dans un multiset prend lg n + (s/2) où s est le nombre d'éléments égaux mais il faut y ajouter la constitution du multiset;
• l'allocation de mémoire pour le contenu d'un vecteur de petite taille peut être fait sur la pile, je ne crois pas que ce soit le cas pour un set: cela pourrait militer pour la solution du vector

En bref, éviter une comparaison ne justifie à mon avis presque jamais une perte de précision sémantique et une recherche pas toujours un tri.

Concrètement j'ai juste besoin de parcourir ma map par valeur. Pas de find, pas d'insert, pas de remove. J'ai n'ai pas non plus besoin de le faire souvent, ça reste très ponctuel.
C'est pour cela que j'avais pensé utiliser un set (puis multi-set) mais le fait de garder le vector sur la pile m'a fait changer d'idée. Il est clair que c'est plus propre et plus performant.
Et puis ce n'est pas grand chose à changer, je vais faire ça de suite.

Merci pour vos avis et bon réveillon à tous!

[jo_link_noir]

Je connaissais pas, c'est pratique.

std::tie(a, b) est bien l'équivalent de std::make_tuple(std::ref(a), std::ref(b)); ?

Oui, cela crée une tuple contenant des références.
Je trouve dommage qu'il n'y ai pas d'objet pour optimiser les comparaisons en utilisant une fonction compare (qui retourne -1,0,1) au lieu de a<b puis a==b. Avec des séquences, cela a son importance (std::string par exemple),

le fait de garder le vector sur la pile m'a fait changer d'idée. Il est clair que c'est plus propre et plus performant.

Un vector sur la pile n'est pas quelque chose de trivial. Il faut être sur que la taille de la pile est assez grande. Pour donner un peu de piquant, la taille réservée par le vector est dépendant de l'implémentation de celui-ci. Mais ce n'est pas grave, on peut lui mentir et fourni une zone mémoire pouvant contenir tous les éléments qu'on va y mettre, mais plus petite que la taille demandée. Si on ne l'utilise pas, ce n'est pas grave, c'est juste sale.
Cela dit, std::dynarray ne dépend pas de l'implémentation. Reste à connaître la taille max de la pile et faire un allocateur dédié. Bah oui, par défaut, les containers vont piocher dans le tas.

Tous ça pour dire que si c'est l'argument d'une allocation sur pile qui te fait changer d'avis, c'est une mauvaise raison. Perso, j'aurais choisi la continuité en mémoire des valeurs (donc accès rapide) et l'allocation unique si on utilise les fonctions faites pour (assign/constructeur avec itérateur). Par contre, il faut ajouter la ligne pour trier et celle pour réduire (std::unique ou un filter_iterateur (doit y avoir cela dans boost)).

[ramislebob]

Tous ça pour dire que si c'est l'argument d'une allocation sur pile qui te fait changer d'avis, c'est une mauvaise raison. Perso, j'aurais choisi la continuité en mémoire des valeurs (donc accès rapide) et l'allocation unique si on utilise les fonctions faites pour (assign/constructeur avec itérateur). Par contre, il faut ajouter la ligne pour trier et celle pour réduire (std::unique ou un filter_iterateur (doit y avoir cela dans boost)).

Hum... une question, en quoi est ce plus rapide de parcourir une mémoire continue plutôt qu'une linked list? Le temps d'accès random oui, c'est clair, mais si je veux juste parcourir ma liste/array/vector c'est pareil non? Dans les deux cas on connait l'adresse mémoire du prochain élément...
En quoi cette opération:

Code :

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

1
2
3
4
 
        std::vector<std::pair<int,int> > myVect = getMyVectorOrderedByValue();
	for (auto it = myVect.cbegin(); it != myVect.cend(); ++it)
		cout << "(" << it->first << ", " << it->second << ")\n";

est elle plus rapide qu'avec un set?

Code :

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

1
2
3
4
 
        std::set<std::pair<int,int> > mySet = getMySetOrderedByValue();
	for (auto it = set.cbegin(); it != set.cend(); ++it)
		cout << "(" << it->first << ", " << it->second << ")\n";

Autre question, je n'arrive pas à trouvé explicitement que lorsque j'utilise un vecteur avec une taille réservée, l'allocation est faite sur la pile.
Si je fais ceci:

Code :

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

std::vector<std::pair<int,int>> myVect(getMapSize());

Que ce passe-t'il? Comme la taille n'est pas statique, j'ai tendance à penser que ça partira dans la heap... (comment on dit heap en français?)
Si j'ai bien compris tous les éléments sont initialisés avec le constructeur par défault? Est ce vrai?

Si je ne donne pas la taille initiale du vecteur dans le constructeur comme si dessus mais utilise reserve

Code :

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

1
2
3
 
std::vector<std::pair<int,int>> myVect;
myVect.reserve(getMapSize());

C'est forcément alloué dans la heap non? Si j'ai bien compris la taille du vecteur sera de 0. Donc la mémoire n'est pas initialisé si?

Allez dernière question, que vaut il mieux privilégier:

Code :

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

1
2
3
4
5
6
 
std::map<int,int> myMap = getMap();
std::vector<std::pair<int,int>> myVect;
myVect.reserve(getMapSize());
for (auto it = myMap.cbegin(); it != myMap.cend(); ++it)
        myVect.push_back(std::pair<ushort, ushort>(it->first, it->second));

ou

Code :

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

1
2
3
4
5
6
 
std::map<int,int> myMap = getMap();
std::vector<std::pair<int,int>> myVect(getMapSize());
int i=0;
for (auto it = myMap.cbegin(); it != myMap.cend(); ++it)
        myVect[i++] = std::pair<ushort, ushort>(it->first, it->second);

Est ce équivalent? Personnellement ayant des gros doutes sur le fait que le vector serait sur la pile en utilisant le constructeur avec la taille dynamique je pencherai plus pour la première option et le réserve car je suppose que le bloc de mémoire global est réservé sans initialiser chaque élément avec le constructeur par défault de ma pair<int, int>. Est ce correct?

Bonne année tout le monde!

[jo_link_noir]

Hum... une question, en quoi est ce plus rapide de parcourir une mémoire continue plutôt qu'une linked list? Le temps d'accès random oui, c'est clair, mais si je veux juste parcourir ma liste/array/vector c'est pareil non?

Justement non, list/map/set fragmentent la mémoire car chaque élément est alloué indépendamment. Cela augmente le risque de cachemiss et le nombre de déréférencement. De plus, le compilateur ne peut pas faire convenablement certaines optimisations (ex: préchargement de la mémoire).

Autre question, je n'arrive pas à trouvé explicitement que lorsque j'utilise un vecteur avec une taille réservée, l'allocation est faite sur la pile.

Normal, l'allocation est faîte sur le tas (heap). À moins de définir un allocateur perso (second paramètre template du vector) le comportement par défaut est d'utiliser ::operator new.

Si je fais ceci:

Code :

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

std::vector<std::pair<int,int>> myVect(getMapSize());

Si j'ai bien compris tous les éléments sont initialisés avec le constructeur par défault? Est ce vrai?

Oui depuis c++11. Avant, c'est une copie d'un paramètre construit avec le constructeur par défaut si non fournit. Mais il existe un constructeur prenant des iterateurs qui permettent d'initialiser les valeurs sans passer par le constructeur par défaut.

Si je ne donne pas la taille initiale du vecteur dans le constructeur comme si dessus mais utilise reserve

Code :

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

1
2
3
 
std::vector<std::pair<int,int>> myVect;
myVect.reserve(getMapSize());

[...] Si j'ai bien compris la taille du vecteur sera de 0. Donc la mémoire n'est pas initialisé si?

C'est bien cela. Mais il faut savoir que push_back contient un test conditionnel qui casse le pipeline et ralentit le programme quand le compilateur ne fait pas bien les optimisations (et cela arrive).

Allez dernière question, que vaut il mieux privilégier:

Code :

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

1
2
3
4
5
6
 
std::map<int,int> myMap = getMap();
std::vector<std::pair<int,int>> myVect;
myVect.reserve(getMapSize());
for (auto it = myMap.cbegin(); it != myMap.cend(); ++it)
        myVect.push_back(std::pair<ushort, ushort>(it->first, it->second));

ou

Code :

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

1
2
3
4
5
6
 
std::map<int,int> myMap = getMap();
std::vector<std::pair<int,int>> myVect(getMapSize());
int i=0;
for (auto it = myMap.cbegin(); it != myMap.cend(); ++it)
        myVect[i++] = std::pair<ushort, ushort>(it->first, it->second);

Est ce équivalent? Personnellement ayant des gros doutes sur le fait que le vector serait sur la pile en utilisant le constructeur avec la taille dynamique je pencherai plus pour la première option et le réserve car je suppose que le bloc de mémoire global est réservé sans initialiser chaque élément avec le constructeur par défault de ma pair<int, int>. Est ce correct?

Entre les deux, je préfère la seconde solution pour la raison évoquée plus haut concernant push_back. Et aussi parce que l'initialisation d'une pair de short est 'rapide'.

D'ailleurs, en utilisant une structure intermédiaire, il est possible de ne rien initialiser:

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
template<class T>
struct uninitialized_storage
{
  uninitialized_storage() {} // constructeur qui n'initialise pas la valeur
 
  operator T & () { return x; }
  operator T const & () const { return x; }
 
private:
  T x;
};
 
int x1; //non initialisé
int x2{}; //initialisé à 0
uninitialized_storage<int> x3; //non initialisé
uninitialized_storage<int> x4{}; //non initialisé
 
using uninitialized_ushort = uninitialized_storage<ushort>;
 
std::vector<std::pair<uninitialized_ushort, uninitialized_ushort>> v(3); // les valeurs ne sont pas initialisées

(C'est dans ces moments-là que vector manque d'une fonction d'initialisation externe du style assign(size_t, RawInitializer, RawCopy).)

Sinon, la forme la plus simple est:

Code :

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

1
2
3
 
std::map<int,int> myMap = getMap();
std::vector<std::pair<int,int>> myVect(myMap.begin(), myMap.end());

Cependant, comme les itérateurs du map sont bidirectionnel, la complexité de std::distance utilisé par le vecteur est de O(n). Un gros hack consiste à wrapper l'itérateur du map dans un itérateur taggué random_access_iterator_tag pour que std::distance(first, last) retourne last-first et que la soustraction retourne myMap.size() ().


Bonne année !