 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Matthias Pfeifer
Guest
|
 Posted: Fri Feb 10, 2006 3:06 pm Post subject: howto assure that a bunch of vectors is a connected amount o |
 |
|
Hello,
I hope the subject does not unclarify to much...
Well. Basically the question is like this: I want to use a
std::vector<std::vector<mytype> > my_vector;
I know in advance how elements there will be in my_vector and
i know in advance how much memory each of these members will
consume. What i want to achieve is that the memory of the
individual elements is not scattered all over the addressspace
but that they line up one after the other. Is that possible?
matthias
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
 |
Daniel T.
Guest
|
| Posted: Fri Feb 10, 2006 5:06 pm Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
In article <453dopF4p2mrU1 (AT) news (DOT) dfncis.de>,
Matthias Pfeifer <pfemat (AT) web (DOT) de> wrote:
| Quote: | Hello,
I hope the subject does not unclarify to much...
Well. Basically the question is like this: I want to use a
std::vector<std::vector<mytype> > my_vector;
I know in advance how elements there will be in my_vector and
i know in advance how much memory each of these members will
consume. What i want to achieve is that the memory of the
individual elements is not scattered all over the addressspace
but that they line up one after the other. Is that possible?
|
Yes, but not with that construct. Use a Matrix class instead:
template < typename T >
class Matrix
{
int _size;
std::vector<T> _rep;
public:
Matrix( int s ): _size( s ), _rep( s * s ) { }
T& operator()( int x, int y ) { return _rep[x * _size + y]; }
const T& operator()( int x, int y ) const {
return _rep[x * _size + y];
}
};
Other methods, and error protection should be added to taste.
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Michael Tiomkin
Guest
|
| Posted: Fri Feb 10, 2006 5:06 pm Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
Matthias Pfeifer wrote:
| Quote: | Hello,
I hope the subject does not unclarify to much...
Well. Basically the question is like this: I want to use a
std::vector<std::vector<mytype> > my_vector;
I know in advance how elements there will be in my_vector and
i know in advance how much memory each of these members will
consume. What i want to achieve is that the memory of the
individual elements is not scattered all over the addressspace
but that they line up one after the other. Is that possible?
|
Most of implementations of std::vector<T> use 'T *' as iterator
type, and the usual ++ and -- ptr operators for these iterators. In
this case, the addresses of the members will not be scattered. BTW, I'm
only talking about virtual addresses here.
On a different implementation, the vector elements can be placed in
different regions of memory at the same time. One example is a 16-bit
address machine with 16MB addressability (80286), or a 32-bit address
processor with >4GB addressability (80386, P4, P5, P6, Pentium 4,
PowerPC etc.). If you need a larger array, you'll use a long ptr that
usually contains a segment-offset pair, and the computation of address
from the offset is a bit more complicated.
The second question is the placement of elements of your array in
physical memory. If your process uses virtual memory for data, you
cannot ensure consequent addresses of the elements. On a DSP without
virtual memory and without memory segmentation, you would avoid
scattering of elements in physical memory.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Pete Becker
Guest
|
| Posted: Sat Feb 11, 2006 3:06 am Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
Matthias Pfeifer wrote:
| Quote: |
I know in advance how elements there will be in my_vector and
i know in advance how much memory each of these members will
consume. What i want to achieve is that the memory of the
individual elements is not scattered all over the addressspace
but that they line up one after the other. Is that possible?
|
One of the big benefits you get from using vector is that it handles
memory management for you. If you want to do your own memory management
vector might not be the right tool. My inclination would be to write my
own container. It's not that hard...
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Ivan Vecerina
Guest
|
| Posted: Sat Feb 11, 2006 3:06 am Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
"Matthias Pfeifer" <pfemat (AT) web (DOT) de> wrote in message
news:453dopF4p2mrU1 (AT) news (DOT) dfncis.de...
....
: Well. Basically the question is like this: I want to use a
:
: std::vector<std::vector<mytype> > my_vector;
:
: I know in advance how elements there will be in my_vector and
: i know in advance how much memory each of these members will
: consume. What i want to achieve is that the memory of the
: individual elements is not scattered all over the addressspace
: but that they line up one after the other. Is that possible?
You cannot have guaranteed continuity accross vectors.
What you have to do instead is use a single vector:
std::vector< mytype > my_vector;
then use some customized index computations (probably
encapsulated in some utility functions).
Cheers,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Maciej Sobczak
Guest
|
| Posted: Sat Feb 11, 2006 3:06 am Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
Matthias Pfeifer wrote:
| Quote: | std::vector<std::vector<mytype> > my_vector;
I know in advance how elements there will be in my_vector and
i know in advance how much memory each of these members will
consume. What i want to achieve is that the memory of the
individual elements is not scattered all over the addressspace
but that they line up one after the other. Is that possible?
|
It is possible, but rather tricky. You will need to define your own
allocator and use it for the "nested" vectors. In this allocator, use
some preallocated (and big "enough") block of memory as a pool and
allocate the memory for these nested vectors from this pool. For this to
work, you will need to make sure that the vectors do not resize in the
meantime, because they will then fragment your pool. Use the reserve
method or the sizing constructor to define the vectors' sizes once and
for all and be *very* careful about what you are doing then with all the
vectors, so that they don't need to reallocate their internal buffers.
--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Matthias Pfeifer
Guest
|
| Posted: Sat Feb 11, 2006 12:06 pm Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
"Michael Tiomkin" <tmk (AT) netvision (DOT) net.il> wrote in
news:1139584809.287300.79510 (AT) g43g2000cwa (DOT) googlegroups.com:
| Quote: | Most of implementations of std::vector<T> use 'T *' as iterator
type, and the usual ++ and -- ptr operators for these iterators. In
this case, the addresses of the members will not be scattered. BTW, I'm
only talking about virtual addresses here.
|
Please. Did you note that i am talking about
std::vector< std::vector<T> >
(note the nesting)?
Matthias
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Matthias Pfeifer
Guest
|
| Posted: Sat Feb 11, 2006 12:06 pm Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
"Daniel T." <postmaster (AT) earthlink (DOT) net> wrote in news:postmaster-
B4301C.11223210022006 (AT) news (DOT) east.earthlink.net:
| Quote: |
Yes, but not with that construct. Use a Matrix class instead:
|
This is just what i want to avoid. Also the vectors (inside the
vector) have different lengths.
Matthias.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Ivan Vecerina
Guest
|
| Posted: Sat Feb 11, 2006 12:06 pm Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
"Maciej Sobczak" <no.spam (AT) no (DOT) spam.com> wrote in message
news:dsifr7$662$1 (AT) sunnews (DOT) cern.ch...
: Matthias Pfeifer wrote:
:
: > std::vector<std::vector<mytype> > my_vector;
: >
: > I know in advance how elements there will be in my_vector and
: > i know in advance how much memory each of these members will
: > consume. What i want to achieve is that the memory of the
: > individual elements is not scattered all over the addressspace
: > but that they line up one after the other. Is that possible?
:
: It is possible, but rather tricky. You will need to define your own
: allocator and use it for the "nested" vectors. In this allocator, use
: some preallocated (and big "enough") block of memory as a pool and
: allocate the memory for these nested vectors from this pool. For this to
: work, you will need to make sure that the vectors do not resize in the
: meantime, because they will then fragment your pool. Use the reserve
: method or the sizing constructor to define the vectors' sizes once and
: for all and be *very* careful about what you are doing then with all the
: vectors, so that they don't need to reallocate their internal buffers.
If this was to ever work by chance on a specific platform & library
version, it would be excessively brittle.
If nothing else, an implementation of std::vector is always free to
over-allocate its capacity during resizing or calls to reserve().
As per the standard:
23.2.4.2/2 ( about vector::capacity(), **emphasis** added )
Effects: A directive that informs a vector of a planned change in size,
so that it can manage the storage allocation accordingly. After
reserve(), capacity() is **greater or equal** to the argument of reserve
if reallocation happens; and equal to the previous value of capacity()
otherwise. Reallocation happens at this point if and only if the current
capacity is less than the argument of reserve().
Cheers,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Daniel T.
Guest
|
| Posted: Sat Feb 11, 2006 6:06 pm Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
In article <Xns9766F0876B25Cpfematwebde (AT) 130 (DOT) 133.1.17>,
Matthias Pfeifer <pfemat (AT) web (DOT) de> wrote:
| Quote: | "Daniel T." <postmaster (AT) earthlink (DOT) net> wrote in news:postmaster-
B4301C.11223210022006 (AT) news (DOT) east.earthlink.net:
Yes, but not with that construct. Use a Matrix class instead:
This is just what i want to avoid. Also the vectors (inside the
vector) have different lengths.
|
A single vector is guaranteed contiguous, but you have a number of
vectors so each individual vector is contiguous but they will not be
laid back to back. The only way to do that is to use a single vector.
Maybe I misunderstood what you wanted?
If you need all the objects in a contiguous block of memory and have a
ragged array, you can make a more complex Matrix class that does the
right thing.
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Carl Barron
Guest
|
| Posted: Sat Feb 11, 2006 6:06 pm Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
In article <Xns9766F0876B25Cpfematwebde (AT) 130 (DOT) 133.1.17>, Matthias Pfeifer
<pfemat (AT) web (DOT) de> wrote:
| Quote: | "Daniel T." <postmaster (AT) earthlink (DOT) net> wrote in news:postmaster-
B4301C.11223210022006 (AT) news (DOT) east.earthlink.net:
Yes, but not with that construct. Use a Matrix class instead:
This is just what i want to avoid. Also the vectors (inside the
vector) have different lengths.
Why? Note a vector<T*> whose elements point into a vector<T |
does not require the rows[internal vectors] to be the same length,
if the size of the rows is known at construction time then something
like this accomplishes producing a data structure with the ussual
subscript notation producing appropriate results.
template <class T>
class Jaggaed
{
std::vector<T> data;
std::vector<T *> row_start;
public:
Jagged(int n_r, int *rs):row_start(rs,rs+n_r)
{
int n_elements = std::accumulate(rs,rs+n_r,0);
data.resize(n_elements);
T *p = &data[0];
for(int i=0;i!=n_r;++i,p+=rs[i])
row_start[i] = p;
}
T * operator [](std::ptrdiff_t i) {return row_start[i];}
};
now
Jagged jag(....);
jag[i][j] is the ussual meaning most likely...
it might place the data in two contiguous areas, but all the data of
the 'matrix' is in Jagged::data, and all the pointers are in
Jagged::row_start,
This is what you want to accomplish isn't it???
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Maciej Sobczak
Guest
|
| Posted: Sun Feb 12, 2006 6:06 pm Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
Ivan Vecerina wrote:
| Quote: | After
reserve(), capacity() is **greater or equal** to the argument
|
You are right about the fact that the vector might get *more* memory
than actually requested and there is no control over this additional
amount. I was thinking in terms of allocating a memory to all vectors so
that all elements fall into the single block of memory, which can be for
example requested from the operating system with a single bulk
allocation. Then, custom allocator can do the trick.
After re-reading the OP it looks like what is really required is "that
they line up one after the other". If this really means "with no padding
at all" (for example so that all elements can be iterated over with a
single pointer and a loop), then even the custom allocator will not
work. Separate vectors are separate objects and the internal
overallocation is what can make the elements really apart.
Thanks for pointing that out.
--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Matthias Pfeifer
Guest
|
| Posted: Mon Feb 13, 2006 12:06 am Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
:As per the standard:
:23.2.4.2/2 ( about vector::capacity(), **emphasis** added )
: Effects: A directive that informs a vector of a planned change in size,
:so that it can manage the storage allocation accordingly. After
:reserve(), capacity() is **greater or equal** to the argument of reserve
:if reallocation happens; and equal to the previous value of capacity()
:otherwise. Reallocation happens at this point if and only if the current
:capacity is less than the argument of reserve().
Maciej's looks still like the most c++-way to solve the task,
if we are not considering anything below the virtual memory
system. The gain i had in mind was (of course) than i access
the memory in a linear pattern. If i understook you critic,
you say that there might still be "holes" in my array caused
by reserve()?
Can you also go a little more into detail? How much of a "hole"
might that be and why is it there?
Matthias
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Maciej Sobczak
Guest
|
| Posted: Mon Feb 13, 2006 10:06 am Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
Matthias Pfeifer wrote:
| Quote: | The gain i had in mind was (of course) than i access
the memory in a linear pattern. If i understook you critic,
you say that there might still be "holes" in my array caused
by reserve()?
|
Yes, the reserve() function is allowed to allocate more than requested.
The only thing it guarantees is that there will be place for *at least*
the requested number of elements, without the need for reallocation.
| Quote: | Can you also go a little more into detail? How much of a "hole"
might that be and why is it there?
|
The "hole" can be whatever the library likes. The raison d'etre for this
hole is to ease anticipated (future) insertions and additions, or just
because the vector was designed in a way that makes it easier to work
with some size patterns, like "divisible by 16", "be power of 2", etc.
Try this simple test:
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char *argv[])
{
for (int s = 1; s != 50; ++s)
{
vector<int> v;
v.reserve(s);
cout << s << '\t' << v.capacity() << '\n';
}
}
It prints the requested and actually allocated buffer sizes. On my
system it prints the same values in both columns (which means that there
are no overallocations), but that's not guaranteed by the standard and
other implementations can print larger values in the right column.
--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Matthias Pfeifer
Guest
|
| Posted: Mon Feb 13, 2006 2:06 pm Post subject: Re: howto assure that a bunch of vectors is a connected amou |
|
|
Carl Barron wrote:
| Quote: | In article <Xns9766F0876B25Cpfematwebde (AT) 130 (DOT) 133.1.17>, Matthias Pfeifer
pfemat (AT) web (DOT) de> wrote:
"Daniel T." <postmaster (AT) earthlink (DOT) net> wrote in news:postmaster-
B4301C.11223210022006 (AT) news (DOT) east.earthlink.net:
Yes, but not with that construct. Use a Matrix class instead:
This is just what i want to avoid. Also the vectors (inside the
vector) have different lengths.
Why? Note a vector<T*> whose elements point into a vector<T
does not require the rows[internal vectors] to be the same length,
if the size of the rows is known at construction time then something
like this accomplishes producing a data structure with the ussual
subscript notation producing appropriate results.
[SNIP]
it might place the data in two contiguous areas, but all the data of
the 'matrix' is in Jagged::data, and all the pointers are in
Jagged::row_start,
This is what you want to accomplish isn't it???
|
Well, this is what i already have (sort of...). And - Yes, you are
right: what is implemented here is a matrix. I already have a
working code and right now i am trying to simplify it.
Matthias
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
