STL issues with sort()?

[Radius]

Hi,

I have a vector<MyStruct> and I'm trying to sort it. Basically I have a struct with two 32bit numbers that are in bit fields and I've overridden > < == and != and all they do is compare the bit fields to determine if the operator is true or not. I'd post it but it's useless and I know it works, trust me.

I have also overridden the = operator and all it does is a quickie memcpy() because as I say, there are just two 32bit numbers, no pointers in the struct or anything fancy.

Anyhow, this all works perfectly, until I have more than 261 elements in my vector! When I have more than 261 elements, the < operator fails and tells me the one local var in my function isn't defined and my two 32bit values are completely unintelligent.

The one local variable I have is a bool result; which just tells me if it's truly < the element it's being compared to and it's always initialized before the calculations take place.

I know all the elements are good because I've gone so far as looking at each one now manually. It only complains when it reaches the end of the function where the return result; sits.

In the STL source code, it fails on a line that reads "if (*_Last < *_Mid)" and that in turn is called from "_Med3(_Last - 2 * _Step, _Last - _Step, _Last);" in the <alogrithm> file. That is probably totally useless info though.

I'll post code for the struct if anyone thinks it's really necessary. I invoke it with "sort(sorted,begin(), sorted.end()); so nothing special there I think.

Any suggestions?

[JVene]

Well, since STL sort has performed well, in much larger vectors, for many circumstances, I'd say we can't provide any feedback without something to actually try on your behalf.

However, as a guess, I'd say that you've described what could be memory corruption symptoms, and that leads me to the memcpy or some other features of data management that might be 'going wrong' somewhere.

[Radius]

Ya, I've been thinking about that. I don't use this across threads or anything, but maybe something totally unrelated has ripped into the memory, I am putting some bounds checking software on here and seeing what that points to.

Anyways, here's the struct I use:

typedef struct tagSORTED_LIST
{
   RCP_JOB_INFO::point_info pi;

   unsigned long job_idx; // Only valid for sorting a list of RCP_JOB_INFOs.

   inline tagSORTED_LIST &operator = (tagSORTED_LIST _v)
   {
      if ( this != &_v )
         memcpy(this, &_v, sizeof(tagSORTED_LIST));

      return *this;
   }

   inline bool operator < (tagSORTED_LIST _v)
   {
      return (_v > *this);
   }

   inline bool operator > (tagSORTED_LIST _v)
   {
      bool result;

      result = false;

      if ( (pi.has_sub == 0) && (_v.pi.has_sub == 0) )
      {
         if ( pi.main_adr == _v.pi.main_adr )
         {
            if ( pi.num > _v.pi.num )
               result = true;
            else
               result = false;
         }
         else if ( pi.main_adr > _v.pi.main_adr )
            result = true;
         else
            result = false;
      }
      else if ( (pi.has_sub == 0) && (_v.pi.has_sub == 1) )
      {
         if ( pi.main_adr > _v.pi.main_adr )
            result = true;
         else
            result = false;
      }
      else if ( (pi.has_sub == 1) && (_v.pi.has_sub == 1) )
      {
         if ( pi.main_adr == _v.pi.main_adr )
         {
            if ( pi.sub_a == _v.pi.sub_a )
            {
               if ( pi.sub_adr > _v.pi.sub_adr )
                  result = true;
               else if ( pi.sub_adr == _v.pi.sub_adr )
               {
                  if ( pi.num > _v.pi.num )
                     result = true;
                  else
                     result = false;
               }
               else
                  result = false;
            }
            else if ( pi.sub_a == 0 && _v.pi.sub_a == 1 )
               result = true;
            else // if ( pi.sub_a == 1 && _v.pi.sub_a == 0 )
               result = false;
         }
         else if ( pi.main_adr > _v.pi.main_adr )
            result = true;
      }
      else // pi.has_sub == 1 && _v.pi.has_sub == 0
      {
         if ( pi.main_adr >= _v.pi.main_adr )
            result = true;
         else
            result = false;
      }

      return result;
   }

   inline bool operator == (tagSORTED_LIST)
   {
      return false;
   }

   inline bool operator != (tagSORTED_LIST)
   {
      return true;
   }
} SORTED_LIST;

