Csortedarray<template> visual c++ mfc

Commenter

Contenu du snippet

Une classe template dérivée du CArray des MFC
J'ai ajouté des méthodes de tri qui manquent cruellement
Vu que je manipule beaucoup de données au boulot, je m'en sert souvent

AddSorted(element) : ajoute "element" par insertion après recherche de sa position par dichotomie
Sort() : tri la table à l'aide d'un qSort
PartialSort(start, end) : tri une partie de la table avec qSort
Swap(src,dst) : échange 2 éléments dans la table

j'ai laissé les méthodes de tri partiel et de swap en public vu qu'elles ont leur utilité pour moi

Source / Exemple : 


#pragma once

#include "afxtempl.h"

// Classe dérivée de CArray en reprenant toutes les capacités
// Ajout de méthodes de tri et d'ajout par insertion avec recherche de position par dichotomie
template <class TYPE, class ARG_TYPE = const TYPE&>
class CSortedArray : public CArray<TYPE, ARG_TYPE>
{
public:
	INT_PTR AddSorted(TYPE newElement); // Ajout par insertion avec recherche de position par dichotomie
	void Sort(void) { QuickSort(0, GetCount()-1); } // Effectue un tri complet de la table à l'aide la méthode QuickSort
	void PartialSort(INT_PTR startIndex, INT_PTR endIndex); // Effectue un tri partiel de la table
	void Swap(INT_PTR src, INT_PTR dst) { TYPE tmp=GetAt(src); SetAt(src, GetAt(dst)); SetAt(dst, tmp); } // Echange 2 éléments dans la table

protected:
	void QuickSort(INT_PTR startIndex, INT_PTR endIndex);
};

// Ajoute un élément à la table par insertion en recherchant sa position par dichotomie
// Entrée : le nouvel élément à ajouter
// Sortie : l'index dans la table où le nouvel élément a été ajouté
template <class TYPE, class ARG_TYPE>
AFX_INLINE INT_PTR CSortedArray<TYPE, ARG_TYPE>::AddSorted(TYPE newElement)
{
	INT_PTR start = 0, end = GetCount();
	while(start < end)
	{
		INT_PTR pos = (start + end) / 2;
		if(newElement > GetAt(pos))
			start = pos + 1;
		else
			end = pos;
	}
	InsertAt(start, newElement);
	return start;
}

// Effectue un tri QuickSort des éléments compris entre les index "A" et "B" (inclus)
// Entrée : l'index du premier élément et l'index du dernier élément à trier
template <class TYPE, class ARG_TYPE>
AFX_INLINE void CSortedArray<TYPE, ARG_TYPE>::PartialSort(INT_PTR startIndex, INT_PTR endIndex)
{
	if(startIndex < 0)
		startIndex = 0;

	if(endIndex >= GetCount())
		endIndex = GetCount() - 1;

	if(startIndex >= endIndex)
		return;

	QuickSort(startIndex, endIndex);
}

// Méthode de tri QuickSort d'une portion de la table
// Entrée : l'index du premier élément à trier et l'index du dernier élément à trier
template <class TYPE, class ARG_TYPE>
AFX_INLINE void CSortedArray<TYPE, ARG_TYPE>::QuickSort(INT_PTR startIndex, INT_PTR endIndex)
{
	if(startIndex >= endIndex)
		return;

	if(startIndex == endIndex - 1)
	{
		if(GetAt(startIndex) > GetAt(endIndex))
			Swap(startIndex, endIndex);
		return;
	}

	INT_PTR startToEnd = startIndex, endToStart = endIndex;

	Swap((startToEnd + endToStart) / 2, endToStart);

	TYPE middle = GetAt(endToStart);

	while(startToEnd < endToStart)
	{
		while(GetAt(startToEnd) <= middle && startToEnd < endToStart) startToEnd++;
		while(middle <= GetAt(endToStart) && startToEnd < endToStart) endToStart--;
		if(startToEnd < endToStart)
			Swap(startToEnd, endToStart);
	}

	SetAt(endIndex, GetAt(endToStart));
	SetAt(endToStart, middle);

	QuickSort(startIndex, startToEnd - 1);

	QuickSort(endToStart + 1, endIndex);
}

Conclusion :


J'ai séparé la fonction de comparaison pour pouvoir la modifier facilement à votre convenance, par exemple pour trier dans l'ordre croissant ou décroissant

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (shenron666)