468,491 Members | 1,996 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,491 developers. It's quick & easy.

stl::sort with a vector

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<IMAGEvImages(100);
for (int i = 0; i < 100; i++) {
vImages[i].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

Aug 28 '06 #1
8 3742
markww wrote:
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
Aug 28 '06 #2

Jens Theisen wrote:
markww wrote:
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
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

Aug 28 '06 #3
On 28 Aug 2006 14:36:41 -0700, "markww" <ma****@gmail.comwrote:
>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
Aug 28 '06 #4
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
Aug 28 '06 #5

Jens Theisen wrote:
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

Aug 29 '06 #6

markww wrote:
Jens Theisen wrote:
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
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::pair<co nst
CString,std::map<CString,std::map<CString,BYTE *>>>>,false>
1 ]

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

Aug 29 '06 #7

markww wrote:
Jens Theisen wrote:
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<BYTEvPix;
};
struct SeriesSink {
map<CString, ImageSinkmImages;
};
struct StudySink {
map<CString, SeriesSinkmSeries;
};

class CDatasetPixelMap {

public:
CDatasetPixelMap();
~CDatasetPixelMap();

map<CString, StudySinkm_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

Aug 29 '06 #8
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:
markww wrote:
Jens Theisen wrote:
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<BYTEvPix;
};
struct SeriesSink {
map<CString, ImageSinkmImages;
};
struct StudySink {
map<CString, SeriesSinkmSeries;
};

class CDatasetPixelMap {

public:
CDatasetPixelMap();
~CDatasetPixelMap();

map<CString, StudySinkm_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
Aug 29 '06 #9

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

6 posts views Thread by Aaron Broad | last post: by
10 posts views Thread by Paul Schneider | last post: by
6 posts views Thread by Der Andere | last post: by
9 posts views Thread by Christian Chrismann | last post: by
2 posts views Thread by thinktwice | last post: by
3 posts views Thread by mweltin | last post: by
2 posts views Thread by alice | last post: by
2 posts views Thread by Builder | last post: by
reply views Thread by NPC403 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.