RCP_JOB_INFO:oint_info pi; is just another 32bit number with nit fields, no thing strange or unusual about it.

[JVene]

While I'm not of the opinion this is the problem, this is suspect:

 inline tagSORTED_LIST &operator = (tagSORTED_LIST _v)
   {
      if ( this != &_v )
         memcpy(this, &_v, sizeof(tagSORTED_LIST));

      return *this;
   }

I'd suggest the parameter to the function should be a reference, because I think a copy is being made which would obviate any meaning to the test for 'this != &_v' - if _v is a copy made on the stack for this call, this would never fire, even if the source parameter in the calling code were 'this'.

Although you state that pi is another 32bit value, the various uses suggest it's either a union or something more complex than a 32bit value.

However, if it IS just a 32bit value, I think memcpy is a bit much for use.

The overhead of the function call (and the safety issues with memcpy in general) would probably NOT be faster than:

job_idx = _v.job_idx;
pi          = _v.pi;

This turns out to be two quick moves, whereas a memcpy is a function call, complete with preamble, cleanup, return....much longer, actually - and perhaps related to your problem.


You might also consider references for your other comparison operator overloads (probably const references at that) - they are similarly making copies, which might not be your best performance choice.


I know more than a couple here would point out that _v treads on reserved territory (underscores are reserved for compiler implementation work, supposedly taboo for application code). That, however, is likely not your problem.


Also, without understanding RCP_JOB_INFO:oint_info, I can't help review, so I must ask: are you certain the logic here results in a consistent > evaluation? I see your < overload simply resorts to a > overload, which is logically questionable - any value that could cause BOTH to be true is irrational.

However, since sorting doesn't require both, that might not be the problem. Is it possible, instead, that the results of the > overload are not consistent regarding order? That can cause curious behavioral problems with recursive sorting algorithms, and it's about the only other potential point I can see (with this viewpoint) where you have an opportunity to contribute to a bug there.

[Paul McKenzie]

Ya, I've been thinking about that. I don't use this across threads or anything, but maybe something totally unrelated has ripped into the memory, I am putting some bounds checking software on here and seeing what that points to.

1) Since this is C++, the use of "typedef struct" is no longer necessary. The "typedef struct" is only necessary for 'C' programs.

struct SortedList
{
  ///...
};

2) Looking at your member variables, there is no need for a user-defined assignment operator. If the member variables of your struct are safely copyable by themselves, adding an unnecessary user-defined assignment operator will just lead to bugs.

Speaking of that, you didn't code it correctly, and you are missing a user-defined copy constructor to match the assignment operator. Recommendations: Get rid of the user-defined assignment operator, unless you can show us that the members are not safely copyable.

3) This is incorrect

   inline tagSORTED_LIST &operator = (tagSORTED_LIST _v)
   {
      if ( this != &_v )
         memcpy(this, &_v, sizeof(tagSORTED_LIST));

      return *this;
   }

Since your struct is non-POD, using memcpy to copy from one instance to another is undefined behaviour. Never use raw C functions to copy non-POD types. Again, get rid of this altogether, and let the C++ generate the standard assignment operator.

4) When using std::sort() it requires that the function used to see if a > b be of a strict weak ordering. This means that if a > b, then b < a for all pairs of values. In other words, if your code determines that a > b for values a and b, and for some unforseen reason determines that b > a when given the same pair of values in another iteration of the sort, then the sort will not work.

This can be caused by a badly coded sort predicate, or a sort predicate that just won't uniquely determine the correct order of a and b (even though the coder believes it will always correctly and uniquely determines the order of two values). It is hard to tell if your function adheres to this.

5) The std::sort() predicate must check for a < b and return true (for descending sort), or if a > b and return true (for ascending sort). Otherwise return false. Do not return true if a == b. This violates the strict weak ordering rule.

In general, it looks like a C programmers valiant attempt at C++. The flaws I pointed out earlier should be addressed, and then try the sort again.

Regards,

Paul McKenzie

[grahamr (work)]

Also don't assume that sort() will be the fastest sort. Also try partial_sort().

In this thread, I found that partial_sort can run faster than sort.

Thanks, G.