#+TITLE : Prise de notes TD 4I400 PSCR
Yann Thierry-Mieg ([email protected]) 4I400
unsigned int length(const char *string);
char *newcopy(const char *string);Pour faire ça proprement, on créé un fichier strutil.h (fichier d’en-tête), dans lequel on met les signatures, et un autre fichier pr.c, dans lequel on mettra l’implémentation.
// Dans un fichier d'en tête (en .h)
#pragma once
#include <cstring>
namespace pscr {
size_t length(const char *string);
char *newcopy(const char *string);
}On peut aussi se débrouiller avec ifndef, define, endif, à la C.
La vraie manière, à la Linus :
// Dans un fichier source, .cpp
#include "strutil.h"
#include <cstring>
#include <cstdlib>
namespace pscr {
size_t length(const char *string)
{
size_t size = 0;
for ( ; *string; string++, size++);
return size;
}
char *newcopy(const char *string)
{
size_t n = length(string);
char *ptr = new char[n+1];
while (*string) {
*ptr++ = *string++;
}
*ptr = '\0';
return ptr - n;
}
}#include <cstring>
char *newcopy(const char *string)
{
size_t n = length(string);
char *ptr = new char[n+1] ;
memcpy(ptr, string, n + 1);
return ptr;
}#include "strutil.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace pscr;
using namespace std;
int main()
{
const char *str = "Hello World !";
char *copy = newcopy(str);
printf("%p %s %lu\n", str, str, length(str));
printf("%p %s %lu\n", copy, copy, length(copy));
delete[] copy;
return 0;
}Remarque :
str est imprimé comme un string, et pas comme une adresse. Pour faire ce qu’on a fait avec printf, on doit écrire :
cout << (void *)str << " " << str << " " << length(str) << endl;
cout << (void *)copy << " " << copy << " " << length(copy) << endl;Alors qu’on penserait que les instructions suivantes fonctionneraient :
cout << str << " " << *str << " " << length(str) << endl;
cout << copy << " " << *copy << " " << length(copy) << endl;En fait cout voit que str pointe sur un caractère et voit le caractère ‘\0’. Il interprète ça comme une string.
On n’arrive pas à forcer une erreur de segmentation, malgré un débordement de tampon forcé ? (Ni en C avec malloc, ni en C++ avec new).
Pour compiler tout ça :
g++ -std=c++1y -O0 -g3 -Wall -c -o "/chemin/vers/strutil.o" /chemin/vers/strutil.cpp
g++ -std=c++1y -O0 -g3 -Wall -c -o "/chemin/vers/exo1.o" /chemin/vers/exo1.cpp
g++ -o /chemin/vers/exo1 /chemin/vers/strutil.o /chemin/vers/exo1.o
/chemin/vers/exo1 # pour lancer le programme
valgrind --leak-check=full --track-origins=yes /chemin/vers/exo1 # pour vérifier les fuites de mémoireOn s’est permis de faire un Makefile.
#pragma once
#include <cstring>
#include <iostream>
namespace pscr {
class String {
friend std::ostream & operator<< (ostream &os, const pscr::String &str);
const char *str;
public:
String(const char* ori);
size_t length() const;
};
std::ostream & operator<< (ostream &os, const pscr::String &str);
}#include "string.h"
#include "strutil.h"
#include <iostream>
using namespace std;
namespace pscr {
String::String(const char *ori):str(ori)
{}
size_t String::length() const
{
return pscr::length(str);
}
ostream & operator<< (ostream &os, const pscr::String &s)
{
return os << s.str;
}
}abc pointe vers un endroit de la mémoire où il n’y a plus rien de légal.
#pragma once
#include <cstddef> // size_t
#include "strutil.h"
namespace pr {
class String {
const char * str;
public:
String(const char *cstr=""): str(newcopy(cstr)){};
virtual ~String() { delete [] str;}
size_t length() const { return pr::length(str);};
};
} // fin namespace prLe problème, c’est que vu que l’appel String ne se résout pas vers une fonction définie par l’utilisateur : elle résout vers une version par défaut du compilateur.
La version par défaut du compilateur construit par copie.
Elle copie donc la référence str, aliasant la chaîne déjà dans le tas.
Quand je sors du scope avec les crochets, le stack frame du pointeur est dépilé, et donc le destructeur est appelé par défaut.
Donc le contenu du tas pointé par abc et def et désalloué.
Quand je fais référence au même octet avec abc , j’ai :
Undefined behaviour. On a pas forcément toujours segfault.
Deuxième problème.
= va se résoudre sur la version par défaut de l’opérateur =. Va juste copier la référence (pointeur) str, on va avoir le même problème en pire.
Sauf que l’autre chaîne du tas n’aura plus de référence, et donc on a une fuite.
Si la classe contient un pointeur, il va falloir redéfinir le constructeur, le destructeur, l’opérateur = et la copie.
En se servant des primitives de la semaine dernière :
#pragma once
#include <cstddef> // size_t
#include "strutil.h"
namespace pr {
class String {
const char * str;
public:
// Cteur avec constante
String(const char *cstr=""): str(newcopy(cstr)){};
// Dteur
virtual ~String() { delete [] str;}
// Taille
size_t length() const { return pr::length(str);};
// Cteur par copie
String(const String &other) {
str = newcopy(other.str);
}
// Opérateur =
String & operator= (const String &other) {
if (&other != this) {
delete[] this->str;
str = newcopy(other.str);
}
}
};
} // fin namespace prDans tous les cas où on a des pointeurs dans les classes, il faut absolument définir ces choses-là.
Implémentons nous-même la classe Vector. On a de la généricité (on peut définir des Vector de int ou float, ou autre chose)
Quand on a une classe générique, on écrit le code de l’implantation directement dans le fichier d’en-tête (en effet, on a besoin du code de l’implantation à chaque fois que la classe générique est instanciée sur un type simple, ce qui se fait aussi dans un fichier d’en-tête).
// Vector.h ou un truc du genre
#pragma once
#include <cstddef> // size_t
namespace pr {
template <typename T>
class Vector {
private:
T *tab;
size_t alloc_sz;
size_t size;
public:
Vector(size_t asize=10) {
size = 0;
alloc_sz = asize;
tab = new T[alloc_sz];
}
~Vector() {
delete[] tab;
}
// On devrait ici avoir un cteur par copie
// Un opérateur =
T& operator[](size_t index) {
return tab[index];
}
const T& operator[](size_t index) const {
return tab[index];
}
void push_back(const t& obj) {
ensureCapacity(size + 1);
tab[size++] = obj;
}
int ensureCapacity(size_t n) {
if (n >= alloc_sz) {
T *tmp = new T[alloc_sz * 2];
for (int i = 0; i < size; ++i) {
tmp[i] = tab[i];
}
delete []tab;
tab = tmp;
return alloc_sz * 2;
}
return alloc_sz;
}
};
}En fait la référence, c’est un pointeur toujours déréférencé.
On doit dédoubler l’opérateur [], parce que probablement quelque part, quelqu’un a écrit un opérateur qui prend une référence const. Si j’essaie de me servir de cet opérateur, je ne peux pas compiler.
Le const après la déclaration d’une méthode porte sur le premier paramètre implicite de la méthode, le this.
Pourquoi alloc_sz * 2 ? La réponse en cours d’ALGAV (en gros, croissance exponentielle de la taille du conteneur garantit un appel logarithmique en la taille à la fonction de grossissement, qui est coûteuse).
// list.h ou un truc du genre
#pragma once
#include <cstddef> // size_t
namespace pr {
template <typename T>
class list {
struct Chainon {
T data;
Chainon *next;
Chainon(const T& data, Chainon *next) : data(data),next(next) {}
};
Chainon *tete;
public:
list() {
tete = nullptr;
}
void push_front(const T& data) {
tete = new Chainon(data,tete);
}
T& operator[] (size_t index) {
Chainon *cur = tete;
for (int i = 0; i < index; ++i) {
cur = cur->next;
}
return cur->data;
}
const T& operator[] (size_t index) const {
Chainon *cur = tete;
for (int i = 0; i < index; ++i) {
cur = cur->next;
}
return cur->data;
}
};
}La meilleure manière d’accéder au nombre d’éléments stockés dans la table (size), c’est d’enregistrer cette valeur au fur et à mesure qu’on rajoute des valeurs.
Le calcul de la taille requiert d’itérer sur tous les éléments du vecteur, puis sur tous les éléments de la liste chaînée : obtenir la taille d’une liste chaînée simple est une opération non-triviale, de complexité au pire cas O(n).
On se permet donc de créer un champ dans privé qui contient la taille, initialisé dans les constructeurs (pour permettre la bonne valeur d’être mise lors d’une construction par copie).
On donne ici notre implémentation complète de la table de hachage, qui se sert autant qu’il est possible des fonctions de la bibliothèque standard (plutôt que nos implémentations).
#include <iostream>
#include <fstream>
#include <regex>
#include <chrono>
#include <vector>
#include <utility>
#include <forward_list>
using namespace std;
template <typename K, typename V>
class HashMap {
struct Entry {
const K key;
V value;
Entry(const K& key, const V& value) : key(key), value(value) {}
};
std::vector <std::forward_list<Entry>> buckets;
size_t nb_stored_values;
public:
HashMap(size_t size) {
buckets.resize(size);
nb_stored_values = 0;
}
HashMap() {
buckets.resize(256);
nb_stored_values = 0;
}
V* get(const K& key) {
size_t h = std::hash <K>()(key);
h = h % buckets.size();
for (Entry& ent : buckets[h]) {
if (ent.key == key) {
return &ent.value;
}
}
return nullptr;
}
bool put(const K& key, const V& value) {
size_t h = std::hash <K>()(key);
h = h % buckets.size();
for (Entry& ent : buckets[h]) {
if (ent.key == key) {
ent.value = value;
return true;
}
}
buckets[h].push_front(Entry(key, value));
this->nb_stored_values++;
return false;
}
bool del(const K& key) {
size_t h = std::hash <K>()(key);
h = h % buckets.size();
auto prev = buckets[h].before_begin();
for (auto it = buckets[h].before_begin();
it != buckets[h].end();) {
prev = it;
if ((++it)->key == key) {
buckets[h].erase_after(prev);
nb_stored_values--;
return true;
}
}
return false;
}
size_t nb_buckets() const {
return buckets.size();
}
size_t size() const {
return nb_stored_values;
}
void grow() {
size_t former_size = buckets.size();
HashMap nouvelle_map(2 * former_size);
K temp_key;
V temp_value;
size_t temp_nb_values = 0;
for (int i = 0; i < former_size ; i++) {
while (buckets[i].empty() != 1) {
temp_key = buckets[i].front().key;
temp_value = buckets[i].front().value;
buckets[i].pop_front();
nb_stored_values--;
nouvelle_map.put(temp_key, temp_value);
temp_nb_values++;
}
}
buckets.swap(nouvelle_map.buckets);
this->nb_stored_values = temp_nb_values;
nouvelle_map.buckets.clear();
}
};
int main()
{
HashMap<int,int> test;
test.put(1,15);
cout << *(test.get(1)) << endl;
cout << test.nb_buckets() << endl;
cout << test.size() << endl;
test.grow();
cout << test.nb_buckets() << endl;
cout << test.size() << endl;
cout << *(test.get(1)) << endl;
test.put(2,16);
cout << test.size() << endl;
return 0;
}Retour sur l’expansion de foreach
for (T& elt : vec) {
//body
}Correspond à :
for (auto it = vec.begin(), end = vec.end();
it != end;
++it) {
T& elt = *it;
// body
}Les conditions pour que ça marche :
- auto a,b requiert que a et b aient le même type
- conteneur doit disposer des fonctions begin et end qui rendent chacun un itérateur
- itérateur doit disposer d’un opérateur !=, doit disposer d’un opérateur ++ (pré-incrément), et d’un opérateur *
template <typename T>
class Vector<T> {
T *tab;
size_t size;
size_t alloc_size;
public:
typedef T * iterator;
typedef const T * const_iterator;
iterator begin() {
return tab;
}
iterator end() {
return tab + size;
}
const_iterator begin() const {
return tab;
}
const_iterator end() const {
return tab + size;
}
}Supposons que l’itérateur est simplement un pointeur nu vers T.
Est-ce que les opérations par défaut sur les pointeurs nus se conforment au contrat demandé par l’expansion de la boucle foreach ?
- On a bien un opérateur != fonctionnel entre deux adresses : il donne bien la sémantique qu’on veut.
- On a bien un opérateur ++ : il augmente l’adresse de la taille de l’objet pointé : nous fait augmenter d’une case exactement, bien ce qu’on demande.
- On a bien un opérateur * : il déréférence l’adresse du machin pointé, ce qui correspond bien à une référence (pointeur toujours déréférencé)
Si je pose begin = &toto[0] et end = &toto[size], ça marche (voir la méthode plus haut, avec la coquetterie du typedef)
La même question, avec une liste chaînée.
template <typename T>
class List<T> {
struct Chainon {
T donnee;
T* suivant;
};
struct Chainon *tete;
public:
class iterator {
Chainon *courant;
public:
iterator(Chainon *courant : courant(courant)) {}
iterator& operator++() {
return courant->suivant;
}
T& operator*() {
return courant->donnee;
}
bool operator!=(const iterator& other) {
return (cur != other.cur);
}
};
class const_iterator {
const Chainon *courant;
public:
const_iterator(const Chainon *courant : courant(courant)) {}
const_iterator& operator++() {
return courant->suivant;
}
const T& operator*() {
return courant->donnee;
}
bool operator!=(const const_iterator& other) {
return (cur != other.cur);
}
};
const_iterator begin() const {
return const_iterator(tete);
}
const_iterator end() const {
return const_iterator(nullptr);
}
iterator begin() {
return iterator(tete);
}
iterator end() {
return iterator(nullptr);
}
}On va devoir définir l’opérateur ++ pour faire cur = cur->suivant;
On va devoir définir l’opérateur * pour aller chercher juste donnee, plutôt que le chaînon entier.
!= n’a pas besoin de manipulation.
end() devra rendre un nullptr begin() rendra tete
On va créer un itérateur sur notre table de hachage.
On va avoir dans la classe itérateur un itérateur sur le vecteur de liste et un itérateur sur une liste :
vit : vector<forward_list<Entry>>::iterator lit : forward_list<Entry>::iterator
vit va pointer sur la case du vecteur lit va pointer sur l’entrée
la fonction begin va rendre la première entrée valable la fonction end va rendre vit = &vector[size] (past the end) et lit = nullptr.
Fonction find
template <typename iterator, typename T>
iterator find(iterator begin, iterator end, const T& target)
{
for (auto it = begin; it != end; ++it) {
if (*it == target) return it;
}
return end;
}A dire vrai, notre code compilera seulement si cette fonction est appelée sur des itérateurs qui disposent d’une opération * et ++ idoine.
Sous des hypothèses généreuses, on peut se permettre de coder de manière aussi triviale.
On stocke l’itérateur retour de la fonction find dans une variable (auto, on s’emmerde pas. En vrai conteneur_sur_lequel_on_linvoque::iterator)
Et si la variable est différente de end, alors on peut l’afficher.
Même question avec find_if (on remplace le target par un prédicat, de manière à se donner plus de flexibilité)
bool matches(const T& elt);On s’en fout de ce que matches teste, on veut juste qu’il ait bien cette signature.
template <typename iterator, typename T>
iterator find_if(iterator begin, iterator end, predicate<+> pred)
{
for (auto it = begin; it != end; ++it) {
if (pred(*it)) return it;
}
return end;
}On a trois manières de passer la fonction de test :
- Pointeur de fonction, à la C
- Foncteur, espèce d’objet-fonction
- Lambda, fonction anonyme
La première manière, on écrit la fonction, et on passe le nom de la fonction comme troisième paramètre à la fonction find_if.
La deuxième manière, on définit une struct matcher, par exemple :
struct matcher {
bool operator() (const string &s) {
return s.length() == 3;
}
};Ensuite on instancie la classe en une instance m, et on appelle :
matcher m;
auto it = find_if(vec.begin(), vec.end(), m("un string"))La troisème manière, la plus moderne (supportée depuis C++11) :
auto it = find_if(vec.begin(), vec.end(), [](const string &s) {return s.length() == 3});le type predicate est un concept dont les seules contraintes sont de prendre des arguments et de rendre un booléen.
The concept predicate<F, Args…> specifies that F is a predicate that accepts arguments whose types and value categories are encoded by Args…, i.e., it can be invoked with these arguments to produce a boolean result.
On doit introduire une variable n pour le test.
Pour la solution à la C, on doit créer une globale, ce qu’on ne se permet pas.
Dans la version foncteur, on peut ajouter n comme attribut de la structure matcher (peut-être le seul intérêt du foncteur à ce jour, probablement).
Dans la version lambda, on fait intervenir la liste de capture vue en cours :
auto it = find_if(vec.begin(), vec.end(), [n](const string &s) {return s.length() == 3});[n] : prend la variable n par copie [&n] : prends la variable n par référence [&] : prends toutes les variables que j’utilise, par référence [=] : prends toutes les variables que j’utilise, par copie
Ecrire la fonction createAndWait
Pour créer un thread, on utilise le constructeur de la classe thread:
thread thread(fonction, arg1, arg2, ...);thread a une méthode membre join(), qui permet de join (!).
Dans le choix entre push_back et emplace_back, il faut faire attention : push_back créé un temporaire, puis se sert du constructeur par copie du conteneur pour mettre le temporaire dans le conteneur. emplace_back ne créé pas de temporaire, mais se sert du constructeur par défaut du conteneur pour mettre l’objet à la bonne place.
void createAndWait(int N) {
std::vector<std::thread> threads;
threads.reserve(N);
for (int i = 0; i < N; ++i) {
// OU ALORS, pas les deux
threads.emplace_back(work, i);
threads.push_back(thread(work, i));
// FIN alternative
cout << "Created" << endl;
}
// La suppression des threads
for (int i = 0; i < N; ++i) {
threads[i].join();
}
// Dans sa version foreach, qui ne marche pas parce qu'on a pas de i
for (auto &t : threads) {
t.join();
cout << "Joined " << ++i;
}
}Quels sont les entrelacements possibles ?
[On peut refaire le dessin du flot de contrôle du tableau]
Il y a plein d’exécutions possibles (Combien ?? [on recomptera si on a le temps])
finished < joined (flèche rouge du join) created < joined (ordre du père) started < finished (ordre du fils)
c,s,f,j s,f,c,j s,c,f,j
Jackpot : on se met dans le cas où plusieurs threads manipulent la même variable.
int main()
{
Compte c;
std::vector<std::thread> threads;
threads.reserve(N);
for (int i = 0; i < N; ++i) {
threads.emplace_back(jackpot, std::ref(c));
// On doit, dans le cas des threads, forcer le compilateur
// à accepter la référence. Ou sinon, faire de c un pointeur
// vers Compte et se simplifier la vie.
cout << "created" ;
}
for (int i = 0; i < N; ++i) {
threads[i].join();
}
return 0;
}Dans l’idée en tous cas :
En fait, une référence reste légale en général aussi longtemps que la chose référencée (pas comme les pointeurs).
(sauf dans les programmes multithreadés)
En pratique, on préfèrera se servir des pointeurs, pour ne pas avoir à se servir de std::ref() (qu’on ne se rappellera probablement pas).
On ne sait pas.
On a plusieurs exécutions possibles [refaire le flot d’exécution]
Data race : course pour être le dernier à écrire la variable.
Le thread sera exécuté de manière pseudo-atomique : pour 100 pièces d’or, un thread n’aura pas le temps de se faire commuter.
atomic garantit un certain nombre de choses : Certaines instructions sont atomiques :
- read
- write
- arithmétique simple : ++, +=, -=
Attention : var = var + 1 n’est pas atomique (créé un temporaire) Mais var += 1 ++var est atomique
La solution consiste à mettre atomic sur la variable solde.
Oui le compte peut tomber en négatif.
Il suffit que je me fasse commuter après le test et avant la mise à jour.
Atomic ne garantit que :
- La vérification est atomique
- La mise à jour à atomique
Mais pas d’atomicité entre la vérification et la mise à jour.
Par contre, le solde du compte est cohérent avec les sommes débitées : atomic. (la banque a juste fait crédit sans le vouloir)
On veut implémenter une section critique autour de (test, mise à jour).
On va utiliser un mutex dans la méthode débiter de la classe Compte :
class Compte {
std::mutex m;
public:
// Les autres méthodes ici, tya compris
bool debiter(unsigned int val) {
m.lock();
if (solde >= val) {
solde -= val;
m.unlock();
return true;
}
m.unlock();
return false;
}
};
Utilisons plutôt un unique_lock : pas parce que c’est utile, juste parce qu’on peut.
class Compte {
std::mutex m;
public:
// Les autres méthodes ici
bool debiter(unsigned int val) {
unique_lock<mutex> l(m);
if (solde >= val) {
solde -= val;
return true;
}
return false;
}
};A dire vrai, la vraie bonne manière, c’est de limiter la quantité des échappements possibles de la fonction :
class Compte {
std::mutex m;
public:
// Les autres méthodes ici
bool debiter(unsigned int val) {
m.lock();
bool doit = (solde>=val);
if (doit) solde -= val;
m.unlock();
return doit;
}
};Dans cette version-là (quand on fait attention à ne pas se compliquer les choses), unique_lock est effectivement inutile.
En gros, le mutex protège une variable en contraignant ceux qui veulent la modifier, quand le atomic le protège directement.
Si on sait exactement qui va essayer de modifier cette variable (et uniquement à cette condition), alors on n’a plus besoin d’utiliser atomic si on prend bien garde à contraindre tous les candidats à la modification à acquérir le verrou.
Dans le OO, on a la garantie que les variables privées d’une classe ne peuvent être manipulées que par les méthodes de la classe.
Pas de constructeur par copie : les mutex ne sont pas copiables, et la version par défaut du contructeur par copie copie tous les éléments.
On doit écrire notre propre constructeur par copie.
class Compte {
Compte(const Compte &c) {
c.m.lock(); // Ou unique_lock<mutex> l(c.m);
this->solde = c.solde;
this->autreattribut = c.autreattribut;
}
};On va manipuler une banque.
On va implémenter des transferts.
On a un thread comptable qui calcule le bilan, soit la somme des soldes.
Interblocage.
Les supports de TD :