The std::less<int>()(int, int) might get a wrong answer

user_14123050 0
Viewed 81

I am learning the SplayTree. When I write my code, I get a mistake as what the title says. This mistake appears at my "splay" mathod:

void splay(const KeyType& arg_key, Node*& tree)

this line:

if (key_less(arg_key, key(tree)))

I tried to output some message about this line and found it always get a 'true' answer

code: 
std::cerr << "arg_key == " << arg_key << "; key(tree) == " << key(tree) << std::endl;
std::cerr << "key_less(arg_key, key(tree)) == " << key_less(arg_key, key(tree)) << std::endl;
std::cerr << "key_less(key(tree), arg_key) == " << key_less(key(tree), arg_key) << std::endl;
std::cerr << "typename of key_less == " << typeid(key_less).name() << std::endl;

output:

arg_key == 2; key(tree) == 8
key_less(arg_key, key(tree)) == 0
key_less(key(tree), arg_key) == 1
typename of key_less == struct std::less<int>

The splay tree template is like that

template <typename KeyType, typename ValueType, typename KeyOfValue, typename Comparator = std::less<KeyType>> class SplayTree

I define a splay tree as that

struct GetKeyFromValue
{
    int operator()(int value)
    {
        return value;
    }
};
SplayTree<int, int, GetKeyFromValue, std::less<int>> tree;

when I change the last template argument to

    struct Comparator
    {
        bool operator()(int lhs, int rhs)
        {
            return lhs < rhs;
        }
    };
    SplayTree<int, int, GetKeyFromValue, Comparator> tree;

It can get the right answer:

arg_key == 2; key(tree) == 8
key_less(arg_key, key(tree)) == 1
key_less(key(tree), arg_key) == 0
typename of key_less == struct `int __cdecl main(void)'::`2'::Comparator

Is it a bug?

thanks very much for watching my problem.

I am really looking forward to your help.

P.S. My platform is Visual Studio 2019 16.7.1 on Windows10 1909.

stl c++
1 Answers

Thanks to @Peter!! As what you mentioned, the problem happens in key(tree). the definition of it is

static const KeyType& key(Node* node_ptr) { return KeyOfValue()(node_ptr->value); }

in this case, the KeyOfValue is a class which i write it carelessly:

struct GetKeyFromValue
    {
        int operator()(int value)
        {
            return value;
        }
    };

after i change it to

struct GetKeyFromValue
    {
        const int& operator()(const int& value)
        {
            return value;
        }
    };

everything is ok now. I think this problem might be the key(tree) returned a const int& reference to a temporary value that GetKeyFromValue::operator()(int) returned?

Thank you to everyone who can read my question and don't hesitate to enlighten me.

user_141230500
Related