SL & STL C++

**romeo9423** · 09/09/2005, 12h03

Bonjour,

j'aurais besoin d'un expert STL.
JE souhaiteriais avoir une methode qui prend en parametre une structure et qui l'ajoute à une liste. L'ajout doit se faire en triant suivant un des champs.

La structure est défini comme ceci :

Code :

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

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
 
typedef struct _TDataChunk 
{
	int nType;		// Type : Numeric, String or Binary
	int nSFID;		// FileID
	int nRecNo;		// RecNo
	int nRecLen ;   // Record Length
	int nRecOffset; // Offset From Record
	int nBuffOffset;// Offset from Linear Buffer
	int nDataOffset;// Sert 
	int nChunkSize; // Size in BITS of the chunk
 
}			TDataChunk;
 
typedef struct _TDataInfo 
{
	int	nFullSize;  // DataLen in BITS
	int     nType;      // Type : Numeric, String or Binary
	int     nStdSize;	// Standard architecture size (8, 16, 32 or 64)	
 
	std::list<TDataChunk> chunklist;
 
}			TDataInfo;
 
 
 
void CDataIndex::AddDataChunk(TDataChunk dataChunk)
{
	map<CString, TDataInfo>::iterator it = NULL;
	TDataInfo dataInfo;
 
	// Si la clé recherché n'existe pas on la crée
	it = m_dataIndex.find(szTag);
	if ( it == m_dataIndex.end() ){
 
		dataInfo.nFullSize = 0;
		dataInfo.nStdSize = 0;
		dataInfo.nType = 0
 
		m_dataIndex[ szTag ] = dataInfo;
	}
 
       dataInfo.nFullSize += dataChunk.
       // Ajout de mon TDataChunk  à ma liste chunklist en triant par
       // ordre croissant de nDataOffset
      // ?????????????? COMMENT FAIRE
}

**Floréal** · 09/09/2005, 12h14

Essaye avec la recherche dicotomique / comparaison, pour ton tri

**Caine** · 09/09/2005, 12h55

Sans garanti car ça fait longtemps que je n'ai pas utiliser les vecteurs:

Il est possible je pense d'utiliser un itérateur avec un container vector, il doit y avoir une méthode toute prête alors pour ajouter en triant.

C'est juste une idée.

**Laurent Gomila** · 09/09/2005, 13h20

Il existe des fonctions pour manipuler des conteneurs triés, mais rien pour ce que tu souhaites a priori. Mais bon, le faire à la main n'est pas trop difficile, il te suffit de parcourir ta liste jusqu'à tomber sur un élément plus grand et insérer ton chunk à cet endroit.

Mais pourquoi ne pas simplement utiliser un std::set ?

**romeo9423** · 09/09/2005, 13h56

Envoyé par Loulou24

Il existe des fonctions pour manipuler des conteneurs triés, mais rien pour ce que tu souhaites a priori. Mais bon, le faire à la main n'est pas trop difficile, il te suffit de parcourir ta liste jusqu'à tomber sur un élément plus grand et insérer ton chunk à cet endroit.

Mais pourquoi ne pas simplement utiliser un std::set ?

J'ai pas encore bien compris l'interet du std::set

**Laurent Gomila** · 09/09/2005, 14h01

