LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 01-05-2006, 02:53 PM   #1
paulsm4
LQ Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
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;
    }
  }
 
Old 01-05-2006, 03:05 PM   #2
Hivemind
Member
 
Registered: Sep 2004
Posts: 273

Rep: Reputation: 30
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?
 
Old 01-05-2006, 03:16 PM   #3
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
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>

Last edited by dmail; 01-05-2006 at 03:33 PM.
 
Old 01-07-2006, 12:30 AM   #4
paulsm4
LQ Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863

Original Poster
Blog Entries: 1

Rep: Reputation: Disabled
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 ;-)

Last edited by paulsm4; 01-07-2006 at 08:24 PM.
 
Old 01-07-2006, 08:20 PM   #5
paulsm4
LQ Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863

Original Poster
Blog Entries: 1

Rep: Reputation: Disabled
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.

Last edited by paulsm4; 01-07-2006 at 08:29 PM.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Ubuntu Fluxbox simple question, simple answer? generallimptoes Linux - Software 3 09-26-2005 02:03 PM
point / STL vector, change element question true_atlantis Programming 1 09-17-2005 01:46 PM
question abt STL algorithim 'difference' irfanhab Programming 2 07-30-2005 09:38 PM
Installing Programs - A simple question from my simple mind jmp875 Linux - Newbie 6 02-18-2004 09:03 PM
Vector(STL) question(push_back & erase) Ohmu Programming 1 01-29-2004 04:50 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 06:21 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration