A lock-free stack can store each value in a std::shared_ptr allocated when the value is pushed. Its pop() returns the pointer, or an empty pointer when the stack is empty; allocating during push avoids a potentially throwing allocation during pop(). section 7.2.1
Listing 7.3. A lock-free stack that leaks nodes
template<typename T>
class lock_free_stack
{
private:
struct node
{
std::shared_ptr<T> data; #1
node* next;
node(T const& data_):
data(std::make_shared<T>(data_)) #2
{}
};
std::atomic<node*> head;
public:
void push(T const& data)
{
node* const new_node=new node(data);
new_node->next=head.load();
while(!head.compare_exchange_weak(new_node->next,new_node));
}
std::shared_ptr<T> pop()
{
node* old_head=head.load();
while(old_head && #3
!head.compare_exchange_weak(old_head,old_head->next));
return old_head ? old_head->data : std::shared_ptr<T>(); #4
}
};
The listing uses std::shared_ptr<T> for node data and returns the removed node’s pointer, while leaving node reclamation unresolved. section 7.2.1
