mardi 25 février 2020

C++ map: operator[] with custom class does not work

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?

Aucun commentaire:

Enregistrer un commentaire