C++ - Extraire des collections de données depuis une collection initiale

Un billet blog de Bousk

Le 05/11/2020, par Bousk, Rédacteur/Modérateur

Il est commun de devoir extraire des vector depuis un vector initial.
Si l'on veut extraire des vector d'utilisateurs par exemple, tout en s'assurant que chaque utilisateur n'est présent que dans un vector à la fois.

La première approche d'un tel problème ressemblerait probablement à ceci :

Code c++ :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<..> originalData; 
std::vector<...> list1; 
std::vector<...> list2; 
std::vector<...> list3; 
std::vector<...> list4; 
for (..& data : originalData) 
{ 
  if (...) 
    list1.push_back(data); 
  else if (...) 
    list2.push_back(data); 
  else if (...) 
    list3.push_back(data); 
  else 
    list4.push_back(data); 
}

Le code est plutôt lisible, mais certains cas peuvent vite entraîner des conditions complexes à écrire.
Toutefois, ce code va effectuer une copie de chaque donnée depuis le vector original vers le vector auquel elle appartient.

Pour supprimer une copie, les vector pourraient être des vector de pointeurs. Mais le vector lui-même réalisera toujours une allocation voire plusieurs réallocations selon la quantité de données.

Pourquoi faire des copies alors que toutes les données sont disponibles dans le vector initial ?
Pourquoi faire la moindre allocation quand les données existent déjà ?
Chaque liste est un sous-ensemble du vector original. Celui-ci possède toutes les données, et c'est très bien ainsi.

Pour y parvenir, on pourrait imaginer un std::sort qui réorganise ce vector original, mais là aussi les conditions peuvent vite devenir complexes à écrire.
Pour y parvenir relativement simplement, nous allons utilisons un petit truc peu connu : std::partition, ou std::stable_partition pour garder un éventuel ordre des données.

partition va réordonner les éléments du vector de telle sorte que tous ceux qui valident la condition (le prédicat retourne true), seront placés en tête de la collection, puis retournera un itérateur sur le premier élément pour lequel le prédicat retourne false.
Exemple :

Code c++ :

1
2
3
4
5
6
7
8
9
  
    std::vector<int> tests{ 0,1,2,3,4 }; 
    auto it_part = std::stable_partition(tests.begin(), tests.end(), [](int v) { return v < 3; }); 
    std::cout << "Before part : "; 
    for (auto it = tests.begin(); it != it_part; ++it) 
        std::cout << *it << ","; 
    std::cout << std::endl << "After part : "; 
    for (auto it = it_part; it != tests.end(); ++it) 
        std::cout << *it << ",";

Qui donnera le résultat suivant :

Code :

1
2
Before part : 0,1,2, 
After part : 3,4,

D'abord, il nous faut une petite structure qui permet de réaliser une vue sur un vector.
Il n'existe malheureusement pas (encore) de vector_view dans le standard. Il y a bien std::span si vous êtes en C++20, mais celui-ci refuse une syntaxe std::span<int> sp(values.begin(), values.end());, ce qui est plutôt dérangeant...
Voici la très simple structure que nous allons utiliser :

Code c++ :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class T> 
class VectorView 
{ 
public: 
    VectorView() 
    { 
        // Default values to prevent iterating over random memory 
        m_begin = m_end; 
    } 
    VectorView(typename std::vector<T>::const_iterator first, typename std::vector<T>::const_iterator end) 
        : m_begin(first) 
        , m_end(end) 
    {} 
    auto begin() const { return m_begin; } 
    auto end() const { return m_end; } 
private: 
    typename std::vector<T>::const_iterator m_begin, m_end; 
};

Elle contient le strict minimum nécessaire, et vous êtes bien sûr libres d'y ajouter ce dont vous avez besoin.

Pour l'exercice, nous allons trier des nombres.
Le but est de finir avec cette syntaxe :

Code c++ :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  
    std::vector<int> values; 
    for (int i = 0; i < 100; ++i) 
        values.push_back(i); 
  
    VectorView<int> pairs; 
    VectorView<int> mul3; 
    VectorView<int> mul5; 
    VectorView<int> mul7; 
    VectorView<int> others; 
  
    CreateLists<int>(values.begin(), values.end() 
    , pairs, [](int v) { return v % 2 == 0; } 
    , mul3, [](int v) { return v % 3 == 0; } 
    , mul5, [](int v) { return v % 5 == 0; } 
    , mul7, [](int v) { return v % 7 == 0; } 
    , others 
    );

Ce que j'estime être une façon plutôt claire et élégante d'extraire les données qui nous intéressent.
Les listes sont créées dans l'ordre où elles apparaissent, une fois qu'un nombre a été ajouté comme multiple de 2, il ne pourra pas aussi se retrouver dans la liste de multiple de 3, 5 ou 7.
Les conditions sont plus simples puisqu'on est assuré que les conditions précédentes ont déjà été épuisées.

Pour y parvenir, il s'agira de méta-programmation relativement simple.
On commence par traiter le cas final, de créer une vue depuis toutes les données restantes :

Code c++ :

