Reference counting in a collection

Question

Let's have a collection of objects (say string is type of collection). I want each element of collection to have a reference count. So, on Add-Usage it should increment count for this given element.

coll.AddUsage("SomeElement"); // Type doesn't matter - but should increase count

On, Release-Usage, it should decrement the reference count for given element, and if count reaches 0, then it should remove the element from collection.

It is not important if AddUsage will allocate element (and set reference-count to 1), or would fail altogether (since element didn't exist). Important thing is RemoveUsage, which should remove given element (object) from collection.

I thought of using vector of a pair (or a custom struct), or using any kind of map/multimap. There exists no existing class in C++ library (may be out of thread-support library, one atomic classes, shared-pointer classes etc).

Question:

So, my question is how to implement such idea, using existing C++ library? It should be thread safe. Yes, C++11/14 is perfectly okay for me. If good idea is there, I would probably craft it on top of templates.

Answer 1

Assuming you ask for a data structure to implement your reference-counting collection...

Use a map<K,V> with K as the type of collection elements (in your example string) and V a type to keep track of meta-information about the element (e.g. reference count). The simplest case is when V is int.

Then, AddUsage is simple, just do refMap[value]++. For RemoveUsage just do a refMap[value]--, then check if the counter hit zero and remove the value from the map.

You need to add error handling too, since AddUsage / RemoveUsage may be called with an object which is not in the map (not added to the collection)

EDIT: You tagged your question with "multithreading", so you probably want to have a mutex of some sort which guards the concurrent access to refMap.

Answer 2

You can use static member(integer) variable in the structure or class. Increment or decrement whereever you want. Remove the element if the value is zero.

Answer 3

You could implement something similar to shared_ptr class but extending it to hold collection of objects.

Like you could design a class with map/multimap as its data member. Key would be your object and value be your reference count.As far as interface is concerned just expose two methods:-

AddUsage(Object);
RemoveUsage(Object);

In your AddUsage method you would first check if element already exists in map.If yes then only increment the count. Likewise you would handle RemoveUsage.Object would be deleted from map if its reference count reaches zero.

This is just my opinion. Please let me know if there are any bottlenecks in this implementation.