stl::sort with a vector

[markww]

Hi,

If I have a vector of structs like this:

struct IMAGE {

unsigned char *pPix;
string strName;
int nNumber;
};

and i allocate a bunch of them:

vector<IMAGE> vImages(100);
for (int i = 0; i < 100; i++) {
vImages.pPix = new unsigned char[512 * 512 * 3];
}

(imagine the number and name members are all allocated too). If I use
stl::sort() on this vector, will it try to physically move the memory
allocated in each structure around?

sort(vImages.begin(), vImages.end(), SortByName());
sort(vImages.begin(), vImages.end(), SortByNumber());

I just want to know if this is going to be extremely slow given the
characteristics of those structs.

Thanks

 

[Jens Theisen]

I just want to know if this is going to be extremely slow given the
characteristics of those structs.

It will be copying your structs around, but that's not going to be
terribly slow, because it's reasonably lightweight.

Some unrelated comments:

1. You don't want to allocate memory directly and store it in raw
pointers. Use std::string or std::vector< char > for it.
2. It's very unorthodox to use a name in caps for something else but a
macro, and thus misleading.

Jens

 

[markww]

It will be copying your structs around, but that's not going to be
terribly slow, because it's reasonably lightweight.

Some unrelated comments:

1. You don't want to allocate memory directly and store it in raw
pointers. Use std::string or std::vector< char > for it.
2. It's very unorthodox to use a name in caps for something else but a
macro, and thus misleading.

Jens

Hi Jens,

In the worst case scenario I'll have about 300 elements in the vector
all with [512 * 512 * 3] pixels. I may have as many as 5 such vectors.
Will sort() still perform quickly give that situation?

I agree on your other comments, thanks,

Mark

 

[Roland Pibinger]

In the worst case scenario I'll have about 300 elements in the vector
all with [512 * 512 * 3] pixels. I may have as many as 5 such vectors.
Will sort() still perform quickly give that situation?

It's not only a question of fast or slow. Your struct IMAGE implements
no copy constructor, no assignment operator and no destructor. For
pPix shallow copies are performed. In the case of std::sort that
probably is ok but other functions might not work with 'shallow'
copies (how would you handle ownership of the allocated Pix?). Also
std::unique, std::remove and std::remove_if almost certainly don't
work that way.

Best wishes,
Roland Pibinger

 

[Jens Theisen]

In the worst case scenario I'll have about 300 elements in the vector
all with [512 * 512 * 3] pixels. I may have as many as 5 such vectors.
Will sort() still perform quickly give that situation?

As you did it, the [512 * 512 * 3] pixels are not copied, only a pointer
to it along with an int and a string instance.

So then it should be pretty quick.

However, I suggested using stl containers instead of raw pointers;
normally std::vector will copy it's data if it's copied - but std::sort
doesn't actually copy, it swaps. And swapping std::vectors works in
constant time - so it's fast again.

Jens

 

[markww]

In the worst case scenario I'll have about 300 elements in the vector
all with [512 * 512 * 3] pixels. I may have as many as 5 such vectors.
Will sort() still perform quickly give that situation?

As you did it, the [512 * 512 * 3] pixels are not copied, only a pointer
to it along with an int and a string instance.

So then it should be pretty quick.

However, I suggested using stl containers instead of raw pointers;
normally std::vector will copy it's data if it's copied - but std::sort
doesn't actually copy, it swaps. And swapping std::vectors works in
constant time - so it's fast again.

Jens

Ok maybe you guys can recommend a better structure design. In my app a
user will load 100 for example. Each image is represented by that
structure:

struct Image {
Image() { pPix = NULL; }
~Image() { if (pPix) delete [] pPix; }

string strStudyID;
string strSeriesID;
string strImageID;
int nNumber;
double dPosition;

BYTE *pPix;
};

Now my original idea was that as the user is scrolling through these
stacks of images (ordered by image number) my app loads the pixel data
associated with that image. The user can be viewing the image series in
multiple windows. So each window can point to this one vector of images
so they dont each have to keep their own copy. This was working fine.

Now I run into the problem that my users want to be able to sort the
images by the position tag too. Great. So I tried doing the sort but I
get a crash, I guess cause my destructor automatically deletes the
pixel data pointer during the copy?

So I guess I have to rethink my whole design now. Two big questions:

