Boost C++ Libraries

Summing all the values in a circular buffer

This example shows several functions, including summing all valid values.

#include <boost/circular_buffer.hpp>
#include <numeric>
#include <assert.h>

int main(int /*argc*/, char* /*argv*/[])
{
   // Create a circular buffer of capacity 3.
   boost::circular_buffer<int> cb(3);
   assert(cb.capacity() == 3);
   // Check is empty.
   assert(cb.size() == 0);
   assert(cb.empty());

   // Insert some elements into the circular buffer.
   cb.push_back(1);
   cb.push_back(2);

   // Assertions to check push_backs have expected effect.
   assert(cb[0] == 1);
   assert(cb[1] == 2);
   assert(!cb.full());
   assert(cb.size() == 2);
   assert(cb.capacity() == 3);

   // Insert some other elements.
   cb.push_back(3);
   cb.push_back(4);

   // Evaluate the sum of all elements.
   int sum = std::accumulate(cb.begin(), cb.end(), 0);

   // Assertions to check state.
   assert(sum == 9);
   assert(cb[0] == 2);
   assert(cb[1] == 3);
   assert(cb[2] == 4);
   assert(*cb.begin() == 2);
   assert(cb.front() == 2);
   assert(cb.back() == 4);
   assert(cb.full());
   assert(cb.size() == 3);
   assert(cb.capacity() == 3);

   return 0;
}

The circular_buffer has a capacity of three int. Therefore, the size of the buffer will never exceed three. The std::accumulate algorithm evaluates the sum of the stored elements. The semantics of the circular_buffer can be inferred from the assertions.

You can see the full example code at circular_buffer_sum_example.cpp.

Bounded Buffer Example

The bounded buffer is normally used in a producer-consumer mode: producer threads produce items and store them in the container and consumer threads remove these items and process them. The bounded buffer has to guarantee that

This example shows how the circular_buffer can be utilized as an underlying container of the bounded buffer.

#include <boost/circular_buffer.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/thread/condition.hpp>
#include <boost/thread/thread.hpp>
#include <boost/call_traits.hpp>
#include <boost/bind.hpp>

#include <boost/timer/timer.hpp> // for auto_cpu_timer

template <class T>
class bounded_buffer
{
public:

  typedef boost::circular_buffer<T> container_type;
  typedef typename container_type::size_type size_type;
  typedef typename container_type::value_type value_type;
  typedef typename boost::call_traits<value_type>::param_type param_type;

  explicit bounded_buffer(size_type capacity) : m_unread(0), m_container(capacity) {}

  void push_front(typename boost::call_traits<value_type>::param_type item)
  { // `param_type` represents the "best" way to pass a parameter of type `value_type` to a method.

      boost::mutex::scoped_lock lock(m_mutex);
      m_not_full.wait(lock, boost::bind(&bounded_buffer<value_type>::is_not_full, this));
      m_container.push_front(item);
      ++m_unread;
      lock.unlock();
      m_not_empty.notify_one();
  }

  void pop_back(value_type* pItem) {
      boost::mutex::scoped_lock lock(m_mutex);
      m_not_empty.wait(lock, boost::bind(&bounded_buffer<value_type>::is_not_empty, this));
      *pItem = m_container[--m_unread];
      lock.unlock();
      m_not_full.notify_one();
  }

private:
  bounded_buffer(const bounded_buffer&);              // Disabled copy constructor.
  bounded_buffer& operator = (const bounded_buffer&); // Disabled assign operator.

  bool is_not_empty() const { return m_unread > 0; }
  bool is_not_full() const { return m_unread < m_container.capacity(); }

  size_type m_unread;
  container_type m_container;
  boost::mutex m_mutex;
  boost::condition m_not_empty;
  boost::condition m_not_full;
}; //

The bounded_buffer relies on Boost.Thread and Boost.Bind libraries and Boost.call_traits utility.

The push_front() method is called by the producer thread in order to insert a new item into the buffer. The method locks the mutex and waits until there is a space for the new item. (The mutex is unlocked during the waiting stage and has to be regained when the condition is met.) If there is a space in the buffer available, the execution continues and the method inserts the item at the end of the circular_buffer. Then it increments the number of unread items and unlocks the mutex (in case an exception is thrown before the mutex is unlocked, the mutex is unlocked automatically by the destructor of the scoped_lock). At last the method notifies one of the consumer threads waiting for a new item to be inserted into the buffer.

The pop_back() method is called by the consumer thread in order to read the next item from the buffer. The method locks the mutex and waits until there is an unread item in the buffer. If there is at least one unread item, the method decrements the number of unread items and reads the next item from the circular_buffer. Then it unlocks the mutex and notifies one of the producer threads waiting for the buffer to free a space for the next item.

The bounded buffer::pop_back() method does not remove the item but the item is left in the circular_buffer which then replaces it with a new one (inserted by a producer) when the circular_buffer is full. This technique is more effective than removing the item explicitly by calling the circular_buffer::pop_back() method of the circular_buffer.

This claim is based on the assumption that an assignment (replacement) of a new item into an old one is more effective than a destruction (removal) of an old item and a consequent inplace construction (insertion) of a new item.

For comparison of bounded buffers based on different containers compile and run bounded_buffer_comparison.cpp. The test should reveal the bounded buffer based on the circular_buffer is most effective closely followed by the std::deque based bounded buffer. (In reality, the result may differ sometimes because the test is always affected by external factors such as immediate CPU load.)

You can see the full test code at bounded_buffer_comparison.cpp, and an example of output is

Description: Autorun "J:\Cpp\Misc\Debug\bounded_buffer_comparison.exe"
bounded_buffer<int> 5.15 s

bounded_buffer_space_optimized<int> 5.71 s

bounded_buffer_deque_based<int> 15.57 s

bounded_buffer_list_based<int> 17.33 s

bounded_buffer<std::string> 24.49 s

bounded_buffer_space_optimized<std::string> 28.33 s

bounded_buffer_deque_based<std::string> 29.45 s

bounded_buffer_list_based<std::string> 31.29 s

.