STL binary search - C2784 in debug only?  
Author Message
TechCzech





PostPosted: Visual C++ Language, STL binary search - C2784 in debug only? Top

I'm porting a Visual C++ 6 project to Visual Studio 2005 and ran into something I don't understand with STL. Below code compiled and worked for debug and release modes in VC6, compiles and works in release mode for VS2005, but won't compile in debug mode under VS2005. The call to lower_bound isn't identifying the second operator < for some reason.

-- Market.h----------

#ifndef __MARKET_H__
#define __MARKET_H__

#include <vector>
#include <algorithm>

class CMarket
{
  CMarket () {};
 ~CMarket () {};

  // Individual quote
  class Quote
  {
  public :
    Quote() {};
    ~Quote() {};

    // For STL sort by date
    inline bool operator < (const Quote &a_quote) const
    {
      return m_DateOrdinal < a_quote.m_DateOrdinal;
    }

    // For STL binary search by date
    inline bool operator < (const unsigned short a_DateOrdinal) const
    {
      return m_DateOrdinal < a_DateOrdinal;
    }

  public:
    // Ordinal into a vector of actual market dates
    unsigned short m_DateOrdinal;
    // Security price
    double m_Price;
  };

  // Quote series
  std::vector < Quote > m_vecQuotes;

  // Binary search
  int GetQuoteIndex (unsigned short a_DateOrdinal);
};
#endif

-- Market.cpp ----------

#include "Market.h"

int CMarket::GetQuoteIndex(unsigned short a_DateOrdinal)
{
  // Binary search through vector for specific date ordinal
  std::vector < Quote > ::const_iterator itQuote;
  itQuote = std::lower_bound(m_vecQuotes.begin(), m_vecQuotes.end(), a_DateOrdinal);
  return (int)(itQuote - m_vecQuotes.begin());
}


Visual C++2  
 
 
cgraus





PostPosted: Visual C++ Language, STL binary search - C2784 in debug only? Top

// return (int)(itQuote - m_vecQuotes.begin());

Are you sure this line is not the problem VC6 had a TERRIBLE STL implimentation. One problem was that it allowed you to treat an iterator as a pointer. That is not allowed. It looks to me like you're using pointer arithmetic here, which you can't do on an iterator, not since VC2002.



 
 
Holger Grund





PostPosted: Visual C++ Language, STL binary search - C2784 in debug only? Top

Your code is perfectly valid. There are cases where the debug functionality of the Dinkumware STL implementation slightly changes the standard requirements for a more proactive approach identifying potential issues in your code.

One of these are the checks for strict weak ordering. Many STL algorithms require a strict weak ordering on their predicate or operator<. The debugging version does a check that a<b implies !(b<a).

And that's where the error comes from. You do not have an operator< overload which handles (unsigned short, Quote).

Try adding a namespace scope or friend member operator<(unsigned short,const Quote&).E.g:

friend bool operator<( unsigned short l, const Quote& r)
{ return l < r.m_aDateOriginal; }

Of course, you could alternatively disable debugging extensions but I think these are extremely useful.

-hg


 
 
TechCzech





PostPosted: Visual C++ Language, STL binary search - C2784 in debug only? Top

cgraus - That line is not the problem, it's definitely the call to lower_bound. Iterators have an "operator -" for just what I'm doing.

Holger - Dead on, I added what you suggested and the debug version compiles and runs now. That seems a bit touchy, but I can go read about it at my leisure now that I know how to dance around it. Thank you.


 
 
Holger Grund





PostPosted: Visual C++ Language, STL binary search - C2784 in debug only? Top

FWIW, not all iterator types have an operator-, but random access iterators have (which is what you have here).

I'm not sure the error you got is actually by design. The strict weak ordering check is probably supposed to kick in for identical types only. E.g. for something like

#include <algorithm>
#include <functional>

int main()
{
int ints[] = { 1, 1 };
std::sort( ints, 1[&ints], std::not2(std::less<int>()) );
}

not2(less) is not a strict weak ordering. I've seen real-world code**** in infinite loops for something like this.

I tend to believe that what you saw is not expected. But then, I'm not certain that there are standard requirements for what you do, because LessThanComparable assumes both arguments to be of type T (unsigned short in your case).

-hg


 
 
aek





PostPosted: Visual C++ Language, STL binary search - C2784 in debug only? Top

I have a related problem. However, I'm using a BinaryPredicate to perform the comparison. So, in the context of the original example, I would have something like this

struct KeyCmp:public binary_function < Quote, unsigned short, bool >
{

result_type operator() ( const first_argument_type & x,
const second_argument_type & y) const
{
return key_compare() (x, y.first);
}
};

In our case, we wanted a map that could cross DLL-boundaries so we've implemented a map template that internally uses a list of key-value pairs as the container. This implementation has been around for at least six years and has served its purpose quite well until we tried to compile it with Visual Studio 2005. I didn't want to post the entire implementation because it is quite lengthy. I did include an abbreviated snippet of the key code pieces below. The binary predicates that we've implemented to be used by the algorithms such as upper_bound and lower_bound are causing compiler problems because the upper_bound and lower_bound function templates are assuming that the parameters to a binary predicate are interchangeable. I''ve been trying to track down whether this assumption is valid within the context of the STL specification.

Within our map template, let's call it MyMapT<K, V> , we've got the following

typedef K key_type;

typedef pair<K, V> value_type;

iterator MyMapT::upper_bound(const K & key)
{
return std::upper_bound(begin(), end(), key, KeyCmp());
}

iterator MyMapT::lower_bound(const K & key)
{
return std::lower_bound(begin(), end(), key, KeyCmp2());
}

struct KeyCmp:public binary_function < key_type, value_type, bool >
{
result_type
operator() ( const first_argument_type & x,
const second_argument_type & y) const
{
return key_compare() (x, y.first);
}
};

struct KeyCmp2:public binary_function < value_type, key_type, bool >
{
result_type operator() (const first_argument_type & x,
const second_argument_type & y) const
{
return key_compare() (x.first, y);
}
};

BTW, I did try overloading the operator() but that didn't work, i.e.,

struct KeyCmp:public binary_function < key_type, value_type, bool >
{
result_type
operator() ( const first_argument_type & x,
const second_argument_type & y) const
{
return key_compare() (x, y.first);
}

result_type operator() ( const second_argument_type & x,
const first_argument_type & y) const
{
return key_compare() (x.first, y);
}

};