1) the pPix member might be allocated as unsigned shorts, or unsigned
char, depending on the image type. That's why I did not use a vector of
BYTE etc. Is there a way I can use templating or something to be able
to allocate the space as either unsigned short or unsigned char
depending on the data type? Currently I was doing it like this:

pPix = (BYTE *)new unsigned short[cx * cy];

or

pPix = (BYTE *)new unsigned char[cx * cy];

this worked fine but was a little annoying when I had to access the
pixel data since I had to constantly check what it was allocated as and
cast it before touching it to get the right values.



2) I only want to have to keep one copy of my pixel data (since there
can be an awful lot). I was thinking of keeping one copy in something
like this:

map<string, map<string, set<PixelSink> > m_Dataset;

So it looks like this:
Study A (StudyID)
|
|---- Series 1A (SeriesID)
| | ---- Pixel Sink (just pixel data) (ImageID)
| | ---- Pixel Sink (just pixel data) (ImageID)
|
|---- Series 1B
| | ---- Pixel Sink (just pixel data) (ImageID)
|
|
Study B
| etc...

So in each window view I still keep a vector of IMAGE structs, but
remove the pPix member. When the user wants to sort by whatever tag
they want, I sort the vector with the new scheme, then can still look
up its associated pixel data by studyID, seriesID, imageID in the
global map.

Is that ridiculous? More information needed? Feel free to bash, I don't
want to have to rewrite this again! Thanks for any suggestions,

Mark

 

[markww]

In the worst case scenario I'll have about 300 elements in the vector
all with [512 * 512 * 3] pixels. I may have as many as 5 such vectors.
Will sort() still perform quickly give that situation?

As you did it, the [512 * 512 * 3] pixels are not copied, only a pointer
to it along with an int and a string instance.

So then it should be pretty quick.

However, I suggested using stl containers instead of raw pointers;
normally std::vector will copy it's data if it's copied - but std::sort
doesn't actually copy, it swaps. And swapping std::vectors works in
constant time - so it's fast again.

Jens

Ok maybe you guys can recommend a better structure design. In my app a
user will load 100 for example. Each image is represented by that
structure:

struct Image {
Image() { pPix = NULL; }
~Image() { if (pPix) delete [] pPix; }

string strStudyID;
string strSeriesID;
string strImageID;
int nNumber;
double dPosition;

BYTE *pPix;
};

Now my original idea was that as the user is scrolling through these
stacks of images (ordered by image number) my app loads the pixel data
associated with that image. The user can be viewing the image series in
multiple windows. So each window can point to this one vector of images
so they dont each have to keep their own copy. This was working fine.

Now I run into the problem that my users want to be able to sort the
images by the position tag too. Great. So I tried doing the sort but I
get a crash, I guess cause my destructor automatically deletes the
pixel data pointer during the copy?

So I guess I have to rethink my whole design now. Two big questions:

1) the pPix member might be allocated as unsigned shorts, or unsigned
char, depending on the image type. That's why I did not use a vector of
BYTE etc. Is there a way I can use templating or something to be able
to allocate the space as either unsigned short or unsigned char
depending on the data type? Currently I was doing it like this:

pPix = (BYTE *)new unsigned short[cx * cy];

or

pPix = (BYTE *)new unsigned char[cx * cy];

this worked fine but was a little annoying when I had to access the
pixel data since I had to constantly check what it was allocated as and
cast it before touching it to get the right values.



2) I only want to have to keep one copy of my pixel data (since there
can be an awful lot). I was thinking of keeping one copy in something
like this:

map<string, map<string, set<PixelSink> > m_Dataset;

So it looks like this:
Study A (StudyID)
|
|---- Series 1A (SeriesID)
| | ---- Pixel Sink (just pixel data) (ImageID)
| | ---- Pixel Sink (just pixel data) (ImageID)
|
|---- Series 1B
| | ---- Pixel Sink (just pixel data) (ImageID)
|
|
Study B
| etc...

So in each window view I still keep a vector of IMAGE structs, but
remove the pPix member. When the user wants to sort by whatever tag
they want, I sort the vector with the new scheme, then can still look
up its associated pixel data by studyID, seriesID, imageID in the
global map.

Is that ridiculous? More information needed? Feel free to bash, I don't
want to have to rewrite this again! Thanks for any suggestions,

