Fixed size vector

[Andrea Crotti]

I would need something in theory quite simple, a vector of a certain
size, which, when I add something and it's full, simply deletes the last
entry.

If for example I have

MyContainer x(3);
x.push(1);
x.push(2);
x.push(3);
x.push(4);

it should contain now
<4, 3, 2>


I don't see any of the STL structures doing exactly what I would like,
any suggestions on how to implement it?

 

[Andrea Crotti]

I would need something in theory quite simple, a vector of a certain
size, which, when I add something and it's full, simply deletes the last
entry.

If for example I have

MyContainer x(3);
x.push(1);
x.push(2);
x.push(3);
x.push(4);

it should contain now
<4, 3, 2>


I don't see any of the STL structures doing exactly what I would like,
any suggestions on how to implement it?

The whole story (which is maybe more helpful) is that I have a vector of
vectors of a certain maximal size
<1, 2, 3>
<2, 2, 3>
....
and I have to compute a vector which is the average of all of them.
Now what I did is a vector of vectors and using a map to count up the
values for after doing the average

--8<---------------cut here---------------start------------->8---
// if it's a landmark one 0 should always be so
std::map<coord_t, int> land_hops;
for (int i=0; i < history_size; ++i) {
for (int j=0; j < address.getSize(); ++j) {
coord_t hop_count = address[j];

// if it's not reachable or == 0 then it should not be inside the average
if (hop_count > 0) {
if (land_hops.count(j) == 0) {
land_hops[j] = hop_count;
} else {
land_hops[j] += hop_count;
}
}
}
--8<---------------cut here---------------end--------------->8---

but it's really ugly and not very smart probably, better ideas??

 

[Morten Frederiksen]

I would need something in theory quite simple, a vector of a certain
size, which, when I add something and it's full, simply deletes the last
entry.

If for example I have

MyContainer x(3);
x.push(1);
x.push(2);
x.push(3);
x.push(4);

it should contain now
<4, 3, 2>

I don't see any of the STL structures doing exactly what I would like,
any suggestions on how to implement it?

What you are looking for is a circular buffer.

The closest thing in STL is probably std::deque but you have to
implement a size overflow check and pop from the front of the queue
yourself.

If you are using Boost, you may have a look at boost::circular_buffer.

Regards,
Morten Frederiksen

 

[Andrea Crotti]

What you are looking for is a circular buffer.

The closest thing in STL is probably std::deque but you have to
implement a size overflow check and pop from the front of the queue
yourself.

If you are using Boost, you may have a look at boost::circular_buffer.

Regards,
Morten Frederiksen

I'm wondering if it's not better to use a simpler approach, an array (or
something similar) with two indices indicating the beginning and the
end.

Would not that be simpler and fast anyway?

More generally I don't understand one thing, suppose I have an object
that without a parameter doens't make sense, BUT in another class I want
it as a member, how do I manage?

For example

--8<---------------cut here---------------start------------->8---
class Person
Person(string name);

class Record
Person p;
--8<---------------cut here---------------end--------------->8---

this of course doesn't work since the object can't be constructed,
differently from java where I could do something like this (and pass the
parameter to the constructor with the *new*).

How am I supposed to do this, using a 0-length constructor and a setter??

 

[Morten Frederiksen]

I'm wondering if it's not better to use a simpler approach, an array (or
something similar) with two indices indicating the beginning and the
end.

That is one way to implement a circular buffer, and it is probably how
boost::circular_buffer is implemented.

More generally I don't understand one thing, suppose I have an object
that without a parameter doens't make sense, BUT in another class I want
it as a member, how do I manage?

For example

--8<---------------cut here---------------start------------->8---
class Person
      Person(string name);

class Record
      Person p;
--8<---------------cut here---------------end--------------->8---

this of course doesn't work since the object can't be constructed,
differently from java where I could do something like this (and pass the
parameter to the constructor with the *new*).

How am I supposed to do this, using a 0-length constructor and a setter??

There are two solutions:

1. Create a default ctor (i.e. taking no args) for Person. (But you
say that this does not make sense in your context.)

2. Create a default ctor for Record and initialize member variable p
in the member initializer list of this ctor.

 

[Andrea Crotti]

There are two solutions:

1. Create a default ctor (i.e. taking no args) for Person. (But you
say that this does not make sense in your context.)

Well it can be done of course, but if they're compulsory arguments to
make the object usable, I don't see why they should not be in the constructor.

2. Create a default ctor for Record and initialize member variable p
in the member initializer list of this ctor.

This I don't get how is done.
I mean if I just add a member of that type without passing the arguments
wanted by the constructor the compiler complains already, an example of
how to do this?

 

[Andrea Crotti]

Ok then, now suppose I create my own RingBuffer, and it will contains
vectors of int.

Now I want to know what's the average of those (a vector of int which
composed by the average of the vectors).

