2

I have the following snippet

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

const size_t INF(numeric_limits<size_t>::max());

class nodehasher;

class node{

public:
  int x,y;
  unordered_set<node, nodehasher>::iterator neighbs[6];  //Issue Here
  node(){}
  node(int x_, int y_):x(x_),y(y_){}
  void set(int x_, int y_){x = x_,y = y_;}
  bool operator == (const node &n)const{
    return x == n.x && y == n.y;
  }
};

class nodehasher{
  std::size_t operator()(node const& n) const{
    std::size_t seed = 0;
    hash_combine(seed, n.x);
    hash_combine(seed, n.y);
    return seed;
  }
};

I seem to be having issues declaring the iterators pointing to class node inside node itself.

This causes a huge number of too verbose errors.

Now i realize i could make my neighbs array, an array of pointers to node, but i want to avoid pointers for obvious reasons

A typical simplified way i use this would be:

unordered_set<node, nodehasher> nodes;
void typical_use(node dest){
  auto src_node = node(0,0);
  int neighbcount = 0;
  auto iter = dest.insert(node).first;
  src_node.neighbs[neighb_count] = iter; 
}

I could obviously convert it into pointers and do:

src_node.neighbs[neighb_count] = &(*iter);

But Is there no way to avoid pointers for what i want to do?

EDIT:

As many of the comments and answers have pointed out both pointers and iterators to the container elements get invalidated after a rehash so it is a bad idea storing them.

I was thinking if the following way works instead of an unordered_set of node i will use an unordered_set of pointer to nodes, something like this

unordered_set<shared_ptr<node> > nodes;

Also, if i know that the number of nodes is always going to be less than 500, i could forgo this whole hash table idea and use an array and each time i will have to search the array to check if the node is already there.

Can you please point out which approach is better?

Vikash Balasubramanian
  • 2,921
  • 3
  • 33
  • 74
  • I am not sure if it is smart storing iterators in a member variable . I don't know if things internally change after you change the unordered_set and then the iterators would point to something else or be something unexpected. – Hayt Oct 17 '16 at 15:16
  • @Hayt oh goodness, i didn't even think about that, looks like pointers it is, thank you, should i delete the question? – Vikash Balasubramanian Oct 17 '16 at 15:17
  • If the question does not provide any more value to you you can delete it. You could also try to rephrase/edit the question to where you want to know an alternative to pointers without the iterator-array part. – Hayt Oct 17 '16 at 15:31
  • 1
    Both pointers and iterators can be dangerous if you don't know when the container will invalidate them. See http://stackoverflow.com/questions/6438086/iterator-invalidation-rules – Mark Ransom Oct 17 '16 at 15:39

1 Answers1

2

Standard containers require complete types for values. node isn't complete type at the point where you use it to instantiate unordered_set<node, nodehasher>.

You could use Boost.Container, because they allow incomplete types, but I don't see hashed containers there (so you'd have to use set).

You should be careful with storing iterators, though, because, at least for unordered_ containers from the standard library, they may be invalidated upon rehashing. References (and pointers) are not invalidated.

Community
  • 1
  • 1
krzaq
  • 16,240
  • 4
  • 46
  • 61
  • Can i use a smart pointer for this purpose? are any of the smart pointers suitable for this purpose? – Vikash Balasubramanian Oct 17 '16 at 15:38
  • You could, but it could easily end up with cyclic dependencies. If you treat your pointers as observer-only pointers then you should be fine with using them, especially since all the nodes belong to the container so their lifetime is well known. – krzaq Oct 17 '16 at 15:44