comparing structures

This is a discussion on comparing structures within the C Programming forums, part of the General Programming Boards category; hello everyone ! I just wanted to know of there exist a way of comparing two values whose type is ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    2

    comparing structures

    hello everyone !

    I just wanted to know of there exist a way of comparing two values whose type is created by the programmer without having to compary all the structure's members ? (for eg , to compare string we user strcmp....)

    suppose we have this structure (record) :
    Code:
    typedef struct{
    int a,
    char b[];
    double c;
    }var1, var2;
    how to compare var1 and var1 ?

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    You can write a function to compare those however you like as there are many ways of doing it. It all depends on what those variables mean.
    For example, if b was a person's name, c was their birthdate, and a was their favourite colour, then one reasonable way to define a comparison function might be:
    Code:
    int compare(myStruct *l, myStruct *r)
    {
        int cmp = strcmp(l->b, r->b);
        if (cmp != 0) return cmp;
        if (l->c < r->c) return -1;
        if (l->c > r->c) return 1;
        return 0;
    }
    Note that b takes no part in the comparison here because it doesn't make sense for the array in question to have two people with the same name and the same birthdate, but with a different favourite colour.
    In order to know how you want YOUR data compared, you'll have to post a REAL struct definition.

    I'm pretty sure that you can't declare an array without a size, except as the last item in a struct (even then only on some compilers).
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Maz
    Maz is offline
    Registered User Maz's Avatar
    Join Date
    Nov 2005
    Location
    Finland
    Posts
    194
    Problem in declaring unknown sized array is a fundamental feature in C. It returns to the very basics of C and memory.

    The structs, variables, everything is just data in memory, starting from certain location, and continuing to certain amount of bytes. And when you handle, lets say a struct, the place of certain members is calculated based on the definition of a struct. Compiler needs to know the size of the struct members, in order to be able to calculate the starting address of the next member.

    However, if you know the size of a struct, you can compare it to another struct by just comparing the data from the starting adresses of the struct, untill the sizeof struct. You can do that easily in a loop, or with some standard functions like memcmp()

  4. #4
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Code:
    int compare(myStruct *l, myStruct *r)
    {
        int cmp = strcmp(l->b, r->b);
        if (cmp != 0) return cmp;
        if (l->c < r->c) return -1;
        if (l->c > r->c) return 1;
        return 0;
    }
    would that work? would be cool if it does, but I would have thought that it wouldent as structs arent null terminated. Maybe strncmp with sizeof(myStruct)

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Structs don't need to be null terminated, themselves - they are accessed by the size of their members which is known by the definition of the struct.

    A char array, inside a struct, can be marked with an end-of-string char, of course.

    BTW, Mike. Did you finish your Tic-Tac-Toe game?

    When I was writing up my TTT game, I found out I had only learned *one* of the three winning tricks in TTT, as a kid. I was taken aback, to be sure!
    Last edited by Adak; 02-15-2009 at 03:10 PM.

  6. #6
    Registered User
    Join Date
    Apr 2006
    Posts
    2,021
    Quote Originally Posted by sleepywalker View Post
    hello everyone !

    I just wanted to know of there exist a way of comparing two values whose type is created by the programmer without having to compary all the structure's members ? (for eg , to compare string we user strcmp....)

    suppose we have this structure (record) :
    Code:
    typedef struct{
    int a,
    char b[];
    double c;
    }var1, var2;
    how to compare var1 and var1 ?
    How does this even compile? You can't have a array without a specified size in the middle of a struct. Also, you are declaring var1 and var2 as type synonyms, not variables.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  7. #7
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    BTW, Mike. Did you finish your Tic-Tac-Toe game?

    When I was writing up my TTT game, I found out I had only learned *one* of the three winning tricks in TTT, as a kid. I was taken aback, to be sure!
    Nah, i never bothered writing the game logic for it as thats not all that fun, and I dont think anyone would want to play the game anyway, lol. So i kinda dropped it after dealing with the move evaluation. I wrote an Othello game in Java using swing after that, which can be played 2 player and plan on adding AI to it when I get time.

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Maz View Post
    However, if you know the size of a struct, you can compare it to another struct by just comparing the data from the starting adresses of the struct, untill the sizeof struct. You can do that easily in a loop, or with some standard functions like memcmp()
    That works for comparing to see if two structs are equal. For any "greater/lesser than" it is unlikely to work - the reason being that it simply compares bytes until it finds either the end or a byte that is different [it may well do this in a way that assumes largely equality and compares LARGE chunks, e.g. 8 or 16 bytes at a time, and only resorts to comparing individual bytes when it's found a chunk that is different]. This really only works for strings and other arrays of bytes. For any other data structure, there are two problems:
    1. There may be gaps for alignment purposes in the structure that aren't filled in at all - so random bytes will disrupt the comparison, but do not actually contain valid data.
    2. Integer values are not always stored "big endian", and a little-endian value of 255 is "greater" than 16777216 - which of course isn't what you want if you want to know if x.a > y.a.
    3. If the structure contains pointers, it would be impossible to compare that in this way - that will ABSOLUTELY have to be compared a different way (unless you actually want to know if all pointers are pointing to the same place, rather than if they are pointing to equal content).

    --
    Mats

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    I can't see any reason for not comparing the struct member for member, as in x.m1==y.m1, x.m2==y.m2 and so on. On a sidenote, it's certainly not possible to write a generic struct comparing function.

    When I was writing up my TTT game, I found out I had only learned *one* of the three winning tricks in TTT, as a kid.
    There is no winning trick in TTT.

    TTT is a 2-player finite zero-sum game with perfect information, hence there exists an optimal strategy, the minimax algorithm. When playing against a perfect player, the best you can hope for is a tie.

    The same applies to other such games like go and chess, but there it's harder to become a perfect player.

    Greets,
    Philip
    Last edited by Snafuist; 02-16-2009 at 08:29 AM.
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  10. #10
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,451
    Code:
    typedef struct{
        int a;
        char b[10];
        double c;
    } bard;
    
    bard thee,summersDay;
    
    if ( memcmp( &thee, &summersDay ) == 0 ) {
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Snafuist View Post
    I can't see any reason for not comparing the struct member for member, as in x.m1==y.m1, x.m2==y.m2 and so on. On a sidenote, it's certainly not possible to write a generic struct comparing function.
    Of course it is. You can construct a list of elements of an object, and write a generic function that compares two structures arbitrarily according to some generic rules. A structure like this would work:
    Code:
    typedef { VOID = 0, INT, STR, CHAR, CHARPTR, FLOAT, DOUBLE } EType; 
    typedef struct SElement
    {
       char *name;   // Not actually needed - just because the macro CAN DO THAT. 
       offset_t offs;
       enum EType type;
    } Element;
    
    typedef struct SExample
    {
        int   a;
        char *str1;
        char str2[40];
        char b;
    } Example;
    
    #define ELEM(structname, name, type)   { #name, offsetof(structname, name), type }
    
    Element ExampleDescr [] = 
    {
       ELEM(Example, a, INT),
       ELEM(Example, str1, CHARPTR),
       ELEM(Example, str2, STR),
       ELEM(Example, b, CHAR)
    };
    
    int CompareStructsGeneric(void *struct1, void *struct2, Element descr, size_t nElements)
    {
       for(i = 0; i < nElements; i++)
       {
           switch(descr[i].type)
           {
               case INT:
                    if (*(int *)((char*)struct1+descr[i].offset) > *(int *)((char*)struct2+descr[i].offset)
                       return 1;
                    else if (*(int *)((char*)struct1+descr[i].offset) < *(int *)((char*)struct2+descr[i].offset)
                       return -1;
                    break;   /* Equal, continue to next element ... */
              .... 
            }
        }
        return 0;
    }
    Obviously, we'll need to make suitable pointer arithmetics to figure out the rest of the functions.

    But you could certainly use this mechanism to compare completely arbitrary structures, as long as they are both the same type.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  12. #12
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Of course it is.
    No, it's not.

    Give me a complete implementation of a struct comparing function and I'll make up a struct which it can't compare. Think of typedef.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Snafuist View Post
    No, it's not.

    Give me a complete implementation of a struct comparing function and I'll make up a struct which it can't compare. Think of typedef.

    Greets,
    Philip
    Well, of course, if you have nested structures (or pointers to structures), you'd need to have a hierarchical structure to support that. Again, it's certainly POSSIBLE to do. Just a bit more complicated - we'd need to add at least one more field to the structure describing the struct and of course, more fields to the enum.

    I doubt that typedef will change anything in itself - it is just a way to alias one type to another name.

    If you don't believe me, please post a structure you think we can't deal with, and I'll see if I can't find a solution.

    Note that the above is simply enough to convey the architecture of a struct comparing function - it can (and probably will) be made MUCH more complex if you need to actually do this in the real world. But I'm still convinced it CAN be done.

    And if all else fails, we can always extend the structure describing each struct by adding a function-pointer that takes the pointer to the current element - that way, you can have "user" types that can be compared in any way the user wishes.

    Whether it is actually MEANINGFUL to do it is of course another matter altogether.

    And, before you say so, I would agree that structs containing unions can be quite tricky - since you'd have to know which variant of the possible members we should look at. Bitfields would also not work - but most people don't use bitfields very often anyways.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #14
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    I completely agree to most of what you say, it's true for native types and compound types. Your implementation will actually work fairly well on all real world examples I can think of right now. We just have a different opinion on the purpose of typedef:

    I doubt that typedef will change anything in itself - it is just a way to alias one type to another name.
    That's what #define is used for. The typedef keyword actually defines a new type, probably inventing new semantics.

    I'm free to do "typedef int foo" and constitute that all even values in the range of foo have the same meaning (say, "bar"), while all odd values in the range of foo have the same meaning as there integer counterpart.

    Now if I have two variables x and y of type foo where x==2 and y==4, then they shall compare equal. For your struct comparing function to return correct results, I need to modify the enum and the function definition. But then, it wasn't generic in the first place.


    I admit that this example is a bit artificial (ok, it's highly artificial), and as I said before, in real world situations your approach is perfectly fine. From a theoretical viewpoint however, it's not possible.

    I know I sound ..........y. Just forget about it, I greatly admire your knowledge and I'm certainly not trying to annoy you.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Snafuist View Post
    I completely agree to most of what you say, it's true for native types and compound types. Your implementation will actually work fairly well on all real world examples I can think of right now. We just have a different opinion on the purpose of typedef:



    That's what #define is used for. The typedef keyword actually defines a new type, probably inventing new semantics.

    I'm free to do "typedef int foo" and constitute that all even values in the range of foo have the same meaning (say, "bar"), while all odd values in the range of foo have the same meaning as there integer counterpart.
    Typedef on it's own will not achieve that - typedef is just a way to say "when I use type X, I want you (the compiler) to see that as <whatever>". In fact, if you use "typedef int foo", the compiler will quite happily pass int and foo types to functions that take foo and int types respectevily, with no restriction. foo is a type in its own right, but it has the same properties and behaviour as int. The only difference is that if you wish to change foo into some other type (long, long long, short, double or some struct), it can easily be done with just changing one typdef line, rather than trying to find all places where "int" is being used.

    To have all even numbers in a different range than odd numbers, you either need C++ classes (which is not available in C), or use some sort of macro/function to compare numbers of that type - but the compiler will not let you simply re-define the meaning of int by calling it foo instead.

    And no, I don't get that easily annoyed or anything - if you had come up with something that would NOT work, then I would have acknowledged you (you may still have thought of something I haven't - I have never actually WRITTEN a function that does what I described above - I have written other functions that do SIMILAR things, but usually on a restricted set of things).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  2. Comparing structures?
    By difficult.name in forum C Programming
    Replies: 2
    Last Post: 11-07-2004, 07:05 PM
  3. Structures & Comparing
    By Cyber Kitten in forum C Programming
    Replies: 1
    Last Post: 10-22-2001, 11:41 AM
  4. Comparing strings w/in structures
    By vehl in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2001, 10:59 AM
  5. Methods for Sorting Structures by Element...
    By Sebastiani in forum C Programming
    Replies: 9
    Last Post: 09-14-2001, 12:59 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21