How should I proceed?
In functional languages (and even python) I would apply some lambda to
the list, or pass some comparison functions.

stupid example:
--8<---------------cut here---------------start------------->8---
l = [(1,2), (3,2)]
l.sort(key=lambda x: x[1])
--8<---------------cut here---------------end--------------->8---
and I sort the list on the second element

Is there a way to do it in such a clean way?

Because otherwise I should implement those functions in RingBuffer,
which is not maybe a good idea...

 

[Morten Frederiksen]

This I don't get how is done.
I mean if I just add a member of that type without passing the arguments
wanted by the constructor the compiler complains already, an example of
how to do this?

class Record
{
public:

// Ctor taking a Person object as arg
Record(const Person& _p)
: p(_p) // This is the member initializer list
{}

Person p;
};

 

[Morten Frederiksen]

Ok then, now suppose I create my own RingBuffer, and it will contains
vectors of int.

Now I want to know what's the average of those (a vector of int which
composed by the average of the vectors).

How should I proceed?
In functional languages (and even python) I would apply some lambda to
the list, or pass some comparison functions.

stupid example:
--8<---------------cut here---------------start------------->8---
l = [(1,2), (3,2)]
l.sort(key=lambda x: x[1])
--8<---------------cut here---------------end--------------->8---
and I sort the list on the second element

Is there a way to do it in such a clean way?

In general, C++ code does not turn out as consize as some other
programming languages.

Because otherwise I should implement those functions in RingBuffer,
which is not maybe a good idea...

It is certainly not a bad idea to implement e.g.
RingBuffer::average().

You could use std::accumulate() from the STL numeric header to sum the
vectors in your ring buffer or just write a for loop to do it.

If you need to compute the average often, it may be a better idea to
let your RingBuffer maintain the accumulated vector, updating it
whenever you push or pop from the RingBuffer. Then your average()
function only needs to divide by the number of elements in the buffer.

 

[Andrea Crotti]

It is certainly not a bad idea to implement e.g.
RingBuffer::average().

You could use std::accumulate() from the STL numeric header to sum the
vectors in your ring buffer or just write a for loop to do it.

If you need to compute the average often, it may be a better idea to
let your RingBuffer maintain the accumulated vector, updating it
whenever you push or pop from the RingBuffer. Then your average()
function only needs to divide by the number of elements in the buffer.

Well I think I will do this in the end, my only concern was just that a
RingBuffer containing a generic object should not really have a method
average.
Unless of course I subclass it with another class

CoordRingBuffer (or whatever) and then I implement it..

But in general is still possible to pass function pointers, why do you
say it's not so concise?

 

[Rui Maciel]

I'm wondering if it's not better to use a simpler approach, an array (or
something similar) with two indices indicating the beginning and the
end.

Would not that be simpler and fast anyway?

I don't know about speed but the simplest way would be to wrap a
std::deque container with a class and push/pop through your interfaces.
The pop method would just std::deque:op_front() and the push method
would push_back. Then, if the deque's size was larger than your limit
then it would perform a deque:op_front().


Rui Maciel

 

[Andrea Crotti]

I don't know about speed but the simplest way would be to wrap a
std::deque container with a class and push/pop through your interfaces.
The pop method would just std::deque:op_front() and the push method
would push_back. Then, if the deque's size was larger than your limit
then it would perform a deque:op_front().


Rui Maciel

That sounds already very good.
You meant something like this?
--8<---------------cut here---------------start------------->8---
template<typename T>
void RingBuffer<T>:ush(T el)
{
if (buffer.size() == max_size) {
buffer.pop_front();
}
buffer.push_back(el);
}

template<typename T>
T RingBuffer<T>:op()
{
return buffer.pop_front();
}
--8<---------------cut here---------------end--------------->8---

It doens't work like this I gues, and about the indexing that's not
automatically kept right?

When I add and remove elements I have to keep track of the indexin a
start/end variable right?