LinuxQuestions.org - Simple STL question

- Programming (https://www.linuxquestions.org/questions/programming-9/)

- - Simple STL question (https://www.linuxquestions.org/questions/programming-9/simple-stl-question-399927/)

Simple STL question

Hi -

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.