1

I have a class Foo, which has a vector of some large classes. The idea is, that an octal tree will be built recursively out of the elements of the vector, and each OctreeNode will have a pointer to few elements of the vector found in Foo. (In the example, just for simplicity, a node will point to only one element of the vector)

class Foo
{
    vector<LargeClass>  mLargeClasses;

    void removeItem(const int index);    //remove an element from the vector at the index
}

class OctreeNode
{
    LargeClass* mLargeClass;
}

One can say, "why bother keeping the vector after the tree is built, and store the objects in the tree itself". True, let's just say, I need to keep vector parallel to the built tree as well.

While the above concept works, I have issues when elements got removed from the underlying vector. In such case, some Octree nodes end up with dangling pointers.

My solution #1: If removeItem function is called, then before it removes the vector element, it first recursively traverse the octal tree, and make all mLargeClass pointer a nullptr which happen to point to that particular vector element. It's ok to have nullptr in the nodes, as I check each time against nullptr, when I access them anyway.

My solution #2: Have the vector store shared_ptrs, and have the OctreeNode store a weak_ptr. I am not fan of this, as each time I access a weak_ptr in the tree, it gets converted to a shared_ptr in the background with all the atomic counter increases. I am not expert on performance testing, but I have a feeling, that it is slower than a simple pointer access with if condition.

Does anybody know any better solutions?

I think the most elegant would be: To have smart pointer which behaves like a shared_pointer, counts, how many other pointer refers to it, keep a record of them, and in case it gets destroyed, it automatically nulls out all other "observer" pointers which refer to it?

Avi
  • 1,066
  • 1
  • 15
  • 37
  • 1
    Do you need to use `std::vector`? Are you iterating over it? Is cache locality useful for your application? Other containers may have more favorable invalidation rules. Naive use of `std::shared_ptr` may already reduce cache locality. – François Andrieux Mar 28 '17 at 20:06
  • @FrançoisAndrieux Yes, I do iterate through often, so I rely on cache locality. – Avi Mar 28 '17 at 20:09
  • 2
    Any insertion or removal from the vector potentially invalidates **all** pointers to its elements, so solution #1 won't really work. – n. m. could be an AI Mar 28 '17 at 20:10
  • @n.m. Ok, I see now. In that case, I would need to store unique_ptrs in that vector to avoid such case. That would also express that Foo class is the solely owner of the LargeClass vector, and it is responsible to delete it. – Avi Mar 28 '17 at 20:14
  • 1
    If the order of elements is not important, you can implement solution #1 by swapping the removed element with the last element in the vector and then popping the back off. Then update all nodes that pointed to the erased element with `nullptr` and update all nodes that pointed to the last element so they point to it's new location in the vector. – François Andrieux Mar 28 '17 at 20:16
  • 1
    @Avithohol If you rely on cache locality, using pointers will likely ruin it. – François Andrieux Mar 28 '17 at 20:17
  • 1
    There are 2 hard problems in computer science. Naming things, cache invalidation and off by one errors. Your OctTreeNode is a cache, and you are having problems with invalidation. Consider not having a cache. Unless that cache is highly, highly important, simply finding your node again *could* be faster than the overhead caused by making cache invalidation work. Regardless, your problem is this cache, and *why* the cache is important to *how* the cache should work. Explain *why*. – Yakk - Adam Nevraumont Mar 28 '17 at 20:32
  • I think there is a problem. Adding items to the vector can invalidate pointers to them. How often is the tree going to be modified (items added, removed)? – Richard Hodges Mar 28 '17 at 20:33
  • @Yakk Understand. Why *cache* is important: In the example, I talk about one Octree, but there are many other trees point the same underlying vector elements. Also there are other "users" who iterate the vector as well. – Avi Mar 28 '17 at 21:13
  • thanks, noted before by @n.m. – Avi Mar 29 '17 at 22:04

1 Answers1

0

While the field, and the purpose is somewhat different, i think i will give a try for the handle system described in this port: Simple, efficient weak pointer that is set to NULL when target memory is deallocated If I fail, I will revert back to the shared_ptr/weak_ptr duo. Described in the same post.

Community
  • 1
  • 1
Avi
  • 1,066
  • 1
  • 15
  • 37