C++ map: operator[] with custom class does not work (always returns 0)

Question

I'm trying to implement a MinHeap, where objects on the heap are WorkerNodes. My method returns map which is intended to allow client code to determine which WorkerNode indices have changed from the minHeapify operation.

std::cout << "heapifying " << heap_[root] << "from index " << root << "\n.";
    int size = heap_.size();
    bool swapped = false;
    std::map<WorkerNode, int> tracker;

    for (int i = root; i >= 0; --i)
    {
        while (true)
        {
            int leftChild = 2 * i + 1;
            if (leftChild < 0 || leftChild >= size)
                break;
            int rightChild = 2 * i + 2;
            int smallerChild = leftChild;
            if (rightChild < size && heap_[rightChild] < heap_[leftChild])
                smallerChild = rightChild;

            if (heap_[i] <= heap_[smallerChild])
                break;

            // index tracking

            tracker[heap_[i]] = smallerChild;
            tracker[heap_[smallerChild]] = i;

            std::cout << "**\n\n"
                      << heap_[i] << " has moved to " << smallerChild;
            std::cout << ", and " << heap_[smallerChild] << " has moved to " << i << "\n**";

            // swap heap_[i] and heap_[smallerChild]
            swapped = true;
            T temp = heap_[i];
            heap_[i] = heap_[smallerChild];
            heap_[smallerChild] = temp;
            i = smallerChild;
        }
    }
    if (!swapped) // avoids bad access
    {
        tracker[heap_[root]] = root;

        for (auto &itm : tracker)
        {
            std::cout << "**\n"
                      << itm.first << " is at " << itm.second << "!!!\n";
        }
        std::cout << "**\nno swap; " << heap_[root] << " stays at " << tracker[heap_[root]] << "\n**";
    }

    return tracker;

Here is the ouput that I am seeing:

heapifying W1-1from index 0
.**
W1-1 is at 0!!!
**
no swap; W1-1 stays at 0
**heapifying W2-2from index 1
.**
W2-2 is at 1!!!
**
no swap; W2-2 stays at 0
**heapifying W3-3from index 2
.**
W3-3 is at 2!!!
**
no swap; W3-3 stays at 0
**heapifying W0-3from index 3
.**
W0-3 is at 3!!!
**
no swap; W0-3 stays at 0

This issue was brought to my attention when running test cases, where I am doing something like this:

WorkerNode key("W4", 2);
    // after two decrements, its index should still be 3.
    BOOST_TEST(tracker[key] == 3);

And getting output like this:

error: in "minheap_test_suite/case6": check tracker[key] == 3 has failed [0 != 3]

So from what I can tell, The pre-exit for loop in my minHeapify method confirms that the proper data is being inserted into the map, but when I try to access this data using the [] operator, it is unable to locate the WorkerNode-index pairing I just inserted, returning 0 as the value it has probably just default-constructed.

When I tried using find() instead of [] just now like so:

tracker[heap_[root]] = root;

        for (auto &itm : tracker)
        {
            std::cout << "**\n"
                      << itm.first << " is at " << itm.second << "!!!\n";
        }
        int index = tracker.find(heap_[root])->second;
        std::cout << "**\nno swap; " << heap_[root] << " stays at " << index << "\n**";

I get the following output:

heapifying W1-1from index 0
.**
W1-1 is at 0!!!
**
no swap; W1-1 stays at -1354735968
**heapifying W2-2from index 1
.**
W2-2 is at 1!!!
**
no swap; W2-2 stays at 3233540

Here is my WorkerNode.h file, comments removed:

#include <ostream>
#include <string>

struct WorkerNode
{
    unsigned numJobs_;     ///< worker job count.
    std::string workerID_; ///< worker ID string.

    explicit WorkerNode() : numJobs_(0), workerID_("") {}

    WorkerNode(std::string id) : numJobs_(0), workerID_(id) {}

    WorkerNode(std::string id, unsigned jobs) : numJobs_(jobs), workerID_(id) {}

    WorkerNode(WorkerNode &&other) : numJobs_(other.numJobs_), workerID_(other.workerID_)
    {
        other.numJobs_ = 0;
        other.workerID_ = "";
    }

    WorkerNode(const WorkerNode &other) : numJobs_(other.numJobs_), workerID_(other.workerID_) {}

    WorkerNode &operator=(const WorkerNode &other)
    {
        if (this == &other)
            return *this;
        this->numJobs_ = other.numJobs_;
        this->workerID_ = other.workerID_;
        return *this;
    }

    WorkerNode &operator=(WorkerNode &&other)
    {
        if (this == &other)
            return *this;
        this->numJobs_ = other.numJobs_;
        this->workerID_ = other.workerID_;
        other.numJobs_ = 0;
        other.workerID_ = "";
        return *this;
    }

    ~WorkerNode() {}

    bool operator<(const WorkerNode &rhs) const
    {
        return *this <= rhs;
    }

    bool operator<=(const WorkerNode &rhs) const
    {
        if (numJobs_ < rhs.numJobs_)
            return true;
        else if (rhs.numJobs_ < numJobs_)
            return false;
        else
        {
            return workerID_.compare(rhs.workerID_) <= 0 ? true : false;
        }
    }

