473,221 Members | 2,339 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,221 software developers and data experts.

Which container to use for circular buffer?

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

Aug 7 '06 #1
7 19958
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
Aug 7 '06 #2

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
Aug 7 '06 #3
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
Aug 7 '06 #4

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
Aug 7 '06 #5
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
}

Aug 7 '06 #6

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

Aug 7 '06 #7

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
Aug 8 '06 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: William Stacey | last post by:
Working with implementing a circular buffer for a producer/consumer deal. Have not done one in a while. The following seems to work. However, I remember and have seen other implementation that...
3
by: davihigh | last post by:
Hi Friends: I am managing a large number of objects which has unique id <ULONG64>. Which container i should choose to perform best find() performance? Can choose from STL in vc2003 or Boost...
6
by: Bart Simpson | last post by:
I am wriing a messaging system and I need to mantain a list of subscribers(object) to topics (string). which of the ff representations is better (and why?) typedef pair<string,...
2
by: marco.furlan | last post by:
Hi there, I have to write an optimized circular buffer to log events in C++. The elements are of type std::string. This should run under Linux on an ARM embedded system. I can dedicate to this...
9
by: thiago777 | last post by:
I have four methods(threads) in my application that must work syncronized sharing an 8 element circular buffer array. Each method should work in the data only after its previous thread had completed...
2
by: sharanap | last post by:
Implement a circular buffer of size 32 using an array inC, can anybody tel the answer, this que. asked to my friends in an interview
12
by: Sven | last post by:
Can someone point out source code for a safe circular buffer receiver transmitter? It's for sending and receiving bytes via RS232. Thanks in advance.
0
by: veera ravala | last post by:
ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
0
by: mar23 | last post by:
Here's the situation. I have a form called frmDiceInventory with subform called subfrmDice. The subform's control source is linked to a query called qryDiceInventory. I've been trying to pick up the...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.