fastest way of storing structured data

[Vince]

Hi,

I am working on a project involving contactless card and to read or
write into these cards we need some parameters (Key to use for instance).
My problem is to store these parameters in the most efficient way.

I was thinking first in a c manner as a struct array like this :
struct TFileInfo
{
int nSFID, // Short file ID
int nLID, // Long File ID
int nKey
};
// not sure of the syntax, it's been a long time I haven't used it
TFileInfo fileInfo[] =
{
{ 0x17, 0x3127, 0x0E },
{ 0x18, 0x3128, 0x08 },
};
and after I need to be able to get the values associated to nSFID.
ex :
CMyClass::GetKe y(int nSFID)
{
for (int i = 0; i < nItems; i++){
if (fileInfo[i].nSFID == nSFID)
return fileInfo[i].nKey
}
}
Or another solution would be to use a std::map<int, TFileInFo>
but I am concerned about performance. Besides I don't find the
initialization very elegant

std::map<int, TFileInfo> fileInfo;

TFileInfo stFileInfo;

stFileInfo.nSFI D = 0x17;
stFileInfo.nLID = 0x3127;
stFileInfo.nKey = 0x0E;
fileInfo[0x17] = stFileInfo;

stFileInfo.nSFI D = 0x18;
stFileInfo.nLID = 0x3128;
stFileInfo.nKey = 0x0E;
fileInfo[0x17] = stFileInfo;

I must add that my numbers of items will be 20 max.
If someone could inform me about this performance problem...

[Alipha]

Vince wrote:

Hi,

I am working on a project involving contactless card and to read or
write into these cards we need some parameters (Key to use for instance).
My problem is to store these parameters in the most efficient way.

I was thinking first in a c manner as a struct array like this :
struct TFileInfo
{
int nSFID, // Short file ID
int nLID, // Long File ID
int nKey
};
// not sure of the syntax, it's been a long time I haven't used it
TFileInfo fileInfo[] =
{
{ 0x17, 0x3127, 0x0E },
{ 0x18, 0x3128, 0x08 },
};
and after I need to be able to get the values associated to nSFID.
ex :
CMyClass::GetKe y(int nSFID)
{
for (int i = 0; i < nItems; i++){
if (fileInfo[i].nSFID == nSFID)
return fileInfo[i].nKey
}
}

this will take an average of 10 comparisions to find the value, if
there's 20 elements. A std::map will take an average of 4 comparisions.
And so, which is more efficient? A linear search is O(n) while a search
on a std::map is O(log n).

Or another solution would be to use a std::map<int, TFileInFo>
but I am concerned about performance. Besides I don't find the
initialization very elegant

std::map<int, TFileInfo> fileInfo;

TFileInfo stFileInfo;

stFileInfo.nSFI D = 0x17;
stFileInfo.nLID = 0x3127;
stFileInfo.nKey = 0x0E;
fileInfo[0x17] = stFileInfo;

stFileInfo.nSFI D = 0x18;
stFileInfo.nLID = 0x3128;
stFileInfo.nKey = 0x0E;
fileInfo[0x17] = stFileInfo;

I must add that my numbers of items will be 20 max.
If someone could inform me about this performance problem...

you might want to consider a std::set instead, since the key is
embedded into the TFileInfo struct. Then give your struct a an
operator<, or pass a functor as the 2nd template argument to std::set.

In any case, you can initialize a std::set or std::map with an array:

std::set<TFileI nfo> myset(fileInfo, fileInfo + 20); // where fileInfo
is the array you have above

A std::map expects iterators to std::pairs, which makes the
initialization a little more awkward:

// you must give TFileInfo a constructor
std::pair<int, TFileInfo> init[] =
{ std::make_pair( 0x17, TFileInfo(0x17, 0x3127, 0x0E)),
std::make_pair( ... , TFileInfo( ... )),
...
};

std::map<int, TFileInfo> mymap(init, init + 20);

[Marc Mutz]

Vince wrote:

CMyClass::GetKe y(int nSFID)
{
for*(int*i*=*0; *i*<*nItems;*i+ +){
if (fileInfo[i].nSFID == nSFID)
return fileInfo[i].nKey
}
}

If you sort your array 'fileInfo' by the nSFID field, then
you can have O(logN) lookup by using std::lower_boun d().

There's nothing wrong per se with POD arrays, esp. if they
can be const, and thus be put into read-only memory.