    bool operator==(const WorkerNode &rhs) const
    {
        if (numJobs_ == rhs.numJobs_ && workerID_ == rhs.workerID_)
            return true;
        else
        {
            return false;
        }
    }

    void operator--()
    {
        if (numJobs_ > 0)
            numJobs_ -= 1;
    }

    void operator++()
    {
        numJobs_ += 1;
    }

    friend std::ostream &operator<<(std::ostream &out, const WorkerNode &n)
    {
        out << n.workerID_ << "-" << n.numJobs_;
        return out;
    }
};

WTF am I doing wrong here?

EDIT:

Okay folks, here is my reprex. My apologies for the prior nonsensical code bloat. This example 100% reproduces my current confusion. Let's get to the bottom of this thing.

Key.h:

// user-defined struct, intended to be used as a map key.

#include <string>
#include <ostream>

struct Key
{
    std::string id;
    unsigned jobs;

    Key(std::string id_ = "", unsigned jobs_ = 0) : id(id_), jobs(jobs_) {}

    bool operator<(const Key &rhs) const
    {
        if (jobs < rhs.jobs)
            return true;
        else if (rhs.jobs < jobs)
            return false;
        else
            return id.compare(rhs.id) <= 0 ? true : false;
    }

    bool operator<=(const Key &rhs) const
    {
        if (jobs < rhs.jobs)
            return true;
        else if (rhs.jobs < jobs)
            return false;
        else
            return id.compare(rhs.id) <= 0 ? true : false;
    }

    friend std::ostream &operator<<(std::ostream &o, const Key &key)
    {
        o << key.id << "-" << key.jobs;
        return o;
    }
};

MinHeap.h:

#include <vector>
#include <map>

#include "Key.h"

struct MinHeap
{
    std::vector<Key> heap;

    std::map<Key, int> minHeapify(int root)
    {
        std::map<Key, int> tracker;
        for (int i = 0; i < heap.size(); ++i)
            tracker[heap[i]] = i;
        return tracker;
    }

    std::map<Key, int> insert(const Key &key)
    {
        heap.push_back(key);
        return minHeapify(heap.size() - 1);
    }
};

main.cpp:

#include <iostream>
#include "MinHeap.h"

int main()
{
    MinHeap heap;
    std::map<Key, int> tracker;
    for (int i = 0; i < 3; ++i)
    {
        Key key("Key" + std::to_string(i), i);
        tracker = heap.insert(key);

        //checking tracker contents using auto for loop
        std::cout << "tracker keyindex contents: ";
        for (auto &itm : tracker)
        {
            std::cout << itm.first << " ::: " << itm.second << ", ";
        }
        std::cout << "\n\n";

        //checking key and tracker[key], which should reflect
        //each other as well as the operation done in minHeapify.

        /// *** what tracker[key] is actually printing ***
        std::cout << "tracker[key] = " << tracker[key] << std::endl;
        /// **********************************************

        /// *** what tracker[key] is expected to be printing ***
        std::cout << "actual tracker key index: " << key.jobs << std::endl;
        /// ****************************************************
    }

    return 0;
}

Run main.cpp yourself. The big problem here is the last two print statements. The prior for loop confirms that the expected Keys are indeed being returned by the minHeapify(int) operation and have the expected index.

However, attempts to subindex using [Key] into map<Key,int> does not return the expected index.

Hopefully, I have illustrated the confusion a little clearer.

Thanks in advance for the help.

Cheers

Answer 1

The problem, I think, is already identified in comments by Remy Lebeau.

Your implementation of Key::operator< does not meet the requirements of strictly weak ordering, as required of a type to be usable as the key in a std::map.

You need a minor change in the implementation.

bool operator<(const Key &rhs) const
{
    if (jobs < rhs.jobs)
        return true;
    else if (rhs.jobs < jobs)
        return false;
    else
        return id.compare(rhs.id) <  0 ? true : false; // Needs to be <, not <=
}

You can simplify the function using std::tie

bool operator<(const Key &rhs) const
{
   std::tie(jobs, id) < std::tie(rhs.jobs, rhs.id);
}

Answer 2

This is what a minimal reproducible example looks like:

#include <iostream>
#include <map>

struct Key {
  std::string id;
  unsigned    jobs;
  bool operator<(const Key & rhs) const {
    if (jobs < rhs.jobs)
      return true;
    else if (rhs.jobs < jobs)
      return false;
    else
      return id.compare(rhs.id) <= 0 ? true : false;
  }
};

int main() {
  std::map<Key, int> m;
  m[Key { "Key0", 0 }] = 0;
  m[Key { "Key1", 1 }] = 1;
  m[Key { "Key2", 2 }] = 2;
  std::cout << m[Key { "Key0", 0 }] << std::endl;
  std::cout << m[Key { "Key1", 1 }] << std::endl;
  std::cout << m[Key { "Key2", 2 }] << std::endl;
  return 0;
}

Is this easier to grasp? Is this easier for people to help you with?

Can you yourself find the problem now?