The C vs. C++ way

Question

Hi,

So I have to write a program that will iterate through an image and record the pixel locations corresponding to each color pixel that appears in it. For example, given

http://www.socuteurl.com/fishywishykissy

I need to find the coordinates of all yellow, purple, dark pink, etc pixels.

In C++ I would use a hash table to do this. I would iterate through the image, check each pixel's value, look up that value and either add to a vector of pixel coordinates if it were found or add a new entry to the table if the value were not already there.

The problem is that I may need to write this program in pure C instead of C++. How would I go about doing this in C? I feel like implementing a hash table would be pretty obnoxious and error-prone: should I avoid doing that?

I'm pretty inexperienced with C and have a fair amount of C++ experience, if that matters.

Thanks.

Answer 1

You should be able to find well tested implementations of hash tables and linked lists for C.

Just out of curiosity, why would you be required to use that language?

Answer 2

You might consider using uthash, which will allow you to store structures within a hash table. Then just define a struct to store pixel/count information and you are good to go.

Or you could roll your own HashTable in C, although it would be mostly as a learning exercise.

Answer 3

There is no algorithm/datastructure you can implement in C++ that you can't implement in C. Sometimes it's arguably more elegant in C++, but it is never impossible in C.

Here are some C hash table implementations: http://www.google.ca/search?q=hash+table+c

You may also be interested in this OOP in C vs C++ link: http://www.eventhelix.com/realtimemantra/basics/object_oriented_programming_in_c.htm

In general, where you'd use classes in C++, you can use structs+functions in C.

Answer 4

For standard functions check the search.h header file and functions it provides. They can be cumbersome to use, but sometimes nevertheless are useful.

In particular: man hsearch and man tsearch

Answer 5

The answers to this SO question have pointers to a lot of options for container libraries in C that you might find useful:

• Container Class / Library for C

Answer 6

Try this.

Allocate a second image, with each element having the size of one coordinate. Allocate another array with the size of the maximum number of colors. Initialize that array to invalid coordinates (say, (-1,-1) ). Iterate through the image. For each color you find, find the corresponding entry in the array. Store the value in the array at the corresponding position in the second image, and store the current coordinate at that place in the array.

Once you're done, your array will form a faux-linked-list to pixel coordinates.

(Don't know if my explanation makes sense, complain if it doesn't).

Answer 7

Here's an alternate algorithm that uses a bit of extra memory, but is easy to implement.

Go through the image and for each pixel, add it to a new array along with its coordinates. Where the pixel value is (R,G,B) put the values (R,G,B,X,Y) into the new array.

Use qsort to sort the new array. Now all pixels of the same color will be grouped together.