7

Can anybody explain this behavior in context of STL sort algorithm? If operator < is not defined const it gives error,

error: passing ‘const B’ as ‘this’ argument of ‘bool B::operator<(const B&)’ discards qualifiers [-fpermissive] while (__pivot < *__last)

Is sort algo lhs const object or sort is const method?

class B
{
 public:
    ...
    bool operator < (const B& b) const       // why const required here?
    {
        return (m_i < b.m_i);
    } 
    ...

 private:
    int m_i;
    int m_j;
};

int main()
{
  vector<B> Bvec2 {B(5), B(3), B(30), B(20), B(8)};
  std::sort(Bvec2.begin(), Bvec2.end());
  ...
}
deepdive
  • 9,720
  • 3
  • 30
  • 38
  • 7
    Because comparing two objects should not change either one of them. – juanchopanza May 29 '14 at 06:23
  • @juanchopanza Agreed but my question is what `sort` is doing internally to force this? – deepdive May 29 '14 at 06:25
  • 1
    It could be as simple as calling a function that takes `const` references to the vector's elements. I don't think this is mandated by the standard, but it makes sense. – juanchopanza May 29 '14 at 06:28
  • while it is easy to imagine a sort implementation which allowed the comparison operator to not be _declared_ const, how could any comparison-based sort operation provide any guarantees if it were not logically const? I'm thinking this might technically be an bug in the implementation though, since I've seen many places in the C++ standard where they talk about operations being logically const (as opposed to syntactically) – Bwmat May 29 '14 at 06:30

2 Answers2

7

Marking the function as const promises that it will not change the object. So it can be used on const objects.

The STL almost certainly takes the arguments as const, because that is the smart thing to do.

It shouldn't hurt you to define operator< as const because I cannot imagine having a less-than operator that changes the object. That would just be silly.

If you want to know exactly where here is some code copied out of libstdc++ bits/stl_algo.h on a Fedora 20 machine:

  /// This is a helper function...
  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
    _RandomAccessIterator
    __unguarded_partition(_RandomAccessIterator __first,
                          _RandomAccessIterator __last,
                          const _Tp& __pivot, _Compare __comp)

const _Tp& __pivot, right there.

Zan Lynx
  • 53,022
  • 10
  • 79
  • 131
4

The standard is a little unclear on this, but [alg.sorting] gives two hints as to why this failure to compile might be standard-conforming behaviour. The first is [alg.sorting]/2:

... It is assumed that comp will not apply any non-constant function through the dereferenced iterator.

Next, we are told that when no comparator is supplied [alg.sorting]/3:

... comp(*i, *j) != false defaults to *i < *j != false

since in your case, comp defaults to *i < *j != false, and this applies a non-const function to the dereferenced iterators. This invalidates the assumption given in [alg.sorting]/2, and so your code has undefined behavior. It is legal for code with undefined behavior to not compile.

Mankarse
  • 39,818
  • 11
  • 97
  • 141