C++ 映射：带有自定义 class 的运算符 [] 不起作用（始终 returns 0）

Question

我正在尝试实现一个 MinHeap，其中堆上的对象是 WorkerNode。我的方法 returns map 旨在允许客户端代码确定哪些 WorkerNode 索引已从 minHeapify 操作更改。

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;

这是我看到的输出：

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

这个问题是在运行测试用例时引起我注意的，我正在做这样的事情：

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

并得到这样的输出：

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

据我所知，我的 minHeapify 方法中的退出前循环确认正确的数据被插入到地图中，但是当我尝试使用 [] 运算符访问此数据时，它无法找到我刚刚插入的 WorkerNode-index 对，returning 0 作为它可能刚刚默认构造的值。

当我尝试使用 find() 而不是 [] 时，就像这样：

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**";

我得到以下输出：

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

这是我的 WorkerNode.h 文件，注释已删除：

#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 我在这里做错了吗？

编辑：

好的伙计们，这是我的代表。我为之前无意义的代码膨胀道歉。这个例子 100% 重现了我目前的困惑。让我们一探究竟。

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;
}

运行main.cpp你自己。这里的大问题是最后两个打印语句。先前的 for 循环确认预期的键确实被 minHeapify(int) 操作 returned 并具有预期的索引。

但是，尝试使用 [Key] 将子索引编入 map<Key,int> 不会 return 预期的索引。

希望我已经更清楚地说明了混淆。

在此先感谢您的帮助。

干杯

Answer 1

我认为这个问题已经在 Remy Lebeau 的评论中指出。

您对 Key::operator< 的实施不符合 strictly weak ordering 的要求，无法满足 std::map.

中可用作键的类型的要求

您需要对实现进行细微更改。

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 <=
}

您可以使用 std::tie

简化函数

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

Answer 2

这是 minimal reproducible example 的样子：

#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;
}

这样更容易掌握吗？人们更容易帮助您吗？

你现在能自己找到问题吗？

C++ 映射：带有自定义 class 的运算符 [] 不起作用（始终 returns 0）

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

c++

stdmap

c++11