0

I had an implementation of a cache which was defined as so;

std::vector<TEntryPair>    m_listEntries;

with TEntryPair being defined as;

typedef std::pair<std::string, FILETIME> TEntryPair;

When inserting a new record into the cache I use std::lower_bound to find the correct place in the cache for an insertion sort as follows;

void AddCacheEntry(std::string const& strResourceName, FILETIME const& fTime)
{
    auto it = std::lower_bound(std::begin(m_listEntries),
                               std::end(m_listEntries),
                               strName);

    m_listEntries.insert(it, std::make_pair(strName, fTime));
}

New entries are insertion sorted based on the std::string parameter, the second value is basically metadata.

I have the following operators defined for std::lower_bound to use when attempting to insert a new record;

bool operator < (std::string const& str, TEntryPair const& rhs)
{
    return str < rhs.first;
}
bool operator < (TEntryPair const& lhs, std::string const& str)
{
    return lhs.first < str;
}

Now this all works fine until I had to change the definition of TEntryPair to the following;

std::pair<std::string, double>

Can somebody explain why the operators I have defined are unable to be used when using std::pair<std::string, double> as opposed to std::pair<std::string, FILETIME>?

The compiler gives the following errors;

Error   9   error C2676: binary '<' : 'std::pair<_Ty1,_Ty2>' does not define this operator or a conversion to a type acceptable to the predefined operator  c:\program files (x86)\microsoft visual studio 11.0\vc\include\algorithm    2736
Error   3   error C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const _Elem *' from 'std::pair<_Ty1,_Ty2>' c:\program files (x86)\microsoft visual studio 11.0\vc\include\algorithm    2736
Error   7   error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::pair<_Ty1,_Ty2>'    c:\program files (x86)\microsoft visual studio 11.0\vc\include\algorithm    2736
Error   2   error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'std::pair<_Ty1,_Ty2>'   c:\program files (x86)\microsoft visual studio 11.0\vc\include\algorithm    2736
Error   4   error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'std::pair<_Ty1,_Ty2>' c:\program files (x86)\microsoft visual studio 11.0\vc\include\algorithm    2736
Error   5   error C2784: 'bool std::operator <(const std::move_iterator<_RanIt> &,const std::move_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::move_iterator<_RanIt> &' from 'std::pair<_Ty1,_Ty2>'   c:\program files (x86)\microsoft visual studio 11.0\vc\include\algorithm    2736
Error   8   error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'const std::string' c:\program files (x86)\microsoft visual studio 11.0\vc\include\algorithm    2736
Error   6   error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::pair<_Ty1,_Ty2>'  c:\program files (x86)\microsoft visual studio 11.0\vc\include\algorithm    2736
Error   1   error C2784: 'bool std::operator <(const std::vector<_Ty,_Alloc> &,const std::vector<_Ty,_Alloc> &)' : could not deduce template argument for 'const std::vector<_Ty,_Alloc> &' from 'std::pair<_Ty1,_Ty2>' c:\program files (x86)\microsoft visual studio 11.0\vc\include\algorithm    2736

As an aside, I can define the following and compile/run the code without any errors;

struct STemp
{
    double m_Value;
}

typedef std::pair<std::string, STemp> TEntryPair;

It seems it is just "basic" types that have a problem?

Ralara
  • 559
  • 4
  • 19
  • 1
    Did you also change `AddCacheEntry` to have a second parameter of type double? – zennehoy Nov 25 '13 at 16:52
  • @zennehoy yes I had updated the definition. – Ralara Nov 25 '13 at 16:56
  • Doesn't std::pair deduce an `operator <` from its "members" automatically if both of them have an `operator <` defined? Like it is the case with buildin types. – Jonas Bötel Nov 25 '13 at 17:00
  • Addendum: In that case you could use a comparator as 4th parameter of `lowerBound` instead of defining another `operator <`. It would actually make more sense too. – Jonas Bötel Nov 25 '13 at 17:07
  • Related: http://stackoverflow.com/questions/16544974/overloading-istream-iterator-cannot-bind-lvalue-to-stdbasic-istreamchar http://stackoverflow.com/questions/4447827/why-does-ostream-iterator-not-work-as-expected – dyp Nov 25 '13 at 17:59
  • @Ralara On StackOverflow, it's very uncommon to mark solved questions in the title. The UI already indicates (and StackOverflow knows) when you have *accepted* an answer. – dyp Nov 26 '13 at 10:38
  • @DyP apologies :) changed it back now. – Ralara Nov 26 '13 at 10:41

1 Answers1

3

The culprit appears to be c++ name resolution (specifically, argument dependent lookup) combined with the predefined operator< in the standard library.

If TEntryPair is located entirely in the standard library, the operator< in your top-level namespace will not be found (there's no argument to operator< outside of namespace std, so only namespace std will be considered for argument dependent lookup).

Although the standard explicitly states that it is not allowed to overload functions in namespace std, the only solution to the problem that I have been able to find is to put the operator< in namespace std, since you are calling operator< from within namespace std, with arguments that all belong to namespace std.

For a standard-conforming solution, you will probably need to define your own class instead of using std::pair.

#include <vector>
#include <algorithm>
#include <string>

typedef double MyType;

struct TEntryPair {
    std::string first;
    MyType second;
};

bool operator < (std::string const& str, TEntryPair const& rhs)
{
    return str < rhs.first;
}
bool operator < (TEntryPair const& lhs, std::string const& str)
{
    return lhs.first < str;
}

std::vector<TEntryPair>    m_listEntries;

void AddCacheEntry(std::string const& strResourceName, MyType fTime)
{
    auto it = std::lower_bound(std::begin(m_listEntries),
                               std::end(m_listEntries),
                               strResourceName);
}

int main() { }
zennehoy
  • 6,405
  • 28
  • 55
  • Correct answer, bad solution *"To fix the problem, put the operator< in namespace std:"*. Though shall not put overloads in namespace `std`, [namespace.std]/1. (Well at least not if it's not *explicitly* allowed.) – dyp Nov 25 '13 at 17:54
  • @DyP: Added a statement to that effect, but I haven't been able to find a different solution to the problem. Deficiency in the standard library? Do you have a suggestion on how to fix it? – zennehoy Nov 26 '13 at 08:36
  • Although that works it isn't really an ideal solution as @DyP mentioned. Using suggestions from some of the linked questions above I've managed to get some form of solution - I've added it as an edit to the original question. Although it just seems a little....inelegant....to me. – Ralara Nov 26 '13 at 08:58
  • Ah! I hadn't seen you're edit as I had been editing my original post. You're solution is much cleaner! I added a constructor to the TEntryPair struct so that I could perform the insert as follows; m_listEntries.insert(it, TEntryPair(strName, 0.1)); Is that the cleanest way of doing it? Or is there a way of using the new c++11 initializer lists? – Ralara Nov 26 '13 at 09:23
  • 1
    @Ralara Yes, that is fine. If using c++11, you could also use `m_listEntries.insert(it, {strName, 0.1})`, even without explicitly defining a constructor. – zennehoy Nov 26 '13 at 09:56
  • I think it's indeed the best solution to use a user-defined type, allowing the use of ADL for `operator<`. Another solution is to pass a comparator, e.g. a lambda. E.g. `lower_bound(begin(m_listEntries), end(m_listEntries), strResourceName, [](TEntryPair const& lhs, string const& rhs) { return lhs < rhs; });` Obviously, using unqualified lookup, it depends on the context if it's possible to use that lambda. Alternatively use `::operator<(lhs, rhs)`. – dyp Nov 26 '13 at 10:33