1
2
3
4
5
6
template<class T> 
typename std::vector<T>::iterator CreateLists(typename std::vector<T>::iterator first, typename std::vector<T>::iterator end, VectorView<T>& list) 
{ 
    list = VectorView<T>(first, end); 
    return end; 
}

Puis le cas où l'on a un prédicat pour extraire les données, avec l'utilisation de stable_partition :

Code c++ :

1
2
3
4
5
6
7
template<class T> 
typename std::vector<T>::iterator CreateLists(typename std::vector<T>::iterator first, typename std::vector<T>::iterator end, VectorView<T>& list, const std::function<bool(T)>& extracter) 
{ 
    auto firstNonExtracted = std::stable_partition(first, end, extracter); 
    list = VectorView<T>(first, firstNonExtracted); 
    return firstNonExtracted; 
}

Enfin, la fonction avec variadic templates qui permet de démarrer le tout :

Code c++ :

1
2
3
4
5
6
template<class T, class... Args> 
void CreateLists(typename std::vector<T>::iterator first, typename std::vector<T>::iterator end, VectorView<T>& list, const std::function<bool(T)>& extracter, Args&&... args) 
{ 
    auto newFirst = CreateLists<T>(first, end, list, extracter); 
    CreateLists<T>(newFirst, end, std::forward<Args>(args)...); 
}

Voici le code complet final, avec un test pour extraire des nombres de 0 à 100 :

Code c++ :

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
#include <algorithm> 
#include <functional> 
#include <iostream> 
#include <vector> 
  
template <class T> 
class VectorView 
{ 
public: 
    VectorView() 
    { 
        // Default values to prevent iterating over random memory 
        m_begin = m_end; 
    } 
    VectorView(typename std::vector<T>::const_iterator first, typename std::vector<T>::const_iterator end) 
        : m_begin(first) 
        , m_end(end) 
    {} 
    auto begin() const { return m_begin; } 
    auto end() const { return m_end; } 
private: 
    typename std::vector<T>::const_iterator m_begin, m_end; 
}; 
  
template<class T> 
typename std::vector<T>::iterator CreateLists(typename std::vector<T>::iterator first, typename std::vector<T>::iterator end, VectorView<T>& list) 
{ 
    list = VectorView<T>(first, end); 
    return end; 
} 
template<class T> 
typename std::vector<T>::iterator CreateLists(typename std::vector<T>::iterator first, typename std::vector<T>::iterator end, VectorView<T>& list, const std::function<bool(T)>& extracter) 
{ 
    auto firstNonExtracted = std::stable_partition(first, end, extracter); 
    list = VectorView<T>(first, firstNonExtracted); 
    return firstNonExtracted; 
} 
template<class T, class... Args> 
void CreateLists(typename std::vector<T>::iterator first, typename std::vector<T>::iterator end, VectorView<T>& list, const std::function<bool(T)>& extracter, Args&&... args) 
{ 
    auto newFirst = CreateLists<T>(first, end, list, extracter); 
    CreateLists<T>(newFirst, end, std::forward<Args>(args)...); 
} 
  
template<class T> 
void PrintValues(const char* name, VectorView<T> values) 
{ 
    std::cout << name << " : "; 
    for (T value : values) 
        std::cout << value << ", "; 
    std::cout << std::endl; 
} 
#define PRINT_VALUES_WITH_NAME(VALUES) PrintValues(#VALUES, VALUES) 
  
int main() 
{ 
    std::vector<int> values; 
    for (int i = 0; i < 100; ++i) 
        values.push_back(i); 
  
    VectorView<int> pairs; 
    VectorView<int> mul3; 
    VectorView<int> mul5; 
    VectorView<int> mul7; 
    VectorView<int> others; 
  
    CreateLists<int>(values.begin(), values.end() 
    , pairs, [](int v) { return v % 2 == 0; } 
    , mul3, [](int v) { return v % 3 == 0; } 
    , mul5, [](int v) { return v % 5 == 0; } 
    , mul7, [](int v) { return v % 7 == 0; } 
    , others 
    ); 
  
    PRINT_VALUES_WITH_NAME(pairs); 
    PRINT_VALUES_WITH_NAME(mul3); 
    PRINT_VALUES_WITH_NAME(mul5); 
    PRINT_VALUES_WITH_NAME(mul7); 
    PRINT_VALUES_WITH_NAME(others); 
    return 0; 
}

Ce qui donne ce résultat dans la console :

Code :

1
2
3
4
5
pairs : 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 
mul3 : 3, 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99, 
mul5 : 5, 25, 35, 55, 65, 85, 95, 
mul7 : 7, 49, 77, 91, 
others : 1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,

Conclusions
- Aucune allocation n'a été nécessaire pour trier et extraire les données dans chaque VectorView.
- Les données dans un VectorView sont contiguës, ce qui permet d'itérer de façon effective en limitant les cache-miss.
- L'élément le plus avancé utilisé est std::function, apparu en C++11. Ce code ne nécessite donc que cette version et peut probablement être utilisé dans votre codebase.
- Ce concept/code peut être élargi à toute collection dont les éléments peuvent être triés (array, dequeue, list, queue, stack).

Pour aller plus loin sur ce sujet.

Billet blog