Vérifier qu'un itérateur précède un autre

Bonjour, Dans le cadre de programmation par contrat, je cherche à pouvoir vérifier qu'un itérateur précède un autre. J'illustre ma question avec l'exemple suivant, une boucle dont l'utilisateur me fournit le début et la fin :

 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

/**
 * \brief Loop
 * \attention T must implement operator++() and operator!=(const T&)
 * \param begin Begin of the loop
 * \param end End of the loop
 * \pre begin precedes end
 */
template <typename T>
void loop(const T& begin, const T& end)
{
  T run = begin;
  while(run != end)
  {
    /* do something with run */
    ++run;
  }
}

loop(0,10);

std::set<double> x;
x.insert(1.0);
x.insert(2.0);
x.insert(3.0);
loop(x.begin(), x.end());

J'aimerais pouvoir vérifier ma précondition dans un assert. Fondamentalement, ça signifie que si j'applique l'opérateur ++ un nombre suffisant de fois sur begin, j'arrive à end. Dans le cas où l'utilisateur me fournit de mauvais itérateurs, j'ai une boucle infinie. Est-ce détectable d'une façon ou d'une autre, sans justement se retrouver dans une boucle infinie ?

Merci d'avance.

Lu'!

Etant donné que même std::distance demande d'avoir un itérateur last accessible depuis first, je ne pense pas qu'il y aie de moyen de l'exprimer hors du RandomAccessIterator.

C'est bien ce que je crois à la base. Mais il existe peut-être une pirouette à laquelle je n'ai pas pensé.

Bonjour,

Il n'y a pas de solution à cette question à ma connaissance. Le concept que tu cherches à vérifier se nomme reachable dans la norme, c'est un pré-requis aux opérations travaillant sur les ranges (à l'heure actuel définit comme un couple d'itérateur) tu ne peux donc pas utiliser ces opérations pour effecteur cette vérification. Les opérations qu'il reste ne travaillent que sur un seul itérateur, ce qui ne peut pas t'aider AMA.

