Which container to use for circular buffer?

[toton]

Hi,
I want a circular buffer or queue like container (queue with array
implementation).
Moreover I want random access over the elements. And addition at tail
and remove from head need to be low cost.

STL vector is suitable for removing form tail? or it is as costly as
removing from middle?
any other std container to serve this purpose? (note , I dont need
linked list implementation of any container, as I want random access)

thanks

abir

[Kai-Uwe Bux]

toton wrote:

Hi,
I want a circular buffer or queue like container (queue with array
implementation).
Moreover I want random access over the elements. And addition at tail
and remove from head need to be low cost.

STL vector is suitable for removing form tail? or it is as costly as
removing from middle?

Removing from the back is cheap in std::vector. Removing from the head is
costly.

any other std container to serve this purpose? (note , I dont need
linked list implementation of any container, as I want random access)

Sounds like std::deque might fit the bill.
Best

Kai-Uwe Bux

[toton]

Kai-Uwe Bux wrote:

toton wrote:

Hi,
I want a circular buffer or queue like container (queue with array
implementation).
Moreover I want random access over the elements. And addition at tail
and remove from head need to be low cost.

STL vector is suitable for removing form tail? or it is as costly as
removing from middle?

Removing from the back is cheap in std::vector. Removing from the head is
costly.

any other std container to serve this purpose? (note , I dont need
linked list implementation of any container, as I want random access)

Sounds like std::deque might fit the bill.

yes, dequeue looks best option. It supports random access and
add/remove from front/back at const time.
Thanks for the solution.
One more side question.
I am putting some classes in a container (previously vector ,now
dequeue :) ) , as value, not as pointer. It requires copy constructor
for the class to be placed (looks very mich logical also ). Otherwise
it gives error.
like vector<Pointpoints;
points.push_back(Point(2,3));
But my question is, does it really create the class & copy it inside
the container, or it creates the class directly in the proper position?
If it is the first case, I suspect serious performance problem in my
code, as I push a lost of Points and other data in a circular buffer
process, and remove. So one copy at every iteration is really a concern
to me.
preiously i used one circular buffer implemented by me, and using
placement new to place it in proper position in the buffer. which works
fine, no copy / assignmen is done. no extra memory allocation etc.
which one has advantage, and should be used?
thanks
abir

>
Best

Kai-Uwe Bux

[Kai-Uwe Bux]

toton wrote:

>
Kai-Uwe Bux wrote:

>toton wrote:

Hi,
I want a circular buffer or queue like container (queue with array
implementation).
Moreover I want random access over the elements. And addition at tail
and remove from head need to be low cost.

STL vector is suitable for removing form tail? or it is as costly as
removing from middle?

Removing from the back is cheap in std::vector. Removing from the head is
costly.

any other std container to serve this purpose? (note , I dont need
linked list implementation of any container, as I want random access)

Sounds like std::deque might fit the bill.

yes, dequeue looks best option. It supports random access and
add/remove from front/back at const time.
Thanks for the solution.
One more side question.
I am putting some classes in a container (previously vector ,now
dequeue :) ) , as value, not as pointer. It requires copy constructor
for the class to be placed (looks very mich logical also ). Otherwise
it gives error.

That is correct.

like vector<Pointpoints;
points.push_back(Point(2,3));
But my question is, does it really create the class & copy it inside
the container, or it creates the class directly in the proper position?

Depends. The compiler is entitled to by-pass copy construction in many
circumstances. Optimizing compilers often do that.

If it is the first case, I suspect serious performance problem in my
code, as I push a lost of Points and other data in a circular buffer
process, and remove. So one copy at every iteration is really a concern
to me.

Measure before taking action.

preiously i used one circular buffer implemented by me, and using
placement new to place it in proper position in the buffer. which works
fine, no copy / assignmen is done. no extra memory allocation etc.
which one has advantage, and should be used?

Before resorting to placement new, you could:

a) reserve enough room in the container so that reallocations are avoided.
b) experiment with various allocators.
Best

Kai-Uwe Bux

[toton]

Kai-Uwe Bux wrote:

toton wrote:

Kai-Uwe Bux wrote:

toton wrote:

Hi,
I want a circular buffer or queue like container (queue with array
implementation).
Moreover I want random access over the elements. And addition at tail
and remove from head need to be low cost.

STL vector is suitable for removing form tail? or it is as costly as
removing from middle?

Removing from the back is cheap in std::vector. Removing from the head is
costly.
any other std container to serve this purpose? (note , I dont need
linked list implementation of any container, as I want random access)

Sounds like std::deque might fit the bill.