Marc

[David Hilsee]

"Vince" <vs**@caramail. com> wrote in message
news:43******** *************** @news.free.fr.. .

Hi,

I am working on a project involving contactless card and to read or
write into these cards we need some parameters (Key to use for instance).
My problem is to store these parameters in the most efficient way.

I was thinking first in a c manner as a struct array like this :
struct TFileInfo
{
int nSFID, // Short file ID
int nLID, // Long File ID
int nKey
};
// not sure of the syntax, it's been a long time I haven't used it
TFileInfo fileInfo[] =
{
{ 0x17, 0x3127, 0x0E },
{ 0x18, 0x3128, 0x08 },
};
and after I need to be able to get the values associated to nSFID.
ex :
CMyClass::GetKe y(int nSFID)
{
for (int i = 0; i < nItems; i++){
if (fileInfo[i].nSFID == nSFID)
return fileInfo[i].nKey
}
}
Or another solution would be to use a std::map<int, TFileInFo>
but I am concerned about performance. Besides I don't find the
initialization very elegant

std::map<int, TFileInfo> fileInfo;

TFileInfo stFileInfo;

stFileInfo.nSFI D = 0x17;
stFileInfo.nLID = 0x3127;
stFileInfo.nKey = 0x0E;
fileInfo[0x17] = stFileInfo;

stFileInfo.nSFI D = 0x18;
stFileInfo.nLID = 0x3128;
stFileInfo.nKey = 0x0E;
fileInfo[0x17] = stFileInfo;

I must add that my numbers of items will be 20 max.
If someone could inform me about this performance problem...

Performance questions are best answered by performance tests. Since there's
only 20 items, I'd bet that the difference between the array and std::map
wouldn't be significant unless your application performs this lookup very
frequently.

As Marc pointed out, sorting the entries and using a search routine is
another option. Also, if nSFID has a limited range, you could create an
array that can be indexed by the nSFID, giving you O(1) lookup time (but
possibly requiring a little more memory).

--
David Hilsee

[Karl Heinz Buchegger]

Vince wrote:

Others have already talked about your 'performance' issue.

But ...
Besides I don't find the
initialization very elegant

std::map<int, TFileInfo> fileInfo;

TFileInfo stFileInfo;

stFileInfo.nSFI D = 0x17;
stFileInfo.nLID = 0x3127;
stFileInfo.nKey = 0x0E;
fileInfo[0x17] = stFileInfo;

stFileInfo.nSFI D = 0x18;
stFileInfo.nLID = 0x3128;
stFileInfo.nKey = 0x0E;
fileInfo[0x17] = stFileInfo;

.... this can easily be cured.
Just provide your struct with a constructor:

struct TFileInfo
{
TFileInfo( int SFID, int LID, int Key )
: nSFID( SFID ), nLID( LID ), nKey( Key )
{}

int nSFID, // Short file ID
int nLID, // Long File ID
int nKey
};

and now you can ceasily create objects and initialize them
on the fly:

fileInfo[0x17] = TFileInfo( 0x17, 0x3127, 0x0E );
fileInfo[0x18] = TFileInfo( 0x18, 0x3128, 0x0E );

--
Karl Heinz Buchegger
kb******@gascad .at

[Capstar]

Alipha wrote:

Vince wrote:

Hi,

I am working on a project involving contactless card and to read or
write into these cards we need some parameters (Key to use for instance).
My problem is to store these parameters in the most efficient way.

I was thinking first in a c manner as a struct array like this :
struct TFileInfo
{
int nSFID, // Short file ID
int nLID, // Long File ID
int nKey
};

you might want to consider a std::set instead, since the key is
embedded into the TFileInfo struct. Then give your struct a an
operator<, or pass a functor as the 2nd template argument to std::set.

But how would you get the TFileInfo structure you're looking for? If I
want to use set::find(), I need to pass a struct TFileInfo, but I just
have a nSFID.

Mark

[Alipha]

Capstar wrote:

[snip]

But how would you get the TFileInfo structure you're looking for? If I
want to use set::find(), I need to pass a struct TFileInfo, but I just
have a nSFID.

Mark

create a TFileInfo with the nSFID field set to what you want then. If
you give your struct a one-argument ctor (probably explicit), then it
would be easy to do myset.find(TFil eInfo(0x17)). Of course, you lose
the ability to initialize your struct with { } initializers.