ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
I'm trying to store a simple "struct" in an STL set.
The goal is to create a list of all the colors in a series of RGB images, and reduce them down to a single 256-entry color palette. The reasons I want to use a "set" are:
a) Since the entries are stored in sorted order (here, by RGBA value), lookup is fast and easy
b) I don't want any duplicates (if a color appears more than once, I tally the #/occurrences).
I'm not proficient with STL. All of the examples I could find deal with scalars (numbers or strings), and not "structs". I got "structs" to work - but it's really ugly and convoluted.
QUESTION:
Is the way I saved "structs" in my STL "set" correct, or is there a better way?
Thanx in advance .. PSM
Code:
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <png.h>
#include <set>
#include <algorithm>
using namespace std;
...
typedef unsigned long RGB_TYPE;
typedef struct rgb_histogram
{
RGB_TYPE quad;
int ct;
int idx;
}
rgb_histogram, *rgb_histogram_p;
// <= I can't get the "set<>" template to work unless I do a typedef for "rgb_histogram_p"
struct id_compare {
bool operator()(const rgb_histogram_p x, const rgb_histogram_p y) const
{
return x->quad < y->quad;
}
};
// <= This struct is necessary so STL can compare (and hence sort) my elements
...
int
gen_histogram (const char *fname, set<rgb_histogram_p, id_compare> * color_set_p)
{
...
// Parse the color table for unique colors
png_bytep* row_pointers = png_get_rows (png_ptr, info_ptr);
for (int y = info_ptr->height-1; y >= 0; --y)
{
// ... Start next row
png_bytep pixel = row_pointers[y];
for (unsigned int x = 0; x < info_ptr->width; x++)
{
// ... Read pixel
RGB_TYPE quad = pixel[0]+(pixel[1]<<8)+(pixel[2]<<16);
// ... Alloc new struct
struct rgb_histogram *rec_p = new struct rgb_histogram;
memset (rec_p, 0, sizeof (struct rgb_histogram));
rec_p->quad = quad;
// <= I literally need to allocate a new "struct" ... just to do
// the compare ... whether I'm going to keep it or not!
set<rgb_histogram_p, id_compare>::iterator ii;
ii = color_set_p->find (rec_p);
if (ii == color_set_p->end())
{
// ... This color does not exist: add it
color_set_p->insert (rec_p);
}
else
{
// ... Deallocate the temp pointer
delete rec_p;
// ... Dereference and increment the found pointer
rec_p = *ii;
rec_p->ct += 1;
// <= To increment the counter, I need to:
// a) throw away the struct I just made (to search with)
// b) dereference the struct I found
// c) modify it
// Is this all really necessary?!?
}
// ... Get next pixel
pixel+=bytesPerPixel;
}
}
Well, it's clear you normally code in C, not C++ and it would have been nice with some platform neutral code complete with a test program, but why does the set need to store pointers?
i don't like the fact you need to create a struct which you may not want, maybe using a std::map with the key as the unsigned long, maps can also do quick look ups. but this may mean storing the 4 bytes of rgb data twice. once as the key and once in the struct.
Just a thought ;(
heres another thought whats the value of the left byte of the
RGB_TYPE quad = pixel[0]+(pixel[1]<<8)+(pixel[2]<<16);
it maybe an idea to push a zero value to the byte to be safe.
<edit> or will this be ok hmmmmm. too many things on my mind to think straight ;(</edit>
Thanx, dmail - I don't like it either, which was the reason for my post. Nevertheless, I absolutely couldn't think of any better/easier way to:
a) Sort my elements into a set (needed a "set" because 1) I needed fast inserts and fast lookups, and 2) because I needed to insure uniqueness)
b) Make the elements "structs" (aggreggate data: not scalars, but not full-fledged classes, either).
Anyway, thank you for the response.
PS:
No thanks to you, Hivemind, for your arrogant, condescending attitude. I'd like to think you were just having a bad day ... and that you took it out on me, rather than going home and kicking the dog ;-)
My new edition of C/C++ User's Journal arrived in the mail today, and there was a note in Andrei Alexandrescu's column that suggests maybe my problem using "structs" with STL "sets" might indeed be a fundamental limitation in STL itself:
Quote:
I was, therefore, more than a bit surprised when stumbling upon a problem that has std::map written all over it, yet can't be solved with the help of an [i]std::map[i] in any reasonable way...
Quote:
...You'd have to create a string from the [iconst char *[i] (which could trigger a call all the way to the memory allocator), then look it up in the map, and then likely throw it away...
Sound familiar? A second example is even closer to home:
Quote:
...The problem is, most of the time, input data doesn't come in the form of vectors, but instead as some pointer in a buffer that's been read from a file. Copying that buffer into yet another vector just for the sake of looking it up in the cache sounds a lot like selling apples just to buy pears. There's a more general problem lurking behind these examples...
Indeed! Final quote from Mr. Alexandrescu:
Quote:
It is surprising that in spite of its versatility, std::map cannot efficiently accomodate keys of altnerate type.
Sigh...
PS:
Sadly, it looks like this month's edition of C/C++ User's Journal (the Feb 2006 edition) is going to be the last one. After nearly 30 years, they're ceasing publication.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.