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 :
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 :
std::vector
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 :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
Voici la très simple structure que nous allons utiliser :
template
class VectorView
{
public:
VectorView()
{
// Default values to prevent iterating over random memory
m_begin = m_end;
}
VectorView(typename std::vector
: m_begin(first)
, m_end(end)
{}
auto begin() const { return m_begin; }
auto end() const { return m_end; }
private:
typename std::vector
};
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 :
std::vector
for (int i = 0; i < 100; ++i)
values.push_back(i);
VectorView
VectorView
VectorView
VectorView
VectorView
CreateLists
, 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 :
template
typename std::vector
{
list = VectorView
return end;
}
Puis le cas où l'on a un prédicat pour extraire les données, avec l'utilisation de stable_partition :
template
typename std::vector
{
auto firstNonExtracted = std::stable_partition(first, end, extracter);
list = VectorView
return firstNonExtracted;
}
Enfin, la fonction avec variadic templates qui permet de démarrer le tout :
template
void CreateLists(typename std::vector
{
auto newFirst = CreateLists
CreateLists
}
Voici le code complet final, avec un test pour extraire des nombres de 0 à 100 :
#include
#include
#include
#include
template
class VectorView
{
public:
VectorView()
{
// Default values to prevent iterating over random memory
m_begin = m_end;
}
VectorView(typename std::vector
: m_begin(first)
, m_end(end)
{}
auto begin() const { return m_begin; }
auto end() const { return m_end; }
private:
typename std::vector
};
template
typename std::vector
{
list = VectorView
return end;
}
template
typename std::vector
{
auto firstNonExtracted = std::stable_partition(first, end, extracter);
list = VectorView
return firstNonExtracted;
}
template
void CreateLists(typename std::vector
{
auto newFirst = CreateLists
CreateLists
}
template
void PrintValues(const char* name, VectorView
{
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
for (int i = 0; i < 100; ++i)
values.push_back(i);
VectorView
VectorView
VectorView
VectorView
VectorView
CreateLists
, 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 :
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).
:fleche: Pour aller plus loin sur ce sujet.
Soutenez le club developpez.com en souscrivant un abonnement pour que nous puissions continuer à vous proposer des publications.