07-stdlib.Rmd

# Introduction à la librairie standard

Nous allons dans ce chapitre très parcellaire présenter rapidement quelques
*containers* proposés par la librairie standard de C++.

## Vecteurs

Les vecteurs `std::vector` de la librairie standard sont beaucoup plus 
performants que les vecteur de R. Il s'agit d'une classe \og templatée\fg ;
on peut avoir des vecteurs de n'importe quels objets. Par exemple,
un `std::vector<int>` est un vecteur d'entiers.

La fonction `wrap` de Rcpp permet de créer des vecteurs de R à partir de 
vecteurs standards: les `std::vector<int>` seront transformés en `IntegerVector`,
les `std::vector<double>` seront transformés en `NumericVector`, et les
`std::vector<std::string>` en `CharacterVector`.

### `push_back`, `pop_back` et `resize`

Le premier intérêt des vecteurs standard est leur capacité à changer de longueur
sans perte grâce à `push_back`, et rétrécir
avec `pop_back`. Leur taille peut aussi être modifiée avec `resize`. L'exemple
suivant déclare un vecteur de longueur 4, y ajoute un élément égal à 5.25,
l'enlève, et redimensionne le vecteur à la taille de 8 éléments.

```{Rcpp}
#include <Rcpp.h>
#include <vector>
using namespace Rcpp;
//[[Rcpp::export]]
void demo_vector_1() {
  std::vector<double> x(4);
  for(auto a : x) Rcout << a << " "; Rcout << "\n";
  x.push_back(5.25);
  for(auto a : x) Rcout << a << " "; Rcout << "\n";
  x.pop_back();
  for(auto a : x) Rcout << a << " "; Rcout << "\n";
  x.resize(8);
  for(auto a : x) Rcout << a << " "; Rcout << "\n";
}
```

**Note :** j'ai mis `#include <vector>` pour le principe. En fait l'inclusion
de `Rcpp.h` suffit, car elle implique l'inclusion de nombreuses composantes 
de la librairie standard, dont celle-ci.

```{r prompt = TRUE}
demo_vector_1()
```


### Contrôler la capacité avec `resize`

En pratique, les vecteurs standard allouent plus de mémoire que nécessaire ;
on parle de \og réserve\fg\ de mémoire. Quand la réserve est épuisée, un
nouveau vecteur est créé avec une réserve plus importante, et l'ancien vecteur
y est recopié. Cela représente une perte de temps, mais la réserve doublant
de taille à chaque fois que cela se produit, cela ne peut pas se produire
trop souvent. On peut anticiper sur les possibilités de changements de taille avec `reserve`. 


```{Rcpp}
#include <Rcpp.h>
#include <vector>
using namespace Rcpp;

template<typename T>
inline void affiche(const std::vector<T> & x) {
  Rcout << "adresse = " << &x[0] << ", ";
  Rcout << "size = " << x.size() << ", ";
  Rcout << "capacity = " << x.capacity() << "\n";
}

//[[Rcpp::export]]
void demo_vector_2(int n, bool res) {
  std::vector<int> x;
  std::cout << "vecteur vide :\n";
  affiche(x);

  if(res) {
    x.reserve(n);
    std::cout << "vecteur avec une réserve :\n";
    affiche(x);
  }

  for(int i = 0; i < n; i++) {
    x.push_back(3);
  }
  std::cout << "vecteur dans lequel on a 'poussé' " << n << " éléments :\n";
  affiche(x);
}
```

```{r prompt = TRUE}
demo_vector_2(4, TRUE)
demo_vector_2(4, FALSE)
demo_vector_2(9, FALSE)
```

Ceci permet par exemple d'extraire les élements non `NA` d'un vecteur sans avoir à les compter avant: 

```{Rcpp}
#include <Rcpp.h>
using namespace Rcpp;

//[[Rcpp::export]]
NumericVector extrait_non_NAs(NumericVector x) {
  std::vector<double> R; // vecteur de doubles, vide par défaut
  R.reserve( x.size() ); // on prévoit de pouvoir étendre la taille de R jusqu'à x.size
  for(auto a : x) {
    if(!NumericVector::is_na(a))
      R.push_back(a);
  }
  return wrap(R);
}
```

### `move` et `emplace_back`

En C++11 est apparu l'opérateur *move* qui permet d’éviter la copie. Nous allons l'illustrer ci-dessous sur sur des `std::string`.

```{Rcpp}
#include <Rcpp.h>
using namespace Rcpp;

//[[Rcpp::export]]
void moves() {
  std::string s1("Bonjour cher ami !");
  std::string s2 = s1; // copie
  Rcout << "s1 = " << s1 << " adresse = " << (void *) &s1[0] << "\n";
  Rcout << "s2 = " << s2 << " adresse = " << (void *) &s2[0] << "\n";
  std::string s3( std::move(s1) );
  Rcout << "s1 = " << s1 << "\n";
  Rcout << "s3 = " << s3 << " adresse = " << (void *) &s3[0] << "\n";
}
```

```{r prompt = TRUE}
moves()
```

**Note :** Cet exemple pourrait échouer ; si la chaîne `s1` fait moins de 16 caractères, elle est copiée dans `s3` malgré l'opérateur `move`!

Il est donc plus efficace pour remplir un vecteur `V` d'utiliser `V.push_back(std::move(x))` que `V.push_back(x)` -- si on n'a pas besoin de `x` après. La solution idéale est (normalement) l'utilisation d'`emplace_back` qui permet de construire directement l'objet en dernière position du vecteur.

