CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8

Thread: sort vector of struct

  1. #1
    Join Date
    May 2018
    Posts
    103

    sort vector of struct

    I run this code for make exercises with STL but I got message "segmentation fault".
    If I reduce N value to 10, there is no problem.
    Suggestion please?



    Code:
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    struct app {
    	int max;
    	int dup;
    };
    
    bool mycmp(struct app a, struct app b) {
    	if (a.max >= b.max)
    		return true;
    	return false;
    }
    
    int main() {
    	int N;
    	N = 100;
    	vector <app> vapp(N);
    	for (int i=0; i<N; ++i) {
    		vapp[i].max = -1;
    		vapp[i].dup = 0;
    	}
    	sort(vapp.begin(), vapp.end(), mycmp );
    }
    Last edited by zio_mangrovia; December 13th, 2019 at 02:07 PM.

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,768

    Re: sort vector of struct

    The comparator is required to model a "less than" comparison, or what they call comparing for "strict weak ordering". What this means is that if A "less than" B is true, then B "less than" A must be false. This is satisfied by > as if A > B is true, then B > A is false, but is not satisfied by >= as if A >= B is true, B >= A could also be true since A could be equal to B.

  3. #3
    Join Date
    Feb 2017
    Posts
    567

    Re: sort vector of struct

    Also isn't it required that the comparator is presented to sort as a function object, and not just a plain function? If this is so it could be the cause of the segment fault even though I would expect the compiler to complain.

  4. #4
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,768

    Re: sort vector of struct

    No, I think ordinary functions are allowed as long as they take the two required parameters and return bool according to the strict weak ordering requirement. The advantage of a function object lies in being able to be initialised with and store state that might be useful. (Oh, and of course the useful lambda function syntax does result in a function object.)

    Looking at the function again though, arguably the parameters should be const references instead, although this app struct isn't particularly expensive to copy.

    EDIT:
    Yeah, the standard sounds slightly misleading because it does use the term "function object", but:
    Quote Originally Posted by C++11 Clause 20.8 Paragraph 1
    A function object type is an object type (3.9) that can be the type of the postfix-expression in a function call (5.2.2, 13.3.1.1). A function object is an object of a function object type. In the places where one would expect to pass a pointer to a function to an algorithmic template (Clause 25), the interface is specified to accept a function object. This not only makes algorithmic templates work with pointers to functions, but also enables them to work with arbitrary function objects.
    (I'd quote a newer version but I haven't gotten round to getting a copy yet and I loathe quoting from new draft versions as if they were the final standard, even if they likely are unchanged.)
    Last edited by laserlight; December 13th, 2019 at 02:41 PM.

  5. #5
    Join Date
    Feb 2017
    Posts
    567

    Re: sort vector of struct

    Quote Originally Posted by laserlight View Post
    No, I think ordinary functions are allowed
    Yes you're right, and I suppose the OP would've got a compiler error if they weren't allowed.

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,267

    Re: sort vector of struct

    From the code, I'm guessing that you were first a c programmer before starting to code in c++?

    When specifying arguments to a function, you don't need to specify struct for a struct - just the type name is fine in c++. Also, unless there is a good reason, in c++ arguments are usually passed by ref rather than by value (for performance reasons) - and if the value isn't (shouldn't) be changed in the function then they are also passed as const.

    As each element of the array is initialised to the same value in this test code, there is a useful function fill() which can do this. Also, the default values for the members of a struct can be initialised.

    Consider:

    Code:
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    struct app {
    	int max {-1};
    	int dup {0};
    };
    
    bool mycmp(const app& a,  const app& b) {
    	return a.max < b.max;
    }
    
    int main() {
    	constexpr size_t N {100};
    	vector<app> vapp(N);
    
    	fill(begin(vapp), end(vapp), app());
    	sort(begin(vapp), end(vapp), mycmp);
    }
    Note that rather than = being used for initialisation, {} is used. This is C++ universal initialization and can be used with most objects - not just numbers.

    constexpr means that the value is determined at compile time and not run-time.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.7.4)

  7. #7
    Join Date
    Feb 2017
    Posts
    567

    Re: sort vector of struct

    Quote Originally Posted by 2kaud View Post
    As each element of the array is initialised to the same value in this test code, there is a useful function fill() which can do this.
    I don't think the call to fill is strictly necessary since when the vapp vector is constructed it will be filled with N default constructed app structs whose members will be initialized to the specified values.

    On the other hand I don't think it's wrong to initialize vapp explicitly using say fill. Better safe than sorry.
    Last edited by wolle; December 15th, 2019 at 02:14 AM.

  8. #8
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,267

    Re: sort vector of struct

    Quote Originally Posted by wolle View Post
    I don't think the call to fill is strictly necessary since when the vapp vector is constructed it will be filled with N default constructed app structs whose members will be initialized to the specified values.
    Correct. My original code didn't have the struct default initialization - so the fill was required to replace the OP for loop. I then added the struct initialization and just changed the app construct in fill() - rather than removing the fill() statement which, as wolle says, is now redundant. . This gives:

    Code:
    #include <vector>
    using namespace std;
    
    struct app {
    	int max {-1};
    	int dup {0};
    };
    
    bool mycmp(const app& a,  const app& b) {
    	return a.max < b.max;
    }
    
    int main() {
    	constexpr size_t N {100};
    	vector<app> vapp(N);
    
    	sort(begin(vapp), end(vapp), mycmp);
    }
    Last edited by 2kaud; December 15th, 2019 at 07:05 AM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.7.4)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)