C ++ <algorithm> mise en œuvre expliquée

Question

Lorsque je voudrais savoir comment un algorithme en C++ de la Bibliothèque Standard pourrait être mis en œuvre, je regarde toujours http://en.cppreference.com/w/cpp/algorithmqui est une grande source. Mais parfois, je ne comprends pas les détails de l'implémentation et j'aurais besoin d'une explication des raisons pour lesquelles quelque chose est fait de cette manière. Par exemple, dans la mise en œuvre de l' std::copy_n, pourquoi la première affectation est faite en dehors de la boucle et la boucle commence donc avec 1?

template< class InputIt, class Size, class OutputIt>
OutputIt copy_n(InputIt first, Size count, OutputIt result)
{
    if (count > 0) {
        *result++ = *first;
        for (Size i = 1; i < count; ++i) {
            *result++ = *++first;
        }
    }
    return result;
}

En outre: connaissez-vous un site où c'est possible des implémentations d'algorithmes sont expliqués?

Answer 1

Comparer avec la naïveté de mise en œuvre:

template< class InputIt, class Size, class OutputIt>
OutputIt copy_n(InputIt first, Size count, OutputIt result)
{
  for (Size i = 0; i < count; ++i) {
    *result++ = *first++;
  }
  return result;
}

Cette version est encore une augmentation de la first!

1. count==0, les deux n' 0 par incréments de first.

2. count==1, leur version zéro n'incréments de first. La version ci-dessus ne 1.

3. count==2, leur version ne un incréments de first. La version ci-dessus ne 2.

Une possibilité est de gérer les itérateurs qui sont dereferenceable, mais pas incrementable. Au moins dans la STL jours, il y a une distinction. Je ne suis pas sûr si l'entrée des itérateurs ont cette propriété d'aujourd'hui.

Ici est un bug qui semble se produire si vous utilisez l'implémentation naïve, et Ici est une partie de la documentation qui prétend "Le réel de l'opération de lecture est effectuée lors de l'itérateur est incrémenté, et non pas lorsqu'elle est déréférencé."

Je n'ai pas encore retrouvé le chapitre et le verset de l'existence de dereferenceable, non incrementable entrée des itérateurs. Apparemment, le standard de détails, combien de fois copy_n déréférence l'entrée/sortie des itérateurs, mais ne détaille pas combien de fois il incrémente le itérateur d'entrée.

La naïveté de la mise en œuvre des incréments de l'itérateur d'entrée une fois de plus que la non-implémentation naïve. Si nous avons un seul passage d'entrée itérateur qui se lit sur ++ avec l'espace est insuffisant, copy_n pourrait bloquer inutilement sur la poursuite de l'entrée, en essayant de lire des données au-delà de la fin du flux d'entrée.

Answer 2

C'est juste une mise en œuvre. La mise en œuvre dans GCC 4.4 est différent (et conceptuellement plus simple):

template<typename InputIterator, typename _Size, typename _OutputIterator>
_OutputIterator
copy_n(_InputIterator __first, _Size __n,
     _OutputIterator __result)
{
  for (; __n > 0; --__n)
{
  *__result = *__first;
  ++__first;
  ++__result;
}
  return __result;
}

[Avec un peu de handwaving, puisque je n'ai fourni la mise en œuvre au moment de l'entrée itérateur est un itérateur d'entrée, il y a une mise en œuvre différente pour le cas où l'itérateur est un itérateur à accès aléatoire] Que la mise en œuvre a un bug en ce qu'il incrémente le itérateur d'entrée une fois de plus que prévu.

La mise en œuvre dans GCC 4.8 est un peu plus compliquée:

template<typename _InputIterator, typename _Size, typename _OutputIterator>
_OutputIterator
copy_n(_InputIterator __first, _Size __n,
     _OutputIterator __result)
{
  if (__n > 0)
{
  while (true)
    {
      *__result = *__first;
      ++__result;
      if (--__n > 0)
    ++__first;
      else
    break;
    }
}
  return __result;
}

Answer 3

Avec l'implémentation naïve, vous incrémenter la valeur d'entrée itérateur n temps, pas seulement n - 1 temps. Ce n'est pas seulement potentiellement inefficace (depuis les itérateurs peuvent avoir arbitraire et arbitrairement cher types définis par l'utilisateur), mais il peut également être carrément indésirable lors de l'itérateur d'entrée ne supporte pas de sens "passé-la-fin" de l'état.

Pour un exemple simple, lisez n éléments d' std::cin:

#include <iostream>    // for std:cin
#include <iterator>    // for std::istream_iterator


std::istream_iterator it(std::cin);
int dst[3];

Avec la naïveté de la solution, le programme bloque sur le dernier incrément:

int * p = dst;

for (unsigned int i = 0; i != 3; ++i) { *p++ = *it++; }   // blocks!

La bibliothèque standard de l'algorithme n'a pas de bloc:

#include <algorithm>

std::copy_n(it, 3, dst);    // fine

---

Noter que la norme n'est pas fait explicitement parler itérateur incréments. Il est dit (25.3.1/5) copy_n(first, n, result) a

Effets: Pour chaque entier non négatif i < n, effectue *(result + i) = *(first + i).

Il n'existe qu'une note dans 24.2.3/3:

[input iterator] les algorithmes peuvent être utilisés avec istreams comme la source de l'entrée les données grâce à l' istream_iterator classe de modèle.

Answer 4

En raison de la vérification initiale

if (count > 0)

nous savons que nombre > 0, donc l'auteur de ce code sentait qu'il n'avait pas besoin de test contre le comte de nouveau jusqu'à ce qu'il atteint la valeur de 1. Rappelez-vous que "pour" exécute le test conditionnel au début de chaque itération, non pas à la fin.

Size count = 1;
for (Size i = 1; i < count; ++i) {
    std::cout << i << std::endl;
}

imprime rien.

Ainsi, le code permet d'éliminer une branche conditionnelle, et si la Taille est de 1, il élimine la nécessité pour incrémenter/ajuster la "première" - d'où le fait qu'elle soit une pré-incrémentation.