Я пытаюсь реализовать MinHeap, где объектами в куче являются WorkerNodes. Мой метод возвращает карту, которая предназначена для того, чтобы позволить клиентскому коду определить, какие индексы 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]
Итак, из того, что я могу сказать , Предварительный выход для l oop в моем методе minHeapify подтверждает, что в карту вставляются правильные данные, но когда я пытаюсь получить доступ к этим данным с помощью оператора [], он не может найти индекс WorkerNode спаривание, которое я только что вставил, возвращая 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 самостоятельно. Большая проблема здесь - последние два печатных заявления. Предыдущее для l oop подтверждает, что ожидаемые ключи действительно возвращаются операцией minHeapify(int) и имеют ожидаемый индекс.
Однако попытки субиндексировать с помощью [Key] в map<Key,int> не не возвращают ожидаемый индекс.
Надеюсь, я проиллюстрировал путаницу немного яснее.
Заранее спасибо за помощь.
Приветствия