yes, dequeue looks best option. It supports random access and
add/remove from front/back at const time.
Thanks for the solution.
One more side question.
I am putting some classes in a container (previously vector ,now
dequeue :) ) , as value, not as pointer. It requires copy constructor
for the class to be placed (looks very mich logical also ). Otherwise
it gives error.

That is correct.

like vector<Pointpoints;
points.push_back(Point(2,3));
But my question is, does it really create the class & copy it inside
the container, or it creates the class directly in the proper position?

Depends. The compiler is entitled to by-pass copy construction in many
circumstances. Optimizing compilers often do that.

but not always done? I mean according to you it is a option only, like
return value optimization, and implementation depends on the compiler
itself?

If it is the first case, I suspect serious performance problem in my
code, as I push a lost of Points and other data in a circular buffer
process, and remove. So one copy at every iteration is really a concern
to me.

Measure before taking action.

I will measure the performance, surely.
In fact I may port the application to a low end mobile device, where I
am not sure a optimizing compiler will exist!!!

>

preiously i used one circular buffer implemented by me, and using
placement new to place it in proper position in the buffer. which works
fine, no copy / assignmen is done. no extra memory allocation etc.
which one has advantage, and should be used?

Before resorting to placement new, you could:

a) reserve enough room in the container so that reallocations are avoided.
b) experiment with various allocators.

I assure the container doesn't allocate additional memory too
frequently.It is surely a rare event, occures only when I really need
to store additional Points. It is more like a fixed buffer, or
citrcular queue, with proper memory reserved for the container. And the
memory gets reused thriough out the process. (In my placement new
implementation, you can well think a fixed amount of memory pre
allocated, and objects gets initialized & deinitialized over the rail
in a circular fashion, without any extra memory allocation, or copying
or assignment).

The additional cost if comes, it is only through the assignment / copy
constructor, as every moment I may create a bunch of additional object,
put a copy inside container , and destroy it .It never creates
excessive memory allocation, but can have very frequent memory
allocation & deallocation outside container.

Allocators are used to allocate memory for the container, I think. But
my container is almost fixed size. will it gain any performance
improvement from a different allocator?

Thanks again for the suggestion.... I am gaining a lot in these days
regarding C++ working concepts :)

Best

Kai-Uwe Bux

[Mark P]

toton wrote:

Hi,
I want a circular buffer or queue like container (queue with array
implementation).
Moreover I want random access over the elements. And addition at tail
and remove from head need to be low cost.

STL vector is suitable for removing form tail? or it is as costly as
removing from middle?
any other std container to serve this purpose? (note , I dont need
linked list implementation of any container, as I want random access)

thanks

abir

Typically a circular buffer would be a fixed size (otherwise the
"circle" isn't very well defined). Here's some old code I once posted
here in response to a similar question. Help yourself...

-Mark
#include <vector>
#include <iostream>

///////////////////
// class CBuffer //
///////////////////

template <class T>
class CBuffer
{
public:
CBuffer (unsigned int size);
T read ();
void write (const T& value);

private:
std::vector<Tbuffer;
unsigned int size;
unsigned int rIdx;
unsigned int wIdx;
bool empty;
bool full;
};

template <class T>
CBuffer<T>::CBuffer (unsigned int size) :
buffer(size), size(size), rIdx(0), wIdx(0),
empty(true), full(false) {}

template <class T>
T CBuffer<T>::read()
{
if (empty)
{
std::cerr << "Error: can't read from empty buffer." << std::endl;
exit(1);
}
full = false; // buffer can't be full after a read
const T& result = buffer[rIdx];
rIdx = (rIdx + 1) % size;
empty = (rIdx == wIdx); // true if read catches up to write
return result;
}

template <class T>
void CBuffer<T>::write (const T& value)
{
empty = false; // buffer can't be empty after a write
buffer[wIdx] = value;
wIdx = (wIdx + 1) % size;
if (full)
rIdx = wIdx;
full = (wIdx == rIdx); // true if write catches up to read
}

[Alan Johnson]

toton wrote:

Kai-Uwe Bux wrote:

toton wrote:

Hi,
I want a circular buffer or queue like container (queue with array
implementation).
Moreover I want random access over the elements. And addition at tail
and remove from head need to be low cost.
>
STL vector is suitable for removing form tail? or it is as costly as
removing from middle?

Removing from the back is cheap in std::vector. Removing from the head is
costly.

any other std container to serve this purpose? (note , I dont need
linked list implementation of any container, as I want random access)

Sounds like std::deque might fit the bill.

yes, dequeue looks best option. It supports random access and
add/remove from front/back at const time.
Thanks for the solution.
One more side question.
I am putting some classes in a container (previously vector ,now
dequeue :) ) , as value, not as pointer. It requires copy constructor
for the class to be placed (looks very mich logical also ). Otherwise
it gives error.
like vector<Pointpoints;
points.push_back(Point(2,3));
But my question is, does it really create the class & copy it inside
the container, or it creates the class directly in the proper position?
If it is the first case, I suspect serious performance problem in my
code, as I push a lost of Points and other data in a circular buffer
process, and remove. So one copy at every iteration is really a concern
to me.
preiously i used one circular buffer implemented by me, and using
placement new to place it in proper position in the buffer. which works
fine, no copy / assignmen is done. no extra memory allocation etc.
which one has advantage, and should be used?
thanks
abir

