6-SmartPointers.ipynb 21.2 KB
Newer Older
1 2 3 4 5 6
{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
7
    "# [Getting started in C++](./) - [Useful concepts and STL](./0-main.ipynb) - [Smart pointers](./6-SmartPointers.ipynb)"
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>Table of contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Introduction\" data-toc-modified-id=\"Introduction-1\">Introduction</a></span></li><li><span><a href=\"#unique_ptr\" data-toc-modified-id=\"unique_ptr-2\"><code>unique_ptr</code></a></span><ul class=\"toc-item\"><li><span><a href=\"#Usage-to-store-data-in-a-class\" data-toc-modified-id=\"Usage-to-store-data-in-a-class-2.1\">Usage to store data in a class</a></span></li><li><span><a href=\"#Releasing-a-unique_ptr\" data-toc-modified-id=\"Releasing-a-unique_ptr-2.2\">Releasing a <code>unique_ptr</code></a></span></li></ul></li><li><span><a href=\"#shared_ptr\" data-toc-modified-id=\"shared_ptr-3\"><code>shared_ptr</code></a></span></li><li><span><a href=\"#Efficient-storage-with-vectors-of-smart-pointers\" data-toc-modified-id=\"Efficient-storage-with-vectors-of-smart-pointers-4\">Efficient storage with vectors of smart pointers</a></span><ul class=\"toc-item\"><li><ul class=\"toc-item\"><li><span><a href=\"#Using-a-trait-as-syntactic-sugar\" data-toc-modified-id=\"Using-a-trait-as-syntactic-sugar-4.0.1\">Using a trait as syntactic sugar</a></span></li></ul></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
26
    "In short, **smart pointers** are the application of [RAII](./2-RAII.ipynb) to pointers: objects which handle more nicely the acquisition and release of dynamic allocation.\n",
27
    "\n",
28
    "There are many ways to define the behaviour of a smart pointer (the dedicated chapter in \\cite{Alexandrescu2001} is a very interesting read for this, especially as it uses heavily the template [policies](../4-Templates/5-MoreAdvanced.ipynb#Policies) to implement his):\n",
29 30 31 32 33 34 35 36 37 38 39
    "\n",
    "* How the pointer might be copied (or not).\n",
    "* When is the memory freed.\n",
    "* Whether `if (ptr)` syntax is accepted\n",
    "* ...\n",
    "\n",
    "The STL made the choice of providing two (and a half in fact...) kinds of smart pointers (introduced in C++ 11):\n",
    "\n",
    "* **unique pointers**\n",
    "* **shared pointers** (and the **weak** ones that goes along with them).\n",
    "\n",
40
    "One should also mention for legacy the first attempt: **auto pointers**, which were removed in C++ 17: you might encounter them in some libraries, but by all means don't use them yourself (look for *sink effect* on the Web if you want to know why).\n",
41 42 43 44 45
    "\n",
    "By design all smart pointers keep the whole syntax semantic:\n",
    "* `*` to dereference the (now smart) pointer.\n",
    "* `->` to access an attribute of the underlying object.\n",
    "\n",
46
    "Smart pointers are clearly a very good way to handle the ownership of a given object. \n",
47
    "\n",
48
    "This does not mean they supersede entirely ordinary (often called **raw** or **dumb**) pointers: raw pointers might be a good choice to pass an object as a function parameter (see the discussion for the third question in this [Herb Sutter's post blog](https://herbsutter.com/2013/06/05/gotw-91-solution-smart-pointer-parameters/)). The raw pointer behind a smart pointer may be accessed through the `get()` method.\n",
49
    "\n",
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
    "Both smart pointers exposed below may be constructed directly from a raw pointer; in this case they take the responsability of destroying the pointer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <memory>\n",
    "#include <iostream>\n",
    "\n",
    "struct Foo\n",
    "{\n",
    "    ~Foo() \n",
    "    {\n",
    "        std::cout << \"Destroy foo\"<< std::endl;\n",
    "    }\n",
    "    \n",
    "};\n",
70
    "\n",
71 72 73 74 75 76 77 78 79 80 81 82 83 84
    "{\n",
    "    Foo* raw = new Foo;\n",
    "    \n",
    "    std::unique_ptr<Foo> unique(raw); // Now unique_ptr is responsible for pointer ownership: don't call delete\n",
    "                                      // on `raw`! Destructor of unique_ptr will call the `Foo` destructor.\n",
    "    \n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
85 86 87 88 89 90
    "## `unique_ptr`\n",
    "\n",
    "This should be your first choice for a smart pointer.\n",
    "\n",
    "The idea behind this smart pointer is that it can't be copied: there is exactly one instance of the smart pointer, and when this instance becomes out of scope the ressources are properly released.\n",
    "\n",
91
    "In C++ 11 you had to use the classic `new` syntax to create one, but C++ 14 introduced a specific syntax `make_unique`:"
92 93 94 95
   ]
  },
  {
   "cell_type": "code",
GILLES Sebastien's avatar
GILLES Sebastien committed
96
   "execution_count": null,
97 98 99 100 101 102
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <memory>\n",
    "\n",
    "{\n",
103
    "    auto ptr = std::make_unique<int>(5);\n",
104 105 106 107 108 109 110 111 112 113 114 115 116 117
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The parenthesis takes the constructor arguments.\n",
    "\n",
    "The smart pointer can't be copied, but it can be moved:"
   ]
  },
  {
   "cell_type": "code",
GILLES Sebastien's avatar
GILLES Sebastien committed
118
   "execution_count": null,
119
   "metadata": {},
GILLES Sebastien's avatar
GILLES Sebastien committed
120
   "outputs": [],
121 122 123 124
   "source": [
    "#include <memory>\n",
    "\n",
    "{\n",
125
    "    auto ptr = std::make_unique<int>(5);\n",
126 127 128 129 130 131
    "    auto copy = ptr; // COMPILATION ERROR: can't be copied!    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
GILLES Sebastien's avatar
GILLES Sebastien committed
132
   "execution_count": null,
133
   "metadata": {},
GILLES Sebastien's avatar
GILLES Sebastien committed
134
   "outputs": [],
135 136
   "source": [
    "#include <memory>\n",
GILLES Sebastien's avatar
GILLES Sebastien committed
137
    "#include <iostream>\n",
138 139
    "\n",
    "{\n",
140 141 142 143 144 145
    "    auto ptr = std::make_unique<int>(5);\n",
    "    auto copy = std::move(ptr); \n",
    "    \n",
    "//  std::cout << \"Beware as now there are no guarantee upon the content of ptr: \" << *ptr << std::endl;\n",
    "// < This line is invalid (using `ptr` after move is undefined behaviour) and makes Xeus-cling crash\n",
    "    \n",
146 147 148 149 150 151 152
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
153
    "As usual with move semantics, beware in this second case: ptr is undefined after the `move` occurred... (this code run on [Coliru](http://coliru.stacked-crooked.com/a/a1aa87e64f64c9e8) leads to a more explicit segmentation fault).\n",
154 155 156 157 158 159 160 161
    "\n",
    "### Usage to store data in a class\n",
    "\n",
    "`std::unique_ptr` are a really good choice to store objects in a class, especially ones that do not have a default constructor. The underlying object may be accessed through reference or raw pointer; usually your class may look like:\n"
   ]
  },
  {
   "cell_type": "code",
162
   "execution_count": null,
163 164 165 166 167 168 169 170 171 172
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <string>\n",
    "\n",
    "// Class which will be stored in another one through a `unique_ptr`\n",
    "class Content\n",
    "{\n",
    "    public:\n",
    "        \n",
173 174
    "        Content(std::string&& text); // notice: no default constructor!\n",
    "    \n",
175
    "    \n",
176
    "    const std::string& GetValue() const;\n",
177 178 179 180 181 182 183 184 185
    "    \n",
    "    private:\n",
    "    \n",
    "        std::string text_ = \"\";\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
186
   "execution_count": null,
187 188 189 190 191 192 193 194 195 196
   "metadata": {},
   "outputs": [],
   "source": [
    "Content::Content(std::string&& text)\n",
    ": text_(text)\n",
    "{ }"
   ]
  },
  {
   "cell_type": "code",
197
   "execution_count": null,
198 199 200 201 202 203 204 205 206 207 208
   "metadata": {},
   "outputs": [],
   "source": [
    "const std::string& Content::GetValue() const\n",
    "{\n",
    "    return text_;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
209
   "execution_count": null,
210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <memory>\n",
    "\n",
    "class WithUniquePtr\n",
    "{\n",
    "    public:\n",
    "    \n",
    "        WithUniquePtr(std::string&& text);\n",
    "\n",
    "        const Content& GetContent() const; // adding `noexcept` would be even better but Xeus-cling \n",
    "                                           // doesn't like it!\n",
    "    \n",
    "    private:\n",
    "    \n",
    "        // A pointer of sort is required here:\n",
    "        // - No default constructor so `Content` can't be stored directly.\n",
    "        // - A reference would mean the object is effectively stored elsewhere; we assume \n",
    "        // we intend here to store the content in the current class.\n",
    "        std::unique_ptr<Content> content_ = nullptr;\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
236
   "execution_count": null,
237 238 239 240 241 242 243 244 245 246
   "metadata": {},
   "outputs": [],
   "source": [
    "WithUniquePtr::WithUniquePtr(std::string&& text)\n",
    ": content_(std::make_unique<Content>(std::move(text)))\n",
    "{ }"
   ]
  },
  {
   "cell_type": "code",
247
   "execution_count": null,
248 249 250 251 252
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <cassert>\n",
    "\n",
253
    "const Content& WithUniquePtr::GetContent() const \n",
254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271
    "{\n",
    "    assert(content_ != nullptr);\n",
    "    return *content_;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Doing so:\n",
    "\n",
    "* `Content` is stored by a `unique_ptr`, which will manage the destruction in due time of the object (when the `WithUniquePtr` object will be destroyed).\n",
    "* `Content` object might be manipulated through its reference; end-user don't even need to know ressource was stored through a (smart) pointer:"
   ]
  },
  {
   "cell_type": "code",
272
   "execution_count": null,
273 274 275 276 277 278 279 280 281 282 283 284 285
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "\n",
    "void PrintContent(const Content& content)\n",
    "{\n",
    "    std::cout << content.GetValue() << std::endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
286
   "execution_count": null,
287
   "metadata": {},
288
   "outputs": [],
289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310
   "source": [
    "{\n",
    "    WithUniquePtr obj(\"My priceless text here!\");\n",
    "    \n",
    "    decltype(auto) content = obj.GetContent();\n",
    "    PrintContent(content);    \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Releasing a `unique_ptr`\n",
    "\n",
    "To free manually the content of a `unique_ptr`:\n",
    "\n",
    "* Use `release()` method:"
   ]
  },
  {
   "cell_type": "code",
311
   "execution_count": null,
312 313 314 315 316 317 318 319 320 321 322 323 324 325
   "metadata": {},
   "outputs": [],
   "source": [
    "{\n",
    "    auto ptr = std::make_unique<int>(5);\n",
    "    ptr.release(); // Beware: `.` and not `->` as it is a method of the smart pointer class, not of the \n",
    "                   // underlying class!\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
GILLES Sebastien's avatar
GILLES Sebastien committed
326
    "* Or assign `nullptr` to the pointer"
327 328 329 330
   ]
  },
  {
   "cell_type": "code",
331
   "execution_count": null,
332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348
   "metadata": {},
   "outputs": [],
   "source": [
    "{\n",
    "    auto ptr = std::make_unique<int>(5);\n",
    "    ptr = nullptr;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `shared_ptr`\n",
    "\n",
    "The philosophy of `shared_ptr` is different: this kind of smart pointers is fully copyable, and each time a copy is issued an internal counter is incremented (and decremented each time a copy is destroyed). When this counter reaches 0, the underlying object is properly destroyed.\n",
    "\n",
349
    "As for `unique_ptr`, there is a specific syntax to build them (properly named `make_shared`...); it was introduced earlier (C++ 11) and is not just cosmetic: the compiler is then able to store the counter more cleverly if you use `make_shared` rather than `new` (so make it so!)."
350 351 352 353
   ]
  },
  {
   "cell_type": "code",
354
   "execution_count": null,
355
   "metadata": {},
356
   "outputs": [],
357 358
   "source": [
    "#include <iostream>\n",
359
    "#include <memory>\n",
360 361
    "\n",
    "{\n",
GILLES Sebastien's avatar
GILLES Sebastien committed
362
    "    std::shared_ptr<double> ptr = std::make_shared<double>(5.);\n",
363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378
    "    \n",
    "    auto ptr2 = ptr;\n",
    "    \n",
    "    std::cout << \"Nptr = \" << ptr.use_count() << std::endl; \n",
    "    //< Notice the `.`: we access a method from std::shared_ptr, not from the type encapsulated\n",
    "    // by the pointer!\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "`shared_ptr` are clearly useful, but you should always wonder first if you really need them: for most uses a `unique_ptr` eventually seconded by raw pointers extracted by `get()` is enough.\n",
    "\n",
379
    "There is also a risk of not releasing properly the memory is there is a circular dependancy between two `shared_ptr`. A variation of this pointer named `weak_ptr` enables to circumvent this issue, but is a bit tedious to put into motion. I have written in [appendix](../7-Appendix/WeakPtr.ipynb) to describe how to do so.\n",
380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Efficient storage with vectors of smart pointers\n",
    "\n",
    "* `std::vector` are cool, but the copy when capacity is exceeded might be very costly for some objects. Moreover, it forces you to provide copy behaviour to your classes intended to be stored in `std::vector`, which is not a good idea if you do not want them to be copied.\n",
    "\n",
    "* An idea could be to use pointers: copy is cheap, and there is no need to copy the underlying objects when the capacity is exceeded. Another good point is that a same object might be stored in two different containers, and the modifications given in one  of this is immediately \"seen\" by the other (as the underlying object is the same).\n",
    "However, when this `std::vector` of pointers is destroyed the objects inside aren't properly deleted, provoking memory leaks.\n",
    "\n",
    "\n",
    "The way to combine advantages without retaining the flaws is to use a vector of smart pointers:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <array>\n",
    "\n",
    "class NotCopyable\n",
    "{\n",
    "    public:\n",
    "    \n",
    "        NotCopyable(double value);\n",
    "    \n",
    "        ~NotCopyable();\n",
    "\n",
    "        NotCopyable(const NotCopyable& ) = delete;    \n",
    "        NotCopyable& operator=(const NotCopyable& ) = delete;\n",
    "        NotCopyable(NotCopyable&& ) = delete;    \n",
    "        NotCopyable& operator=(NotCopyable&& ) = delete;\n",
    "    \n",
    "    private:\n",
    "    \n",
    "        std::array<double, 1000> data_;\n",
    "    \n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NotCopyable::NotCopyable(double value)\n",
    "{\n",
    "    data_.fill(value);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "\n",
    "NotCopyable::~NotCopyable()\n",
    "{\n",
    "    std::cout << \"Call to NotCopyable destructor!\" << std::endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <vector>\n",
    "#include <iostream>\n",
    "\n",
    "{\n",
    "    std::vector<std::unique_ptr<NotCopyable>> list;\n",
    "\n",
    "    for (double x = 0.; x < 8.; x += 1.1)\n",
    "    {\n",
    "        std::cout << \"Capacity = \" << list.capacity() << std::endl;\n",
GILLES Sebastien's avatar
GILLES Sebastien committed
467
    "        list.emplace_back(std::make_unique<NotCopyable>(x)); // emplace_back is like push_back for rvalues\n",
468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495
    "    }\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Doing so:\n",
    "\n",
    "- The `NotCopyable` are properly stored in a container.\n",
    "- No costly copy occurred: there were just few moves of `unique_ptr` when the capacity was exceeded.\n",
    "- The memory is properly freed when the `list` becomes out of scope.\n",
    "- And as we saw in previous section, the underlying data remains accessible through reference or raw pointer if needed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Using a trait as syntactic sugar\n",
    "\n",
    "I like to create aliases in my classes to provide more readable code:"
   ]
  },
  {
   "cell_type": "code",
496
   "execution_count": null,
497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <array>\n",
    "#include <vector>\n",
    "\n",
    "class NotCopyable2\n",
    "{\n",
    "    public:\n",
    "    \n",
    "        // Trait to alias the vector of smart pointers.\n",
    "        using vector_unique_ptr = std::vector<std::unique_ptr<NotCopyable2>>;\n",
    "    \n",
    "        NotCopyable2(double value);\n",
    "\n",
    "        NotCopyable2(const NotCopyable2& ) = delete;    \n",
    "        NotCopyable2& operator=(const NotCopyable2& ) = delete;\n",
    "        NotCopyable2(NotCopyable2&& ) = delete;    \n",
    "        NotCopyable2& operator=(NotCopyable2&& ) = delete;\n",
    "    \n",
    "    private:\n",
    "    \n",
    "        std::array<double, 1000> data_; // not copying it too much would be nice!\n",
    "    \n",
    "};"
   ]
  },
  {
   "cell_type": "code",
526
   "execution_count": null,
527 528 529 530 531 532 533 534 535 536 537
   "metadata": {},
   "outputs": [],
   "source": [
    "NotCopyable2::NotCopyable2(double value)\n",
    "{\n",
    "    data_.fill(value);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
538 539 540
   "execution_count": null,
   "metadata": {},
   "outputs": [],
541
   "source": [
542
    "#include <iostream>\n",
543 544 545 546 547 548
    "#include<vector>\n",
    "\n",
    "{\n",
    "    // Use the alias\n",
    "    NotCopyable2::vector_unique_ptr list;\n",
    "    \n",
549 550 551 552 553
    "    // or not: it amounts to the same!\n",
    "    std::vector<std::unique_ptr<NotCopyable2>> list2;\n",
    "    \n",
    "    // std::boolalpha is just a stream manipulator to write 'true' or 'false' for a boolean\n",
    "    std::cout << std::boolalpha << std::is_same<NotCopyable2::vector_unique_ptr, std::vector<std::unique_ptr<NotCopyable2>>>() << std::endl;\n",
554 555 556 557 558 559 560 561 562 563
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This simplifies the reading, especially if templates are also involved... "
   ]
  },
564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The cost of using smart pointers\n",
    "\n",
    "This [article](https://www.modernescpp.com/index.php/memory-and-performance-overhead-of-smart-pointer) provides an analysis of the cost involved both in performance and memory when using a smart pointer. To put in the nutshell, its conclusions are:\n",
    "\n",
    "- `std::unique_ptr` bears no overhead in memory (except in a very edge case you can safely ignore for now) and little overhead in performance, at least for the latter when compiler optimizations are enabled (we will talk about them in a later [notebook](../6-InRealEnvironment/3-Compilers.ipynb)).\n",
    "- `std::shared_ptr` incurs a memory overhead (to keep the reference count) and a performance overhead as well (which is partially mitigated if the memory was allocated through `std::make_shared`). The performance overhead is especially important when no optimizations are involved.\n",
    "\n",
    "This highlights once more what we said earlier:\n",
    "\n",
    "- Use smart pointers: RAII is simply too precious to manage properly your ressources!\n",
    "- Use `std::unique_ptr` wherever you can, and use `std::shared_ptr` when you really need several instances of the same ressource.\n"
   ]
  },
581 582 583 584 585 586
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# References\n",
    "\n",
587
    "[<a id=\"cit-Alexandrescu2001\" href=\"#call-Alexandrescu2001\">Alexandrescu2001</a>] Andrei Alexandrescu, ``_Modern C++ Design: Generic Programming and Design Patterns applied_'', 01 2001.\n",
588 589 590 591 592 593 594 595
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
596
    "© _CNRS 2016_ - _Inria 2018-2021_   \n",
597 598
    "_This notebook is an adaptation of a lecture prepared by David Chamont (CNRS) under the terms of the licence [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)](http://creativecommons.org/licenses/by-nc-sa/4.0/)_  \n",
    "_The present version has been written by Sébastien Gilles and Vincent Rouvreau (Inria)_"
599 600 601 602 603 604 605
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
606
   "name": "xcpp17"
607 608 609 610 611 612
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
613
   "version": "17"
614 615 616 617 618 619
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
620
   "cite_by": "key",
621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
644
   "toc_window_display": false
645 646 647
  }
 },
 "nbformat": 4,
648
 "nbformat_minor": 4
649
}