Mark

Ok so I tried to make a class to represent this data structure which is
a bit of a monster and the compiler complains too:

class CPixelMap {

map<CString, map<CString, map<CString, vector<BYTE> > > >
m_Data;

};

Then I could have looked up the pixel data like:

vector<BYTE> *pPix = *m_Data[studyID][seriesID][imageID];

it compiles but the compiler (vc 2005) gives me a bunch of warnings:

1>c:\program files\microsoft visual studio
8\vc\atlmfc\include\afxtempl.h(1264) : warning C4503:
'std::_Tree<_Traits>::_Myval' : decorated name length exceeded, name
was truncated
1> with
1> [
1>
_Traits=std::_Tmap_traits<CString,std::map<CString,std::map<CString,BYTE
*>>,std::less<CString>,std::allocator<std:air<const
CString,std::map<CString,std::map<CString,BYTE *>>>>,false>
1> ]

this could have worked really well, anyway to get around the warnings?

 

[markww]

In the worst case scenario I'll have about 300 elements in the vector
all with [512 * 512 * 3] pixels. I may have as many as 5 such vectors.
Will sort() still perform quickly give that situation?

As you did it, the [512 * 512 * 3] pixels are not copied, only a pointer
to it along with an int and a string instance.

So then it should be pretty quick.

However, I suggested using stl containers instead of raw pointers;
normally std::vector will copy it's data if it's copied - but std::sort
doesn't actually copy, it swaps. And swapping std::vectors works in
constant time - so it's fast again.

Jens

Ok maybe you guys can recommend a better structure design. In my app a
user will load 100 for example. Each image is represented by that
structure:

struct Image {
Image() { pPix = NULL; }
~Image() { if (pPix) delete [] pPix; }

string strStudyID;
string strSeriesID;
string strImageID;
int nNumber;
double dPosition;

BYTE *pPix;
};

Now my original idea was that as the user is scrolling through these
stacks of images (ordered by image number) my app loads the pixel data
associated with that image. The user can be viewing the image series in
multiple windows. So each window can point to this one vector of images
so they dont each have to keep their own copy. This was working fine.

Now I run into the problem that my users want to be able to sort the
images by the position tag too. Great. So I tried doing the sort but I
get a crash, I guess cause my destructor automatically deletes the
pixel data pointer during the copy?

So I guess I have to rethink my whole design now. Two big questions:

1) the pPix member might be allocated as unsigned shorts, or unsigned
char, depending on the image type. That's why I did not use a vector of
BYTE etc. Is there a way I can use templating or something to be able
to allocate the space as either unsigned short or unsigned char
depending on the data type? Currently I was doing it like this:

pPix = (BYTE *)new unsigned short[cx * cy];

or

pPix = (BYTE *)new unsigned char[cx * cy];

this worked fine but was a little annoying when I had to access the
pixel data since I had to constantly check what it was allocated as and
cast it before touching it to get the right values.



2) I only want to have to keep one copy of my pixel data (since there
can be an awful lot). I was thinking of keeping one copy in something
like this:

map<string, map<string, set<PixelSink> > m_Dataset;

So it looks like this:
Study A (StudyID)
|
|---- Series 1A (SeriesID)
| | ---- Pixel Sink (just pixel data) (ImageID)
| | ---- Pixel Sink (just pixel data) (ImageID)
|
|---- Series 1B
| | ---- Pixel Sink (just pixel data) (ImageID)
|
|
Study B
| etc...

So in each window view I still keep a vector of IMAGE structs, but
remove the pPix member. When the user wants to sort by whatever tag
they want, I sort the vector with the new scheme, then can still look
up its associated pixel data by studyID, seriesID, imageID in the
global map.

Is that ridiculous? More information needed? Feel free to bash, I don't
want to have to rewrite this again! Thanks for any suggestions,

Mark

Alright I tried it out, here's the container class I made:

struct ImageSink {
vector<BYTE> vPix;
};
struct SeriesSink {
map<CString, ImageSink> mImages;
};
struct StudySink {
map<CString, SeriesSink> mSeries;
};

class CDatasetPixelMap {

public:
CDatasetPixelMap();
~CDatasetPixelMap();

map<CString, StudySink> m_DatasetPixelMap;

vector<BYTE> *GetPixelPointer(id,id,id);
}