Effectivement. Je pense que le mieux que je puisse faire est une spécialisation du template pour certains itérateurs. Est-ce qu'il est possible de demander une spécialisation du template pour tous les types numériques d'un seul coup ? Ou bien il faut se les faire un par un (sachant qu'en réalité c'est une classe, c'est pas envisageable) ?

Activer/Désactiver une fonction sous certaines contraintes vérifiables à la compilation ça se fait avec enable_if et des classes de traits. Je dirais le trait is_arithmetic mais comme tu parles de classe à la fin, j'ai un doute.

Par contre il y a un rapport avec la première question ou pas ?

Par exemple :

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

#include<iostream>
#include<type_traits>

template<class T>
typename
    std::enable_if<!std::is_arithmetic<T>::value,int>
        ::type
    foo(T&&)
{ return 0; }


template<class T>
typename
    std::enable_if<std::is_arithmetic<T>::value,int>
        ::type
    foo(T)
{ return 1; }

int main()
{ std::cout << foo(1) << std::endl; }

(On peut utiliser enable_if d'autre facon, l'idée c'est qu'il soit présent, c'est d'ailleurs surment pas en retour qu'il est le mieux, mais c'est juste un exemple)

Une autre solution c'est de mettre en place un tag dispatching :

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

#include<iostream>
#include<type_traits>

template<class T>
int foo_impl(T&&,std::false_type)
{ return 0; }

template<class T>
int foo_impl(T,std::true_type)
{ return 1; }

template<class T>
auto foo(T&& t)
{ return foo_impl(std::forward<T>(t),typename std::is_arithmetic<T>::type()); }

int main()
{ std::cout << foo(1) << std::endl; }

Ici j'ai utilisé true/false_type mais c'est pas important, l'idée c'est de calculer un type grâce aux paramètres template et d'avoir différente spécialisation suivant chacun de c'est type.

Idéalement http://nt2.metascale.fr/doc/html/the_boost_dispatch_library.html arrivera peut-être dans boost un jour.

Un petit rapport oui. Spécialiser mon template pour ajouter un assert lorsque le type le permet est une solution. Mais juste pour du debug, c'est un peu lourd…

Par contre, je suis encore en C++98 ici, les classes de trait ça me tente pas pour le moment. Je crois que je vais juste faire confiance à l'utilisateur.

Note pour les curieux : le contexte est un "super-iterateur" à plusieurs dimensions. Le genre qui permet de faire ceci :

 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

std::set<double> x1; for(unsigned long int i = 0; i < 10; ++i) x1.insert((double)i);
std::set<double> x2; for(unsigned long int i = 0; i < 20; ++i) x2.insert(2.0*(double)i+3.14);
std::vector< std::set<double> > X;
X.push_back(x1);
X.push_back(x2);

// A partir d'ici, je ne connais pas la taille de X à la compilation
std::vector<std::set<double>::const_iterator> begin;
std::vector<std::set<double>::const_iterator> end;
for(unsigned long int i = 0; i < X.size(); ++i)
{
  begin.push_back(X[i].begin());
  end.push_back(X[i].end());
}

// Affiche toutes les combinaisons avec un élément dans chaque sous-ensemble
for(SuperIterator it(begin, end); !it.atEnd(); ++it)
{
  for(unsigned long int i = 0; i < it.size(); ++i)
  {
    if(i > 0)
      std::cout << " ";
    std::cout << *(it[i]);
  }
  std::cout << std::endl;
}

En l'occurrence, j'aimerais vérifier que le begin et end que me donne l'utilisateur ne vont pas mener à une boucle infinie.

Même le random access, je ne suis pas sûr que cela soit une garantie suffisante. Cf les buffers cycliques : si on y autorise un cycle, alors il n'y a vraiment ni avant ni après.

Je crains qu'il s'agisse d'un cas de PpC, où on ne peut pas vérifier la précondition à l'exécution. La meilleure façon d'y parvenir, c'est de colmater la fuite d'abstraction induite par les itérateurs -> tu écris loop() pour travailler sur des ranges, et c'est aux ranges d'assurer leur invariant comme quoi on peut aller du début à la fin.

PS: j'ai patché mon second article sur la PpC (§ sur les preuves formelles, et § sur l'utilisation des exceptions; le 3e pour bientôt j'espère)

lmghs, le refactoring de mon code fait justement suite à tes deux articles.

Avec un iterateur classique, tu n'as pas de contexte associé (tu ne sais pas quelle est le conteneur). Vérifier que les 2 itérateurs se suivent n'est pas suffisant en soi, tu peux avoir quelque chose comme ça :

1
2
3
4
5

vector<int> a(10);
vector<int> b(10);
auto first = begin(a);
auto last = end(b);
assert(is_ordered_iterator(first, last); // sera vrai

Ce qui est problématique, puisque les itérateurs ne viennent pas du même conteneur. Pour vérifier correctement les choses, il faudrait vérifier le contexte :

1
2
3

assert(is_from_container(first, a));
assert(is_from_container(last, a)); // error
assert(is_ordered_iterator(first, last);

Avec un conteneur du type vector (données contiguë), tu n'es pas obligé de faire un boucle, tu peux tester les adresses mémoire

1
2
3

bool is_ordered_iterator(auto first, auto last) {
    return &(*first) < &(*last);
}

Si tu ne peux conserver que les itérateurs, tu n'as pas d'autres choix que de mettre le contexte dans l'itérateur, c'est à dire de créer un itérateur personnalisé, qui contient le conteneur.

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

template<class Container> 
struct DebugIterator : typename Container::iterator { // bof, private
    Container const& container;
};

template<class Container>
DebugIterator<Container> begin(Container const& c) { 
    return DebugIterator(c, begin(c));
}

template<class Container>
DebugIterator<Container> end(Container const& c) { 
    return DebugIterator(c, end(c));
}

template<class Iterator>
bool is_from_container(Iterator first, Iterator last) {
    return first.container == last.container;
}

template<class Iterator>
bool is_ordered_iterator(Iterator first, Iterator last) {
    return from_same_container(first, last) && (first.container < last.container);
}

Par contre, pour que cela fonctionne, il faut que tout ton code soit en programmation générique, pour pouvoir substituer DebugIterator aux std::iterator. (remarque : si tu n'utilises pas begin/end en fonction libre, il faudra du coup créer des versions debug des conteneur, pour que c.begin() et c.end() retourne un DebugIterator)

Cela devrait marcher (en corrigeant le code que j'ai écrit à l'arrache)

HS : tu devrais pas appeler tes itérator begin et end

Hum…

Une solution pourrait être de choisir une largeur max pour le range et le parcourir pour vérifier que sa largeur est bien inférieure. Ce n'est pas vraiment contraignant si on la prend vraiment large. Je ne compte pas travailler avec des set contenant plusieurs milliards d'éléments.

Qu'en pensez-vous ?

 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

template <typename T>
bool range_width_is_lower_than(const T& begin, const T& end, unsigned long int max_width)
{
  try
  {
    unsigned long int i;
    T incr;
    for(incr = begin, i = 0; incr != end && i < max_width; ++incr, ++i);
    return (incr == end);
  }
  catch(...) { return false; }
}

template <typename T>
void loop(const T& begin, const T& end)
{
  assert(range_width_is_lower_than(begin, end, 10000000));

  T run = begin;
  while(run != end)
  {
    /* do something with run */
    ++run;
  }
}

@Caduchon: Incrémenter après un itérateur de fin est invalide (pour les InputIterator). Du coup ta fonction a un comportement indéfinit.

@lmghs: Avec reference_wrapper plutôt, pour obtenir l'affectation par copie (demandé par le concept d'itérateur). Après c'est quand même un peu étrange de réinjecter le conteneur dans l'élément qui est sensé l'abstraire, mais si ça reste uniquement comme outil de debug pourquoi pas.

D'ailleurs je crois que Eric Niebler parle de cette solution (ou une variante proche) dans sa proposition pour l'ajout du concept de Range au standard. Il l'a rejette pour des raisons de compatibilité et pour éviter d’alourdir le concept d'itérateur (à vérifier quand même).

Oui, mais si je passe par la fin je m'arrête. C'est seulement si l'utilisateur m'envoie de la merde que j'aurai un comportement indéfini. Si à ce moment là ça crash, c'est toujours mieux que de n'avoir rien testé.

Oui, sauf qu'un comportement indéterminé (pas indéfini, je me suis trompé) c'est pas forcément un crash, ça peut être n'importe quoi. Après dans la pratique c'est probable que le comportement soit rien du tout ou un crash à cause d'un accès interdit. Mais un comportement indéterminé pour un mécanisme de sécurité, je trouve ça un peu paradoxal quand même.

Tu devrais creuser du côté du mécanisme proposé par lmghs qui doit bien fonctionner.

C'est gbdivers qui a proposé un truc (dans ce fil – ou alors tu fais allusion au passage en full-ranges et 0-itérateurs?)

Ceci dit, si le comportement est indéfini en Debug, il le sera aussi en Release, avec le mécanisme de sécurité désactivé : il pourra y avoir des boucles infinies ou des gros plantages pour accès hors bornes.