Discussion :

[olibara]

Bonjour

Quelqu'un sais-t-il comment inserer efficacement de maniere trieé un élément dans une List<T>

En C j'avais écris un fonction bInsearch qui combinait une recherche dichotomique et l'insertion si nécessaire

[Pol63]

un sortedlist<T> ?

[olibara]

Trier une List<T> ne pose pas de problème
Ce que je cherche c'est d'inserer des element dans la liste au bon endroit sans la trier a chaque insertion ?

[olibara]

Oui je viens de trouver le SortedList que je ne connaissais pas

Mais c'est un peu lourd car il faut comme dans un dictionnaire donner la clef et la valeur, or si la valeur est la clef List<int> ou que la clef est contenue dans la valeur cela fait une redondance d'information d'autant plus encombrante que ces liste sont censées etre tres grande

Je crois que je vais ecrire un InsertSort pour la List qui fera une dichotomie et un Insert

Genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

List.InsertSort(item,comparer);

[olibara]

Et voila j'ai trouvé

C'est tout bete et camouflé dans la doc

If the List<(Of <(T>)>) does not contain the specified value, the method returns a negative integer. You can apply the bitwise complement operation (~) to this negative integer to get the index of the first element that is larger than the search value. When inserting the value into the List<(Of <(T>)>), this index should be used as the insertion point to maintain the sort order.

1- On fait une recherche

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Idx=BinarySearch(Elem,Comparer);

2- Si Idx est >= 0 l'element existe
3- Si Idx est < 0 l'element n'existe pas ~Idx donne la position d'insertion