Now I can get a pointer to the pixel data like:

vector<BYTE> *CDatasetPixelMap::GetPixelPointer(id, id, id)
{
return
&m_DatasetPixelMap[strStudyID].mSeries[strSeriesID].mImages[strImgID].vPix;
}

Is that complelety ridiculous? Looking up the appropriate pixel vector
should be pretty fast thanks to use of the maps right?

Thanks,
Mark

 

[Shooting]

I think your previous implementation is ok. std::map require log time
to find,insert,delete and not so fast as you may think

markww wrote:
In the worst case scenario I'll have about 300 elements in the vector
all with [512 * 512 * 3] pixels. I may have as many as 5 such vectors.
Will sort() still perform quickly give that situation?

As you did it, the [512 * 512 * 3] pixels are not copied, only a pointer
to it along with an int and a string instance.

So then it should be pretty quick.

However, I suggested using stl containers instead of raw pointers;
normally std::vector will copy it's data if it's copied - but std::sort
doesn't actually copy, it swaps. And swapping std::vectors works in
constant time - so it's fast again.

Jens

Ok maybe you guys can recommend a better structure design. In my app a
user will load 100 for example. Each image is represented by that
structure:

struct Image {
Image() { pPix = NULL; }
~Image() { if (pPix) delete [] pPix; }

string strStudyID;
string strSeriesID;
string strImageID;
int nNumber;
double dPosition;

BYTE *pPix;
};

Now my original idea was that as the user is scrolling through these
stacks of images (ordered by image number) my app loads the pixel data
associated with that image. The user can be viewing the image series in
multiple windows. So each window can point to this one vector of images
so they dont each have to keep their own copy. This was working fine.

Now I run into the problem that my users want to be able to sort the
images by the position tag too. Great. So I tried doing the sort but I
get a crash, I guess cause my destructor automatically deletes the
pixel data pointer during the copy?

So I guess I have to rethink my whole design now. Two big questions:

1) the pPix member might be allocated as unsigned shorts, or unsigned
char, depending on the image type. That's why I did not use a vector of
BYTE etc. Is there a way I can use templating or something to be able
to allocate the space as either unsigned short or unsigned char
depending on the data type? Currently I was doing it like this:

pPix = (BYTE *)new unsigned short[cx * cy];

or

pPix = (BYTE *)new unsigned char[cx * cy];

this worked fine but was a little annoying when I had to access the
pixel data since I had to constantly check what it was allocated as and
cast it before touching it to get the right values.



2) I only want to have to keep one copy of my pixel data (since there
can be an awful lot). I was thinking of keeping one copy in something
like this:

map<string, map<string, set<PixelSink> > m_Dataset;

So it looks like this:
Study A (StudyID)
|
|---- Series 1A (SeriesID)
| | ---- Pixel Sink (just pixel data) (ImageID)
| | ---- Pixel Sink (just pixel data) (ImageID)
|
|---- Series 1B
| | ---- Pixel Sink (just pixel data) (ImageID)
|
|
Study B
| etc...

So in each window view I still keep a vector of IMAGE structs, but
remove the pPix member. When the user wants to sort by whatever tag
they want, I sort the vector with the new scheme, then can still look
up its associated pixel data by studyID, seriesID, imageID in the
global map.

Is that ridiculous? More information needed? Feel free to bash, I don't
want to have to rewrite this again! Thanks for any suggestions,

Mark

Alright I tried it out, here's the container class I made:

struct ImageSink {
vector<BYTE> vPix;
};
struct SeriesSink {
map<CString, ImageSink> mImages;
};
struct StudySink {
map<CString, SeriesSink> mSeries;
};

class CDatasetPixelMap {

public:
CDatasetPixelMap();
~CDatasetPixelMap();

map<CString, StudySink> m_DatasetPixelMap;

vector<BYTE> *GetPixelPointer(id,id,id);
}

Now I can get a pointer to the pixel data like:

vector<BYTE> *CDatasetPixelMap::GetPixelPointer(id, id, id)
{
return
&m_DatasetPixelMap[strStudyID].mSeries[strSeriesID].mImages[strImgID].vPix;
}

Is that complelety ridiculous? Looking up the appropriate pixel vector
should be pretty fast thanks to use of the maps right?

Thanks,
Mark