```{Rcpp}
#include <Rcpp.h>
#include <ctime>

//[[Rcpp::export]]
void temps_de_remplissage() {
  clock_t t = clock();
  for(int k = 0; k < 100; k++) {
    std::vector<std::string> V;
    V.reserve(1e5);
    for(int i = 0; i < 1e5; i++) {
      std::string s(50, 'a');
      V.push_back(s);
    }
  }
  t = clock() - t;
  Rcpp::Rcout << "V rempli en " << (double) t / CLOCKS_PER_SEC / 100. << " s\n";
  
  t = clock();
  for(int k = 0; k < 100; k++) {
    std::vector<std::string> V;
    V.reserve(1e5);
    for(int i = 0; i < 1e5; i++) {
      std::string s(50, 'a');
      V.push_back( std::move(s) );
    }
  }
  t = clock() - t;
  Rcpp::Rcout << "V rempli en " << (double) t / CLOCKS_PER_SEC / 100. << " s\n";

  t = clock();
  for(int k = 0; k < 100; k++) {
    std::vector<std::string> V;
    V.reserve(1e5);
    for(int i = 0; i < 1e5; i++) {
      V.emplace_back(50, 'a');
    }
  }
  t = clock() - t;
  Rcpp::Rcout << "V rempli en " << (double) t / CLOCKS_PER_SEC / 100. << " s\n";
}
```

Voilà le résultat. Le gain de temps peut être beaucoup plus important si on manipule de grosses structures (et non comme ici des chaînes de caractères de longueur 50, qui se copient très vite).

```{r cache = TRUE}
temps_de_remplissage() 
```

**Note :** Les 
Nous reviendrons sur ce sujet dans le chapitre sur la programmation objet.

## Pairs & tuples

Définir une paire :
```{Rcpp}
#include <Rcpp.h>
using namespace Rcpp;

//[[Rcpp::export]]
void exemple_de_paire() {
  std::pair<int, double> x;
  x.first = 10;
  x.second = 11.25;
  Rcpp::Rcout << "x.first = " << x.first << "\n";
  Rcpp::Rcout << "x.second = " << x.second << "\n";
}
```

On peut bien sûr faire des vecteurs de paires.
Pour ne pas alourdir la syntaxe utilisons `typedef` pour définir `pts` comme 
abréviation de `std::pair<double, double>`:

```{Rcpp}
#include <Rcpp.h>
using namespace Rcpp;

typedef std::pair<double, double> pts;

//[[Rcpp::export]]
void pts_vector() {
  std::vector<pts> x;
  for(int i = 0; i < 10; i++) {
    x.push_back( std::make_pair(R::rnorm(0,1), R::rnorm(0,1)) );
  }
  std::sort(x.begin(), x.end());
  // afficher contenu
  for(auto & a : x) {
    Rcout << "(" << a.first << "," << a.second << ")\n";
  }
}
```


```{Rcpp}
#include <Rcpp.h>
using namespace Rcpp;

//[[Rcpp::export]]
void exemple_de_tuple() {
  std::tuple<double, double, int> x;
  x = std::make_tuple(0.25, 0.8, 1);
  Rcout << "(" << std::get<0>(x) << "," << std::get<1>(x)
        << "," << std::get<2>(x) << ")\n";
}
```


## Quelques algorithmes

`std::sort` trie \og en place\fg\ ...

```{Rcpp}
#include <Rcpp.h>
using namespace Rcpp;

//[[Rcpp::export]]
NumericVector trie1(std::vector<double> x) {
  std::sort(x.begin(), x.end());
  return wrap(x);
}
//[[Rcpp::export]]
void trie2(NumericVector x) {
  std::sort(x.begin(), x.end());
}

//[[Rcpp::export]]
NumericVector trie3(std::vector<double> x, int n) {
  std::sort(x.begin(), x.begin() + n);
  return wrap(x);
}
```

Dans la première fonction on a fait une copie de `x` vers un `std::vector<double>`, `x` n'est donc pas modifié.
```{r prompt=TRUE}
x <- runif(6)
x
trie1(x)
x
trie2(x)
x
```

Les *itérateurs* sont une généralisation des pointeurs ; en première approximation vous pouvez voir `x.begin()` et `x.end()` comme des pointeurs sur le début et la fin du vecteur. La fonction `trie3` ne trie que les `n` premiers éléments de `x`:

```{r prompt=TRUE}
trie3(x, 4)
```


TODO `std::fill` et `std::accumulate`

```{Rcpp}
#include <Rcpp.h>
using namespace Rcpp;
//[[Rcpp::export]]
double sum_(NumericVector x) {
  return std::accumulate(x.begin(), x.end(), 0.0);
}
//[[Rcpp::export]]
double prod_(NumericVector x) {
  return std::accumulate(x.begin(), x.end(), 1.0, std::multiplies<double>());
}
```


```{r prompt=TRUE, fig.width = 6, fig.height = 3, fig.align = 'center', cache=TRUE}
x <- runif(1e6); 
mbm <- microbenchmark::microbenchmark(sum_(x), sum(x))
ggplot2::autoplot(mbm)
mbm <- microbenchmark::microbenchmark(prod_(x), prod(x))
ggplot2::autoplot(mbm)

```

## Maps

TODO

## Heap

TODO