Итак, я пытаюсь создать структуру данных Graph, в которой я должен отслеживать границы в соответствии с их идентификаторами. Поэтому я создаю идентификаторы ребер в строковой структуре данных как eid: sourceid_destinationid
using namespace std;
class Edge{
public:
bool operator==(const Edge* &obj) const
{
return eid==obj->eid;
}
std::string eid;
set<int> rrids;
int sourceid;
int destid;
int strength;
public:
Edge(std::string eid,int from,int to);
std::string getId();
void addRRid(int rrid);
void removeRRid(int rrid);
void setRRid(set<int> rrids);
void setId(std::string eid);
};
Это еще один класс, который я использую для добавления и удаления краев.
HPP-файл
с использованием пространства имен std;
class RRassociatedGraph{
public:
unordered_map<int,vertex*> vertexMap;
std::unordered_map<std::string,Edge*> EdgeMap;
int noOfEdges;
public:
RRassociatedGraph();
unordered_set<vertex> getVertices();
int getNumberOfVertices();
void addVertex(vertex v);
vertex* find(int id);
Edge* findedge(std::string id);
void addEdge(int from, int to, int label);
void removeEdge(int from, int to,int rrSetID);
};
Когда я отлаживал код, я обнаружил, что в функции add edge здесь место, где я выполняю EdgeMap.insert, выполнение не переходит на следующую строку. Он остается в хеш-таблице для цикла ввода некоторого сегмента. Я не могу часто отлаживать этот код, потому что мне нужно подождать 3 часа, чтобы решить эту проблему. Код отлично работает с небольшими графиками. Но для больших графиков, где edgeMap должен хранить 800k ребер. Он входит в этот бесконечный цикл хеширования. Я не получаю этот хеш-код. Но что-то не так с моей структурой данных создания Edgemap?
#include "RRassociatedGraph.hpp"
RRassociatedGraph::RRassociatedGraph() {
noOfEdges=0;
}
void RRassociatedGraph::addVertex(vertex v) {
vertexMap.insert(pair<int,vertex*>(v.getId(), &v));
}
vertex* RRassociatedGraph::find(int id) {
unordered_map<int,vertex*>::const_iterator got=vertexMap.find(id);
if(got != vertexMap.end() )
return got->second;
return nullptr;
}
Edge* RRassociatedGraph::findedge(std::string id){
unordered_map<std::string,Edge*>::const_iterator got=EdgeMap.find(id);
if(got != EdgeMap.end() )
return got->second;
return nullptr;
}
void RRassociatedGraph::addEdge(int from, int to, int label) {
vertex* fromVertex = find(from);
if (fromVertex == nullptr) {
fromVertex = new vertex(from);
vertexMap.insert(pair<int,vertex*>(fromVertex->getId(), fromVertex));
}
vertex* toVertex = find(to);
if (toVertex == nullptr) {
toVertex = new vertex(to);
vertexMap.insert(pair<int,vertex*>(toVertex->getId(), toVertex));
}
if(fromVertex==toVertex){
// fromVertex->outDegree++;
//cout<<fromVertex->getId()<<" "<<toVertex->getId()<<"\n";
return;
}
std::string eid=std::to_string(from);
eid+="_"+std::to_string(to);
Edge* edge=findedge(eid);
if(edge==nullptr){
edge=new Edge(eid,from,to);
edge->addRRid(label);
fromVertex->addOutGoingEdges(edge);
EdgeMap.insert(pair<std::string,Edge*>(edge->getId(), edge));
noOfEdges++;
}
else{
edge->addRRid(label);
fromVertex->outDegree++;
}
}
void RRassociatedGraph::removeEdge(int from, int to,int rrSetID) {
vertex* fromVertex = find(from);
std::string eid=std::to_string(from);
eid+="_"+std::to_string(to);
if(EdgeMap.count(eid)==1){
Edge* e=EdgeMap.find(eid)->second;
if(fromVertex->removeOutgoingEdge(e,rrSetID)){
EdgeMap.erase(eid);
delete e;
}
}
}
это место, где он продолжает идти по этому циклу. Время вставки карты должно быть очень меньше, но это создает узкое место в моем коде.
template <class _Tp, class _Hash, class _Equal, class _Alloc>
void
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
{
#if _LIBCPP_DEBUG_LEVEL >= 2
__get_db()->__invalidate_all(this);
#endif // _LIBCPP_DEBUG_LEVEL >= 2
__pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
__bucket_list_.reset(__nbc > 0 ?
__pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
__bucket_list_.get_deleter().size() = __nbc;
if (__nbc > 0)
{
for (size_type __i = 0; __i < __nbc; ++__i)
__bucket_list_[__i] = nullptr;
__next_pointer __pp = __p1_.first().__ptr();
__next_pointer __cp = __pp->__next_;
if (__cp != nullptr)
{
size_type __chash = __constrain_hash(__cp->__hash(), __nbc);
__bucket_list_[__chash] = __pp;
size_type __phash = __chash;
for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr;
__cp = __pp->__next_)
{
__chash = __constrain_hash(__cp->__hash(), __nbc);
if (__chash == __phash)
__pp = __cp;
else
{
if (__bucket_list_[__chash] == nullptr)
{
__bucket_list_[__chash] = __pp;
__pp = __cp;
__phash = __chash;
}
else
{
__next_pointer __np = __cp;
for (; __np->__next_ != nullptr &&
key_eq()(__cp->__upcast()->__value_,
__np->__next_->__upcast()->__value_);
__np = __np->__next_)
;
__pp->__next_ = __np->__next_;
__np->__next_ = __bucket_list_[__chash]->__next_;
__bucket_list_[__chash]->__next_ = __cp;
}
}
}
}
}
}
У меня много файлов, поэтому я не могу поместить весь код. Я не так хорош в C ++. Пожалуйста, дайте мне знать, если я должен реализовать это каким-либо другим способом. Я должен использовать hashMap, потому что мне также нужен более быстрый поиск.