L'intérêt de std::set est justement d'être trié (et donc d'offrir des opérations en log(n)).

Code :

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

1
2
3
4
5
6
7
8
9
10
11
struct SortChunk
{
    bool operator ()(const TDataChunk& c1, const TDataChunk& c2)
    {
        return c1.nDataOffset < c2.nDataOffset;
    }
};
 
std::set<TDataChunk, SortChunk> chunklist;
 
chunklist.insert(dataChunk);

**romeo9423** · 09/09/2005, 15h18

Envoyé par Loulou24

L'intérêt de std::set est justement d'être trié (et donc d'offrir des opérations en log(n)).

Code :

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

1
2
3
4
5
6
7
8
9
10
11
struct SortChunk
{
    bool operator ()(const TDataChunk& c1, const TDataChunk& c2)
    {
        return c1.nDataOffset < c2.nDataOffset;
    }
};
 
std::set<TDataChunk, SortChunk> chunklist;
 
chunklist.insert(dataChunk);

Maintenenant j'ai le souci suivant apres avoir fait la chose suivante :

Code :

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

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
 
 
typedef struct _TDataChunk 
{
	int nType;		// Type : Numeric, String or Binary (Redondant pour plus de surete)
	int nSFID;		// FileID
	int nRecNo;		// RecNo
	int nRecLen ;   // Record Length
	int nRecOffset; // Offset From Record
	int	nBuffOffset;// Offset from Linear Buffer
	int nDataOffset;// Sert à trier
	int nChunkSize; // Size in BITS of the chunk
 
}			TDataChunk;
 
typedef struct _TDataInfo 
{
	_TDataInfo() {}
	_TDataInfo(int CustomSize, int Type, int StdSize)  
	{
		nType		= Type;
		nStdSize	= StdSize;
		nCustomSize	= CustomSize;
 
	} 
 
	int nType;      // Type : Numeric, String or Binary
	int nStdSize;	// Standard architecture size (8, 16, 32 or 64)	
	int	nCustomSize;  // DataLen in BITS
 
 
	std::list<TDataChunk> chunklist;
 
}			TDataInfo;
 
 
 
void CDataIndex::AddDataChunk(LPCTSTR szTag, int nStdSize, TDataChunk dataChunk)
{
	map<CString, TDataInfo>::iterator it = NULL;
 
	// Si la donnée recherché n'existe pas on la crée
	it = m_dataIndex.find(szTag);
	if ( it == m_dataIndex.end() ){
 
		m_dataIndex[ szTag ] = TDataInfo(dataChunk.nChunkSize, dataChunk.nType, nStdSize);
		it = m_dataIndex.begin(); // on pointe sur le nouvel element
	}
 
	// Clé existe alors on verifie d'abord le type
	if ( (*it).second.nType != dataChunk.nType ){
		CMisc::Message( _T("Erreur de mapping : une donnée fragmentée comporte des types différents\n") );
	}
 
 
	// On ajoute le bout de donnée
	m_dataIndex[ szTag ].chunklist.push_back( dataChunk );
 
	// Maintenant on trie par DataOffset
	std::sort((*it).second.chunklist.begin(), (*it).second.chunklist.end(), SortByDataOffset() );
}

d:\Logiciels\Visual Studio .NET 2003\Vc7\include\algorithm(1941): error C2676: binary '-' : 'std::list<_Ty>::iterator' does not define this operator or a conversion to a type acceptable to the predefined operator
with
[
_Ty=TDataChunk
]
d:\Logiciels\Visual Studio .NET 2003\Vc7\include\algorithm(1941): error C2780: 'void std::_Sort(_RanIt,_RanIt,_Diff)' : expects 3 arguments - 4 provided
d:\Logiciels\Visual Studio .NET 2003\Vc7\include\algorithm(1941): error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::list<_Ty>::iterator'
with
[
_Ty=TDataChunk
]
,

**Laurent Gomila** · 09/09/2005, 16h24

std::sort n'accepte qu'un certain type d'itérateur, qui n'est pas celui de std::list. Il faut utiliser std::list::sort.

Mais... Tu ne veux vraiment pas utiliser std::set ?

**Swoög** · 10/09/2005, 23h52

Juste une petite remarque :

Envoyé par Loulou24

L'intérêt de std::set est justement d'être trié (et donc d'offrir des opérations en log(n)).

Code :

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

1
2
3
4
5
6
7
8
9
10
11
struct SortChunk
{
    bool operator ()(const TDataChunk& c1, const TDataChunk& c2)
    {
        return c1.nDataOffset < c2.nDataOffset;
    }
};
 
std::set<TDataChunk, SortChunk> chunklist;
 
chunklist.insert(dataChunk);

Je pense que c'est plutôt l'opérator < et non () qu'il faudrait surcharger, non ?

**Luc Hermitte** · 11/09/2005, 02h14

Ceci est un foncteur -- classe qui propose un opérateur (), ce qui au final permet d'écrire nom_d_objet() de la même façon que l'on peut écrire non_de_fonction().

std::set attend en 2e argument template quelque chose qui peut agir comme prédicat de comparaison. Ca tombe bien, c'est ce que fait ce foncteur.

C'est en parti traité dans la FAQ.

**Swoög** · 11/09/2005, 02h21

arf, autant pour moi, encore oublié que les conteneurs stl travaillaient avec des foncteurs, et pas des opérateurs de comparaison :\

**Laurent Gomila** · 11/09/2005, 16h23

Ceci dit on peut tout aussi bien définir un opérateur < pour la structure à trier, et omettre le second paramètre template de std::set.

Stl

SL & STL C++

Discussions similaires

Partager

Partager