/
algorithm.txt
660 lines (623 loc) · 48.5 KB
/
algorithm.txt
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
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
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
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
467
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
496
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
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
ALGORITHM
Concepts minimaux :
InputIt. : istream[buf]_iterator, *directory_iterator
Singlep. + Wr. + Read. : istream_range
incrementable : function_output_iterator
ReadableIt. : zip_iterator
OutputIt. : ostream[buf]_iterator, *insert_iterator
ForwardIt. : vector<bool>, deque<bool>, list<bool>
Min.Bidirect. : reverse_iterator
BidirectionalIt. : list, set, multiset, map, multimap, path::iterator
RandA. + Readable : irange
RandomAccessIt. : vector, deque, string
date iterators : Ne respectent rien, mais on peut définir un wrapper.
------------------------------------------------------------------------------
Le tableau suivant regroupe à la fois les algorithmes de std:: et de boost::
ARGUMENTS :
Symboles :
I : INPUT_ITVR
O : OUTPT_ITVR
B : BIDR_ITVR
F : FORWD_ITVR
R : RANDM_ITVR
P : UNARY PREDIC
[P] : [UNARY PREDIC]
W : WVAR_VAL (du range)
S : SIZE_T_VAL
{ } : Un bloc { }
Pour boost:: uniquement :
- si deux lettres : seconde lettre, non première
- types sont conservés, mais désignent transversal concept uniquement (input -> single pass)
- + : respecte WritableIt.
- changements arguments :
- 2 iterateurs -> 1 RANGE
- 3 iterateurs, mais deux ranges -> 2 RANGE
- 3 iterateurs (milieu étant milieu des deux autres) -> 1 RANGE + 1 itérateur (celui du milieu)
SG :
++ : Setter : ne renvoie rien pour std::, renvoie SP_RANG1 pour boost::
-+ : Setter, et renvoie un itérateur sur la fin du dernier range
- : Renvoie...
-- : Renvoie un ITVR sur... ( ou deuxième ITVR si rien trouvé )
=+, =, ==, =++ :
- Pour std::, Comme -+, -, -- et ++
- Pour boost::, Renvoie une occurence vers l'élément recherché sous forme d'un RANGE ou ITVR du même type que #1
L'occurence renvoie dépend d'un template <...> (template facultatif, par défaut <return_found>, sauf
pour unique, ou c'est <range_begin_found>), qui peut être rempli avec :
- return_found ITERATOR simple (l'occurence trouvée)
- return_begin_found RANGE begin(RANGE) -> occurence
- return_begin_next RANGE begin(RANGE) -> occurence + 1
- return_found_end RANGE occurence -> end(RANGE)
- return_next_end RANGE occurence + 1 -> end(RANGE)
- return_begin_end RANGE begin(RANGE) -> end(RANGE)
EXPLICATION :
$1 : chaque élément du premier range
$2 : chaque élément du second range
#1 : premier range
#2 : second range :
- si *_n, #2 est une suite de S WVAR_VAL, ou ITVR + S élements
- si #2 a que le début, sa fin == début + longueur de #1
#0 : signifie que ITVR1 à ITVR2 est #1, ITVR2 à ITVR3 est #2, et ITVR1 à ITVR3 est #0
[==] : comparaison est via un prédicat binaire, qui est par défaut == (ou <, +, -, *)
TRI :
: le tri / les comparaisons sont effectuées selon [<]
: doit d'abord être trié selon [<]
EXCLU :
s:: : disponible que dans std::
b:: : disponible que dans boost::
TIME :
- Time complexity :
- premier :
- : linéaire
- \ : logarithme
- / : linéaire * logarithme
- | : exponentiel
- deuxième :
- : pour tout RANGE
- + : meilleur cas
- - : pire cas
- b : pour un non-BIDIRECTIONALRANGE
- B : pour un BIDIRECTIONALRANGE
- R : pour un RANDOMACCESSRANGE
- r : pour un non-RANDOMACCESSRANGE
HEADER/REMARQUES :
- si boost::, toujours précédé par <boost/range/...>
- si rien, header est <algorithm> pour std:: et <boost/range/algorithm.hpp> pour boost::
- [.hpp] signifie .hpp seulement pour boost
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| NOM |#1a|#1b|#2a|#2b|#3 |#4 |SG EXPLICATION | TRI|EXCLU|TIME| HEADER / REMARQUES |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| for_each | I | I | P | | | |- fait P($1) -> renvoie P | | | | |
| for_each | I | I | I | I | P | |- fait P($1,$2) -> renvoie P | | b:: | | algorithm_ext.hpp |
| BOOST_FOREACH | W | | I | I |{ }| | { ... }, où $1 == $2 chaque itér.| | b:: | | <boost/foreach.hpp> |
| | | | | | | | | | | | Regarder doc. |
| BOOST_REVERSE_FOREACH | W | | I | I |{ }| | Même chose, mais parcourt #2 à | | b:: | | <boost/foreach.hpp> |
| | | | | | | | l'envers | | | | |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| find | I | I | W | | | |== premier $1 == W | | | | |
| find_if | I | I | P | | | |== premier P($1) == true | | | | |
| search | F | F | F | F |[P]| |== premier sous-range de #1 [==] #2 | | | | |
| search_n | F | F | S | W |[P]| |-- | | | | |
| find_end | F | F | F | F |[P]| |== dernier sous-range de #1 [==] #2 | | ||b-B| |
| find_first_of | FI| FI| F | F |[P]| |== premier $1 [==] l'un de #2 | | | | | |
| adjacent_find | F | F |[P]| | | |== premier $1 [==] next($1) | | | | |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| mismatch | FI| FI| FI|[P]| | |-- premier $1 ![==] $2 | | | | |
| | | | | | | | -> renvoie make_pair($1, $2) | | | | |
| | | | | | | | $2 est end si aucun mismatch | | | | |
| equal | FI| FI| FI|[P]| | |- true si #1 [==] #2 | | | | |
| lower_bound | F | F | W |[P]| | |-- premier $1 ![<] W | | | \R | |
| upper_bound | F | F | W |[P]| | |-- premier $1 ![<] W && $1 != W | | | \R | |
| equal_range | F | F | W |[P]| | |-- make_pair(low_bound, upper_bound)| | | \R | |
| binary_search | F | F | W |[P]| | |-- $1 == W | | | \R | |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| count | RI| RI| W | | | |- nombre de $1 == W | | | | |
| count_if | RI| RI| P | | | |- nombre de P($1) == true | | | | |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| is_sorted | I | I |[P]| | | |-- true si trié selon P | | | | algorithm_ext.hpp |
| sort | R+| R+|[P]| | | |++ tri #1 | | | / | |
| stable_sort | R+| R+|[P]| | | |++ tri #1 (garde ordre relatif) | | |/- +| |
| partial_sort | R+| R+| R |[P]| | |++ prend #0 et trie dans #1 et | | | / | |
| | | | | | | | place dans #2 non-trié | | | | |
| partial_sort_copy | I | I | R | R |[P]| |++ prend #1 et trie dans #2 | | s:: | | |
| | | | | | | | (jusqu'à plus de place) | | | | |
| nth_element | R+| R+| R |[P]| | |++ trie de sorte que ce qui précède | | | | |
| | | | | | | | R3 soit [<] lui, et ce qui lui | | | | |
| | | | | | | | succède soit ![<] lui | | | | |
| | | | | | | | (R3 est compris dans #1) | | | | |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| copy | I | I | O | | | |-+ $2 = $1 | | | | |
| copy_backward | B | B | O | | | |-+ $2 = $1 (O désigne fin de #2, | | | | |
| | | | | | | | et copie à l'envers) | | | | |
| copy_n | I | I | S | O | | |-+ $2 = $1, où end(#1) == begin(#1) | | b:: | | algorithm_ext.hpp |
| | | | | | | | + S | | | | |
| overwrite | I | I | I+| I+| | | $2 = $1 | | b:: | | algorithm_ext.hpp |
| | | | | | | | | | | | Ne renvoie rien. |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| swap | W | W | | | | |++ swap W1 et W2 | | s:: | | nothrow |
| iter_swap | F | F | | | | |++ swap $1 et $2 | | s:: | | nothrow |
| swap_ranges |FI+|FI+|FI+| | | |-+ swap #1 et #2 | | | | Renvoie #2 avec b:: |
| | | | | | | | | | | | nothrow |
| rotate_copy | F+| F+| F | O | | |-+ #2 = rotate(#1) | | | | |
| reverse | B+| B+| | | | |++ reverse(#1) | | | | |
| reverse_copy | B+| B+| O | | | |-+ #2 = reverse(#1) | | | | |
| random_shuffle | R | R |[P]| | | |++ shuffle(#1) | | | | |
| rotate | F+| F+| F | | | |++ rot(#0) de sorte que #0 commence | | | | |
| | | | | | | | par R2 | | | | |
| rotate_copy | F+| F+| F | O | | |-+ #2 = rotate(#1) | | | | |
| partition | F+| F+| P | | | |++=trie #1 de sorte que les P($1) | | | | |
| | | | | | | | renvoyant true précèdent les | | | | |
| | | | | | | | P($1) renvoyant false | | | | |
| stable_partition | F+| F+| P | | | |++=comme partition (garde ordre | | |/- +| |
| | | | | | | | relatif) | | | | |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| remove | F+| F+| W | | | |= trie #1 de sorte qu'un F3 (qui | | | | |
| | | | | | | | est renvoyé) précède tout $1 == W| | | | |
| remove_copy | F+| F+| O | W | | |-+ #2 = remove(#1) | | | | |
| remove_if | F+| F+| P | | | |= trie #1 de sorte qu'un F3 (qui | | | | |
| | | | | | | | est renvoyé) précède tout | | | | |
| | | | | | | | P($1) == true | | | | |
| remove_copy_if | F+| F+| O | P | | |-+ #2 = remove_if(#1) | | | | |
| replace | F+| F+| W | W | | |++ Si $1 == W1, $1 = W2 | | | | |
| replace_copy | F+| F+| O | W | W | |-+ #2 = replace($1) | | | | |
| replace_if | F+| F+| P | W | | |++ Si P($1), $1 = W | | | | |
| replace_copy_if | F+| F+| O | P | W | |-+ #2 = replace_if($1) | | | | |
| unique | F+| F+|[P]| | | |= trie #1 de sorte qu'un F3 (qui | | | | |
| | | | | | | | est renvoyé) précède tout | | | | |
| | | | | | | | $1 [==] next($1) | | | | |
| unique_copy |FI+|FI+| O |[P]| | |-+ #2 = unique(#1) | | | | |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| fill | F+| F+| W | | | |++ $1 = W | | | | |
| fill_n |OF+|SF+| W | | | | | | | | |
| generate | F+| F+| P | | | |++ $1 = P(void) | | | | |
| generate_n | F | S | P | | | | | | s:: | | |
| transform | I | I | O | P | | |-+ $2 = P($1) | | | | |
| | I | I | I | O | P | |-+ $3 = P($1, $2) | | | | |
| | | | | | | | (#1 : I1-I2 ; #2 : I3- ; #3 : O-)| | | | |
| iota | F | F | W | | | | #1 = { W, W+1, W+2, ... } | | b:: | | algorithm_ext.hpp |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| unitialized_copy | I | I | F | | | |-+ $2 = $1_TYPE($1) | | s:: | | memory ; nothrow |
| unitialized_fill | F | F | W | | | |++ $1 = W_TYPE(W) | | s:: | | nothrow |
| unitialized_fill_n | O | S | W | | | |++ | | s:: | | nothrow |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| merge | I | I | I | I | O |[P]|-+ #3 = #1 merge #2 | | | | |
| set_union | I | I | I | I | O |[P]|-+ #3 = #1 union #2 | | | | |
| set_intersection | I | I | I | I | O |[P]|-+ #3 = #1 intersection #2 | | | | |
| set_difference | I | I | I | I | O |[P]|-+ #3 = #1 difference #2 | | | | |
| set_symmetric_difference| I | I | I | I | O |[P]|-+ #3 = #1 symmetric_difference #2 | | | | |
| join | I | I | I | I | | |-- #1#2 | | b:: | | join.hpp |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| inplace_merge | B+| B+| B |[P]| | |++ #0 = tri(#1 + #2) (#1 et #2 | | | / | |
| | | | | | | | doivent être triés selon [<]) | | | | |
| includes | I | I | I | I |[P]| |- true si chaque $1 == l'un des $2 | | | | |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| min | W | W |[P]| | | |- min(W1, W2) | | s:: | | |
| max | W | W |[P]| | | |- min(W1, W2) | | s:: | | |
| minmax | W | W |[P]| | | |-- tuple(min(ARGS),max(ARGS)). | | b:: | | minmax.hpp |
| | | | | | | | Si W1 == W2, renvoie tuple(W1,W2)| | | | |
| [first_]min_element | F | F |[P]| | | |= min(#1) (première occurence) | | | | [minmax_element.hpp] |
| last_min_element | F | F |[P]| | | |= min(#1) (dernière occurence) | | b:: | | minmax_element.hpp |
| [first_]max_element | F | F |[P]| | | |= max(#1) (première occurence) | | | | [minmax_element.hpp] |
| last_max_element | F | F |[P]| | | |= max(#1) (dernière occurence) | | b:: | | minmax_element.hpp |
| minmax_element | F | F |[P]| | | |= pair(min_element,max_element) | | b:: | | minmax_element.hpp |
|first_min_last_max_element|F | F |[P]| | | |= pair(min_element,last_max_element)| | b:: | | minmax_element.hpp |
|last_min_first_max_element| F| F |[P]| | | |= pair(last_min_element,max_element)| | b:: | | minmax_element.hpp |
|last_min_last_max_element| F | F |[P]| | | |= pair(last_min_elm*,last_max_elm*)| | b:: | | minmax_element.hpp |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| lexicographical_compare | FI| FI| F | F |[P]| |- renvoie true si #1 [<] #2 | | | | |
| | | | | | | | (compare élément après élément | | | | |
| | | | | | | | jusqu'à première différence) | | | | |
| next_permutation |FB+|FB+|[P]| | | |- #1 = next_perm(#1) -> renvoie | | | | |
| | | | | | | | false si dernier élément | | | | |
| prev_permutation |FB+|FB+|[P]| | | |- #1 = prev_perm(#1) -> ... | | | | |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| make_heap | R+| R+|[P]| | | |++ make_heap(#1) | | | | |
| sort_heap | R+| R+|[P]| | | |++ destroy_heap_then_sort(#1) | | | / | |
| | | | | | | | (#1 est un heap) | | | | |
| pop_heap | R+| R+|[P]| | | |++ R2 = min(#1) (#1 est un heap) | | | \ | |
| push_heap | R+| R+|[P]| | | |++ Rajoute R2 au heap R1-prev(R2) | | | \ | |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| accumulate | I | I | W |[P]| | |- renvoie $1 [+] $2 [+] ... [+] W | | | | numeric[.hpp] |
| adjacent_difference | I | I | O |[P]| | |-+ $2 = $1 [-] next($1) | | | | numeric[.hpp] |
| partial_sum | I | I | O |[P]| | |-+ $2 = $1[+]tous_les_precédents($1)| | | | numeric[.hpp] |
| inner_product | I | I | I | W |[P]|[P]|- renvoie $1 [*] $2 [+] next($1) | | | | numeric[.hpp] |
| | | | | | | | [*] next($2) [+] ... [+] W | | | | |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
- C : CONTAINER disposant de l'action souhaitée. Le RANGE de l'argument doit provenir du CONTAINER.
- <> : ITERATOR_RANGE
- -> : CONTAINER::ITERATOR
- Renvoient tous CONTAINERS
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
| erase | C | | <>| | | | Si $1 == $2, #1.erase($1) | | b:: | | algorithm_ext.hpp |
| remove_erase | C | | W | | | | Si $1 == W, #1.erase($1) | | b:: | | algorithm_ext.hpp |
| remove_erase_if | C | | P | | | | Si P($1), #1.erase($1) | | b:: | | algorithm_ext.hpp |
| insert | C | ->| I | I | | | #1.insert(-> - 1, $2) | | b:: | | algorithm_ext.hpp |
| push_back | C | | I | I | | | #1.insert(#1.begin(), $2) | | b:: | | algorithm_ext.hpp |
| push_front | C | | I | I | | | #1.insert(#1.end(), $2) | | b:: | | algorithm_ext.hpp |
+-------------------------+---+---+---+---+---+---+------------------------------------+----+-----+----+----------------------+
ALGORITHM ==> #Ces fonctions effectuent une action dans ce que
#j'appellerai un range, soit chaque élément entre un
#ITVR1 (inclus) et un ITVR2 (exclus)
#Les itérateurs peuvent être des pointeurs d'arrays
#dynamiques ou des itérateurs de strings (les strings
#et les arrays dynamiques sont des sortes de containers)
PREDIC ==> #Tous les PREDIC qui suivent :
# - sont de type bool si rien n'est précisé
# - prennent 0, 1 ou 2 WVAR_VAL (en fonction du
# contexte) arguments, renvoyant aux éléments des
# ranges concernés
# - ne peuvent pas prendre des arguments référence
# non-const
NOTATION ==> #Significations :
ITVR #ITRTR_VAR
for_each(INPUT_ITVR1, #Exécute PREDIC(WVAR_VAL), soit WVAR_VAL chaque
INPUT_ITVR2, PREDIC) #élément du range, pour chaque élément du range.
#Renvoie PREDIC.
find(INPUT_ITVR1, #Renvoie un itérateur vers la première occurence de
INPUT_ITVR2, WVAR_VAL) #WVAR_VAL dans le range, ou INPUT_ITVR2 si elle n'a pas
#été trouvée.
find_if(INPUT_ITVR1, #Renvoie un itérateur vers la première occurence dans le
INPT_ITVR2, PREDIC) #range faisant que PREDIC renvoie true, ou INPUT_ITVR2
#si aucune occurence n'a été trouvée.
search(FORWD_ITVR1, #Recherche dans le premier range la première suite
FORWD_ITVR2, FRWD_ITVR3,#d'éléments dont chaque élément renvoie true avec leur
FORWD_ITVR4[, PREDIC]) #semblable dans le deuxième range via PREDIC (par
#défaut equal_to<WVAR>())
#Par défaut recherche donc la première occurence
#entière du deuxième range dans le premier.
#Renvoie un itérateur vers le premier élément dans le
#premier range de l'occurence trouvée, ou FORWD_ITVR2 si
#rien n'a été trouvé.
search_n(FORWD_ITVR1, #Comme search(), sauf que les valeurs du deuxième range
FORWD_ITVR2, SIZE_T_VAL,#à rechercher ne sont pas les WVAR_VAL comprises entre
WVAR_VAL[, PREDIC]) #deux itérateurs, mais une suite de SIZE_T_VAL WVAR_VAL.
find_end(FORWD_ITVR1, #Comme search(), mais recherche non pas la première mais
FORWD_ITVR2, FRWD_ITVR3,#la dernière occurence (et renvoie de même un itérateur
FORWD_ITVR4[, PREDIC]) #vers le premier élément de cette occurence)
find_first_of #Recherche dans le premier range le premier élément qui
(FORWD_ITVR1,FRWD_ITVR2,#renvoie true en étant comparé à n'importe lequel des
FRWD_ITVR3, FORWD_ITVR4 #éléments du deuxième range via PREDIC (par défaut
[, PREDIC]) #equal_to<WVAR>())
#Par défaut recherche donc la première occurence dans le
#premier range de l'un des éléments du second range.
#Renvoie un itérateur vers l'occurence trouvée, ou
#FORWD_ITVR2 si rien n'a été trouvé.
adjacent_find #Renvoie un itérateur vers le premier élément du range
(FORWD_ITVR1, FRWD_ITVR2#qui renvoie true lorsque comparé avec l'élément qui le
[, PREDIC]) #suit via PREDIC (par défaut equal_to<WVAR>())), ou
#FRWD_ITVR2 si rien n'a été trouvé.
mismatch(FORWD_ITVR1, #Compare le premier élément de chaque range via PREDIC,
FORWD_ITVR2, FORWD_ITVR3#(par défaut equal_to<WVAR>()) puis le deuxième, etc.
[, PREDIC]) #jusqu'à ce que :
# 1) PREDIC retourne false, auquel cas une pair avec
# PAIR.first et PAIR.second étant positionnés sur les
# éléments dans le premier et le second range ayant
# renvoyer false.
# 2) la fin de l'un des deux ranges soit atteinte.
# Auquel cas une pair d'itérateurs est aussi renvoyée
# avec PAIR.first valant CONTAINER.end() où CONTAINER
# est celui du premier range.
#Le deuxième range commence à FORWD_ITVR3 et se termine
#à la fin du container.
#Par défaut, recherche donc les premiers éléments
#"mismatchant" entre les deux ranges.
equal(FORWD_ITVR1, #Compare le premier élément de chaque range via PREDIC
FORWD_ITVR2, FORWD_ITVR3#(par défaut equal_to<WVAR>()), puis le deuxième, etc.,
[, PREDIC]) #et renvoie true si aucun PREDIC ne renvoie false et
#que les ranges ont la même longueur.
#Par défaut, teste donc l'égalité de deux containers.
#Le deuxième range commence à FORWD_ITVR3 et se termine
#à la fin du container.
lower_bound(FORWD_ITVR1,#Renvoie un itérateur vers le premier élément du range
FORWD_ITVR2, WVAR_VAL #qui, comparé avec WVAR_VAL via PREDIC (par défaut
[, PREDIC]) #less <WVAR>()) renvoie false, ou CONTAINER.end() si
#aucun élément ne renvoie false.
#Par défaut, renvoie donc le premier élément >= WVAR_VAL
#Le container doit déjà être trié (car il s'agit d'une
#binary search) selon PREDIC.
upper_bound(FORWD_ITVR1,#Même chose, mais l'itérateur ne peut en outre pas
FORWD_ITVR2, WVAR_VAL #pointé une valeur == WVAR_VAL.
[, PREDIC]) #Par défaut, renvoie donc le premier élément > WVAR_VAL
equal_range(FORWD_ITVR1,#Renvoie une PAIR avec PAIR.first et PAIR.second avec
FORWD_ITVR2, WVAR_VAL #les résultats respectifs d'un lower_bound() et
[, PREDIC]) #d'un upper_bound() avec les mêmes arguments.
#Renvoie donc une paire de deux itérateurs identiques si
#WVAR_VAL n'est == à aucun des éléments du range.
#Par défaut, renvoie donc, via une PAIR, un range des
#éléments == WVAR_VAL.
#Le container doit déjà être trié (car il s'agit d'une
#binary search) selon PREDIC
binary_search #Recherche WVAR_VAL dans le range par une recherche
(FRWD_ITVR1, FRWD_ITVR2,#logarithmique via PREDIC (par défaut less<WVAR>()) et
WVAR_VAL[, PREDIC]) #renvoie true s'il a été trouvé.
#Le container doit déjà être trié (car il s'agit d'une
#binary search) selon PREDIC
count(FORWD_ITVR1, #Renvoie le nombre d'occurences de WVAR_VAL dans le
FORWD_ITVR2, WVAR_VAL) #range.
count_if(FORWD_ITVR1, #Renvoie le nombre d'éléments dans le range qui
FORWD_ITVR2, PREDIC) #renvoient true via PREDIC.
sort(RNDOM_ITVR1, #
RNDOM_ITVR2[, PREDIC]) #Trie le range selon PREDIC (par défaut less <WVAR>()).
stable_sort(RNDOM_ITVR1,#Comme sort(), mais deux éléments égaux sont assurés de
RNDOM_ITVR2[, PREDIC]) #conserver leur position relative l'un par rapport à
#l'autre.
partial_sort(RNDM_ITVR1,#Selon PREDIC (par défaut less <WVAR>()), prend les
RNDOM_ITVR2, RNDOM_ITVR3#(RNDOM_ITVR2 - RNDOM_ITVR1) éléments les plus petits du
[, PREDIC]) #range allant de RNDOM_ITVR1 à RNDOM_ITVR3, trie ces
#éléments, et les place dans le range allant de
#RNDOM_ITVR1 à RNDOM_ITVR2, et place les autres éléments
#(les plus grands) entre RNDOM_ITVR2 et RNDOM_ITVR3,
#sans qu'ils soient triés.
partial_sort_copy #Selon PREDIC (par défaut less <WVAR>()), prend les, au
(INPT_ITVR1, INPT_ITVR2,#plus, (RNDOM_ITVR4 - RNDOM_ITVR3) éléments les plus
RNDOM_ITVR3, RNDOM_ITVR4#petits du premier range, trie ces éléments, et les
[, PREDIC]) #copie dans le deuxième range.
nth_element(RNDOM_ITVR1,#Selon PREDIC (par défaut less <WVAR>()), pour un range
RNDOM_ITVR2, RNDOM_ITVR3#allant de RNDOM_ITVR1 à RNDOM_ITVR3, modifie ce range
[, PREDIC]) #de sorte que :
# - l'élément à la position RNDOM_ITVR2 soit le même
# que si le range entier était trié
# - les éléments précédant RNDOM_ITVR2 lui sont
# inférieurs, mais ne sont pas forcément triés entre
# eux
# - les éléments suivant RNDOM_ITVR2 lui sont
# supérieurs, mais ne sont pas forcément triés entre
# eux
copy(INPUT_ITVR1, #Copie les éléments du premier range dans le deuxième
INPUT_ITVR2, OUTPT_ITVR)#range, qui commence à OUTPUT_ITVR ; et renvoie un
#OUTPUT_ITVR2 pointant juste après le dernier élément
#copié. OUTPT_ITVR ne doit pas être dans le premier
#range.
copy_backward #Comme copy(), mais les éléments sont copiés en partant
(INPT_ITVR1, INPT_ITVR2,#du dernier élément, et OUTPUT_ITVR -1 fait donc
OUTPT_ITVR) #référence au premier élément du second range. Un
#OUTPUT_ITVR2 pointant vers le dernier élément copié
#(qui est le début du deuxième range donc) est renvoyé.
#A le même effet quasiment que copy() donc sauf que si
#le deuxième range overlappe le premier alors :
# - si le premier élément du deuxième range est contenu
# dans le premier range, utiliser copy_backward()
# - si le dernier élément du deuxième range est contenu
# dans le premier range, utiliser copy()
#Par deuxième range, je fais référence à l'ensemble
#d'éléments finalement copiés.
swap(VAL1, VAL2) #Le contenu et la taille de VAL1 et VAL2 sont échangées.
#Elles peuvent être des variables normales ou des objets
#(dont containers). Cependant :
# - ils doivent être de même type
# - ce type doit avoir un copy constructor et un copy
# operator
# - c'est plus rapide d'utiliser les méthodes de swap
# et d'assignations des containers, optimisées.
iter_swap(FORWD_ITVR1, #
FORWD_ITVR2) #Equivaut à swap(*FORWD_ITVR1, *FORWD_ITVR2)
swap_ranges #Swappe les deux ranges. Le deuxième range commence à
(FRWD_ITVR1, FRWD_ITVR2,#FORWD_ITVR3, et sa taille est devinée (même taille que
FORWD_ITVR3) #le premier range). Renvoie un FORWD_ITVR4 sur le
#dernier élément du second range.
reverse(BIDR_ITVR1, #
BIDR_ITVR2) #Inverse l'ordre des éléments du range.
random_shuffle #Mélange le range, selon PREDIC (par défaut rand()).
(RNDM_ITVR1, RANDM_ITVR2#PREDIC prend un argument SIZE_T_VAL et retourne une
[, PREDIC]) #SIZ_T_VAL comprise entre la valeur de cet argument et 0
rotate(FORWD_ITVR1, #Effectue une rotation des éléments du range allant de
FORWD_ITVR2, FRWD_ITVR3)#FORWD_ITVR1 à FORWD_ITVR3, de sorte que FORWD_ITVR2
#soit le nouveau premier élément.
partition(BIDR_ITVR1, #Redispose le range de sorte que tous les éléments qui
BIDR_ITVR2, PREDIC) #retournent true via PREDIC soient avant ceux qui
#renvoient false. PREDIC prend un seul argument de type
#WVAR_VAL.
#Renvoie un BIDR_ITVR pointant vers le premier élément
#de la "partie false".
stable_partition #Comme partition(), mais la position relative des
(BIDR_ITVR1, BIDR_ITVR2,#éléments de la partie true entre eux, et celle de ceux
PREDIC) #de la partie false, est assurée d'être la même qu'avant
#stable_partition()
remove(FORWD_ITVR1, #Supprime tous les éléments du range dont la valeur est
FORWD_ITVR2, WVAR_VAL) #WVAR_VAL. Les éléments ne sont pas vraiment supprimés :
#un FORWD_ITVR est en fait renvoyé désignant une
#nouvelle fin pour le range, le raccourcissant (le
#nouveau range n'ayant aucune mention des éléments
#"supprimés"). Si le range est un container, sa taille
#n'est pas affectée : le redimensionner donc en fonction
#de l'itérateur renvoyé.
remove_if(FORWD_ITVR1, #Supprime tous les éléments du range qui via PREDIC
FORWD_ITVR2, PREDIC) #renvoient true. PREDIC ne prend qu'un argument de type
#WVAR_VAL. Même chose pour le fait que la suppression
#est opérée de manière inhabituelle.
replace(FORWD_ITVR1, #
FORWD_ITVR2, WVAR_VAL1, #Remplace tous éléments du range dont la valeur est
WVAR_VAL2) #WVAR_VAL1 par WVAR_VAL2.
replace_if(FORWD_ITVR1, #Remplace tous éléments du range qui via PREDIC
FORWD_ITVR2, PREDIC, #renvoient true, par WVAR_VAL.
WVAR_VAL) #PREDIC prend un seul argument de type WVAR_VAL.
unique(FORWD_ITVR1, #Supprime tous les éléments du range qui comparé avec
FORWD_ITVR2[, PREDIC]) #l'élément qui les précède via PREDIC renvoient true.
#PREDIC prend deux arguments de type WVAR_VAL. Les
#arguments sont supprimées de la même manière
#inhabituelle que remove(), et donc un FORWD_ITVR est
#renvoyé à cet effet.
#PREDIC est par défaut equal_to<WVAR>() : par défaut,
#supprime donc les doublons, mais il faut trier avant.
fill(FORWD_ITVR1, #
FORWD_ITVR2, WVAR_VAL) #Remplit le range avec une suite de WVAR_VAL.
fill_n(OUTPUT_ITVR, #Equivaut à fill(OUTPUT_ITVR, OUTPUT_ITVR + SIZE_T_VAL,
SIZE_T_VAL, WVAR_VAL) #WVAR_VAL)
generate(FORWD_ITVR1, #Remplit le range avec une suite de WVAR_VAL telle que
FORWD_ITVR2, PREDIC) #générées par une succession d'appel à PREDIC. PREDIC ne
#prend pas d'argument (hors bind()) et renvoie une
#WVAR_VAL.
generate_n(FORWD_ITVR1, #Equivaut à generate(FORWD_ITVR, FORWD_ITVR +
SIZE_T_VAL, PREDIC) #SIZE_T_VAL, PREDIC)
transform(INPUT_ITVR1, #Effectue PREDIC pour chaque élément du range, et
INPUT_ITVR2, OUTPT_ITVR,#copie chaque résultat dans le second range, qui
PREDIC) #commence à OUTPUT_ITVR. Renvoie un OUTPUT_ITVR2 vers
#l'élément qui suit le dernier résultat copié.
#PREDIC prend un argument WVAR_VAL, et renvoie un
#WVAR_VAL.
transform(INPUT_ITVR1, #Même chose, sauf que PREDIC prend cette fois deux
INPUT_ITVR2, INPT_ITVR3,#argument WVAR_VAL, à savoir un élément de chacun des
OUTPT_ITVR, PREDIC) #deux premiers ranges. Copie le résultat dans le
#troisième.
#Le deuxième range commence à INPT_ITVR3 (il faut
#s'assurer que sa taille est >= celle du premier range),
#et le troisième à OUTPT_ITVR.
reverse_copy(BIDR_ITVR1,#
BIDR_ITVR2, OUTPUT_ITVR)
rotate_copy(FORWD_ITVR1,#
FORWD_ITVR2, FRWD_ITVR3,
OUTPUT_ITVR)
unique_copy(FORWD_ITVR1,#
FORWD_ITVR2, OUTPUT_ITVR
[, PREDIC])
remove_copy(FORWD_ITVR1,#
FORWD_ITVR2, OUTPT_ITVR,
WVAR_VAL)
remove_copy_if #
(FRWD_ITVR1, FRWD_ITVR2,
OUTPUT_ITVR, PREDIC)
replace_copy(FRWD_ITVR1,#Toutes ces fonctions sont identiques à leur version
FORWD_ITVR2, OUTPT_ITVR,#sans le suffixe "_copy" sauf que plutôt que de modifier
WVAR_VAL1, WVAR_VAL2) #directement le premier range, elles écrivent le
replace_copy_if #résultat dans un second range commençant à OUTPUT_ITVR,
(FRWD_ITVR1, FRWD_ITVR2,#et renvoie un OUTPUT_ITVR2 désignant l'élément suivant
OUTPUT_ITVR, PREDIC, #le dernier élément copié (plutôt que de ne rien envoyer
WVAR_VAL) #ou de renvoyer un autre itérateur pour certaines)
merge(INPUT_ITVR1, #Selon PREDIC (par défaut less <WVAR>()), effectue le
INPUT_ITVR2, INPT_ITVR3,#merge des deux ranges (les doublons ne sont pas
INPUT_ITVR4, OUTPUT_ITVR#supprimés), merge qui est automatiquement trié,
[, PREDIC]) #copie le résultat à partir de OUTPUT_ITVR, et renvoie
#un OUTPUT_ITVR2 positionné après le dernier élément de
#la copie.
#Les deux ranges doivent déjà être triés selon PREDIC.
#Plus rapide qu'un sort().
set_union(INPUT_ITVR1, #
INPUT_ITVR2, INPT_ITVR3,#Comme merge(), mais il s'agit d'une union (éléments
INPUT_ITVR4, OUTPUT_ITVR#présent dans l'un des deux ranges, mais les doublons
[, PREDIC]) #sont enlevés), et non d'un merge()
set_intersection #
(INPT_ITVR1, INPT_ITVR2,#Comme set_union(), sauf qu'il s'agit d'une intersection
INPT_ITVR3, INPUT_ITVR4,#(éléments présents dans les deux ranges en même temps,
OUTPUT_ITVR[, PREDIC]) #leurs doublons étant enlevés)
set_difference #
(INPT_ITVR1, INPT_ITVR2,#Comme set_union(), sauf qu'il s'agit d'une différence
INPT_ITVR3, INPUT_ITVR4,#(éléments présents dans le premier range, mais pas
OUTPUT_ITVR[, PREDIC]) #dans le deuxième)
set_symmetric_difference#
(INPT_ITVR1, INPT_ITVR2,#Comme set_union(), sauf qu'il s'agit d'une différence
INPT_ITVR3, INPUT_ITVR4,#symétrique (éléments présents dans l'un des deux
OUTPUT_ITVR[, PREDIC]) #ranges, mais pas les deux en même temps)
inplace_merge #Selon PREDIC (par défaut less <WVAR>()), merge les
(BIDR_ITVR1, BIDR_ITVR2,#ranges allant de BIDR_ITVR1 à BIDR_ITVR2 et allant de
BIDR_ITVR3[, PREDIC]) #BIDR_ITVR2 à BIDR_ITVR3, merge qui est automatiquement
#trié.
#Les deux ranges doivent déjà être triés selon PREDIC.
#En gros, revient à trier le range allant de BIDR_ITVR1
#à BIDR_ITVR3.
#Plus rapide qu'un sort().
includes(INPUT_ITVR1, #Selon PREDIC (par défaut less <WVAR>()), renvoie true
INPUT_ITVR2, INPT_ITVR3,#si chaque élément du premier range est == l'un des
INPUT_ITVR4, [, PREDIC])#éléments du second range.
#Les deux ranges doivent déjà être triés selon PREDIC.
min(VAL1, VAL2 #Compare VAL1 et VAL2 via PREDIC (par défaut less<TYPE>
[, PREDIC]) #() où TYPE est le type des VAL), et renvoie VAL1 si
#PREDIC renvoie true, VAL2 sinon.
max(VAL1, VAL2 #
[, PREDIC]) #Même chose, sauf qu'utilise par défaut greater<TYPE>()
min_element(FORWD_ITVR1,#Effectue un min(VAL1, VAL2[, PREDIC]) sur les deux
FORWD_ITVR2[, PREDIC]) #premiers éléments du range, puis entre le résultat et
#le prochain élément, etc., et renvoie le dernier
#résultat. Renvoie un itérateur sur l'élément en
#question.
#Par défaut, renvoie donc un itérateur sur la valeur
#minimale du range.
max_element(FORWD_ITVR1,#Même chose, mais avec max(). Par défaut, renvoie donc
FORWD_ITVR2[, PREDIC]) #un itérateur sur la valeur maximale du range.
lexicographical_compare #Test si le premier élément de chaque range sont égaux,
(FORWD_ITVR1,FRWD_ITVR2,#puis le deuxième, etc. jusqu'à ce que deux éléments
FORWD_ITVR3, FORWD_ITVR4#non-égaux soient trouvés, et renvoie alors le résultat
[, PREDIC]) #de leur comparaison via PREDIC (par défaut
#less<WVAR>())
#Par défaut, utilisé sur des strings par exemple pour
#comparer alphabétiquement.
next_permutation #Une permutation est une des N! possibilités (soit N le
(FORWD_ITVR1, FRWD_ITVR2#nombre d'éléments du container) de mélanger ses
[, PREDIC]) #éléments. En utilisant lexicographical_compare avec
#PREDIC (par défaut less <WVAR>()), fait que le
#contenu du container devient permutation supérieure la
#plus proche, et renvoie true.
#S'il s'agissait déjà de la permutation la plus grande,
#le contenu du container devient la permutation la plus
#faible, et false et renvoyé.
prev_permutation #
(FORWD_ITVR1, FRWD_ITVR2
[, PREDIC]) #Comme next_permutation(), mais dans l'autre sens.
make_heap(RNDOM_ITVR1, #Réarrange le range de sorte qu'il forme un heap. Il
RNDOM_ITVR2[, PREDIC]) #s'agit d'un tri très spécial dépendant des
#implémentations, servant à mimer la structure nodale
#d'un heap dans un container, selon PREDIC (par défaut
#less <WVAR>()).
#Il ne faut pas chercher à comprendre la logique de ce
#"tri spécial".
#Les heaps permettent d'insérer et de supprimer des
#éléments en fonction de leur valeur relative, selon un
#temps logarithmique.
sort_heap(RNDOM_ITVR1, #Selon PREDIC (par défaut less <WVAR>()), fait que le
RNDOM_ITVR2[, PREDIC]) #range, qui doit être un heap, et donc disposé selon le
#"tri spécial" des heaps, cesse d'être un heap et soit
#simplement trié. Le range peut ne pas être un heap,
#mais préférer alors sort()
pop_heap(RNDOM_ITVR1, #Selon PREDIC (par défaut less <WVAR>()), fait que
RNDOM_ITVR2[, PREDIC]) #l'élément du range (qui doit être un heap) qui est le
#plus grand (et qui est toujours au début d'un heap),
#soit retiré du heap (le heap se terminant désormais à
#RNDOM_ITVR2 - 1). L'élément retiré est en fait placé
#juste en dehors du nouveau heap, à RNDOM_ITVR2.
#Il faut donc manuellement rétrécir le range de 1
#élément ensuite.
#Le heap est à nouveau trié selon son "tri spécial".
push_heap(RNDOM_ITVR1, #Selon PREDIC (par défaut less <WVAR>()), soit les
RNDOM_ITVR2[, PREDIC]) #éléments allant de RNDOM_ITVR1 à RNDOM_ITVR2 - 1 un
#heap, et soit l'élément à RNDOM_ITVR2 l'élément à
#insérer, insère cet élément dans le heap (se terminant
#désormais à RNDOM_ITVR2).
#Le heap est à nouveau trié selon son "tri spécial".
#Si l'on veut insérer un élément dans un heap, il faut
#donc placer un élément juste après lui, puis faire un
#push_heap()
#Il faut donc manuellement agrandir le range de 1
#élément ensuite.
accumulate(INPUT_ITVR1, #Utilise PREDIC (par défaut plus<WVAR>()) sur le premier
INPUT_ITVR2, WVAR_VAL1 #et le deuxième élément du range, puis sur le résultat
[, PREDIC]) #et le troisième, puis sur le résultat et le quatrième,
#etc., puis sur le résultat final et WVAR_VAL1, et
#renvoie ce résultat sous forme de WVAR_VAL.
adjacent_difference #Ecrit dans chaque élément du deuxième range le résultat
(INPT_ITVR1, INPT_ITVR2,#de l'utilisation de PREDIC (par défaut minus<WVAR>())
OUTPUT_ITVR1[, PREDIC]) #entre l'élément correspondant dans le premier range,
#et l'élément qui le suit.
#Renvoie un OUTPUT_ITVR2 pointant l'élément suivant le
#dernier élément du second range.
partial_sum(INPT_ITVR1, #Ecrit dans chaque élément du deuxième range le résultat
INPT_ITVR2, OUTPUT_ITVR1#de l'utilisation de PREDIC (par défaut plus<WVAR>())
[, PREDIC]) #sur l'élément correspondant dans le premier range, et
#l'élément qui le précède, puis sur le résultat et
#l'élément encore avant, etc. jusqu'au début du range.
#Renvoie un OUTPUT_ITVR2 pointant l'élément suivant le
#dernier élément du second range.
inner_product #Utilise PREDIC2 (par défaut multiplies<WVAR>()) entre
(INPT_ITVR1, INPT_ITVR2,#le premier élément de chaque range, puis utilise
INPUT_ITVR3, WVAR_VAL1 #PREDIC1 (par défaut plus<int>()) entre ce résultat et
[, PREDIC1, PREDIC2] #le résultat de l'utilisation de PREDIC2 entre le
#deuxième élément de chaque range, etc. puis utilise
#PREDIC1 entre le résultat final et WVAR_VAL1, et
#renvoie ce résultat sous forme de WVAR_VAL.
unitialized_copy #Comme copy(), mais effectue $1 = $2_TYPE($2), et non
(INPT_ITVR1, INPT_ITVR2,#$1 = $2, ce dernier échouant si $1 n'est pas initialisé
FW_ITVR) #(par exemple buffer retourné par malloc)
unitialized_fill(FW_IV1,#
FORWD_ITVR2, WVAR_VAL)
unitialized_fill_n #
OUTPT_ITVR, SIZE_T_VAL,
WVAR_VAL) #Même chose pour fill() et fill_n()