If this does cause a performance problem (if the compiler doesn't
optimize away the copy construction completely), there is a less exotic
solution (and thus more maintainable) than placement new. Provide a
"cheap" default constructor and copy constructor, perhaps they do
nothing at all, and then provide another member function to do
initialization. Example:

class Point
{
public:
Point() { /* Do nothing */ }
Point(const Point &) { /* Do nothing */ }
void set(int x, int y) { /* set values here */ }
};

....
dq.push_back(Point());
dq.back().set(3,4);
Before doing that, though, make sure that you really have a problem.
If your point class is only a couple of integers then the cost of
copying (even if the compiler does not optimize away the copy) is very
low. In fact, if we are assuming the compiler will not perform
optimizations, then the cost of copying a couple of integers could very
well be substantially less than the function call overhead in this
method.

--
Alan Johnson

[toton]

Alan Johnson wrote:

toton wrote:

Kai-Uwe Bux wrote:

toton wrote:
>
Hi,
I want a circular buffer or queue like container (queue with array
implementation).
Moreover I want random access over the elements. And addition at tail
and remove from head need to be low cost.

STL vector is suitable for removing form tail? or it is as costly as
removing from middle?
>
Removing from the back is cheap in std::vector. Removing from the head is
costly.
>
>
any other std container to serve this purpose? (note , I dont need
linked list implementation of any container, as I want random access)
>
Sounds like std::deque might fit the bill.

yes, dequeue looks best option. It supports random access and
add/remove from front/back at const time.
Thanks for the solution.
One more side question.
I am putting some classes in a container (previously vector ,now
dequeue :) ) , as value, not as pointer. It requires copy constructor
for the class to be placed (looks very mich logical also ). Otherwise
it gives error.
like vector<Pointpoints;
points.push_back(Point(2,3));
But my question is, does it really create the class & copy it inside
the container, or it creates the class directly in the proper position?
If it is the first case, I suspect serious performance problem in my
code, as I push a lost of Points and other data in a circular buffer
process, and remove. So one copy at every iteration is really a concern
to me.
preiously i used one circular buffer implemented by me, and using
placement new to place it in proper position in the buffer. which works
fine, no copy / assignmen is done. no extra memory allocation etc.
which one has advantage, and should be used?
thanks
abir

If this does cause a performance problem (if the compiler doesn't
optimize away the copy construction completely), there is a less exotic
solution (and thus more maintainable) than placement new. Provide a
"cheap" default constructor and copy constructor, perhaps they do
nothing at all, and then provide another member function to do
initialization. Example:

class Point
{
public:
Point() { /* Do nothing */ }
Point(const Point &) { /* Do nothing */ }
void set(int x, int y) { /* set values here */ }
};

...
dq.push_back(Point());
dq.back().set(3,4);
Before doing that, though, make sure that you really have a problem.
If your point class is only a couple of integers then the cost of
copying (even if the compiler does not optimize away the copy) is very
low. In fact, if we are assuming the compiler will not perform
optimizations, then the cost of copying a couple of integers could very
well be substantially less than the function call overhead in this
method.

Yes, cheap solution, but very bad solution im my case.
My Point's are not supposed to change its value (immutable) and
accesses from different thread. It will be too buggy code, If i allow a
set method for point, and will break all beauty of my code. Those
points are points which draw a english character. and once its written
by a writer, wont change its value. And if I allow a set method, thew
program can unknowningly make an 'A' to 'B'!!! I prefer OOP concepts
over memory management.
I can write one difficult class at one place, but cant allow breaking
encapsulation in the program. It will create more evil than good.
Any tool/technique which can detect whether copy ctor is inlined or
return value optimization is performed? kind of a profiler for C++?

abir

Alan Johnson