Sign in to follow this  

Unity Alternative for std::vector/STL?

This topic is 4246 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi everybody, A few months ago in one of my projects I used the std::vector class. I restarted my project and am working on small executables / 64K apps. But because of this - I lost the opportunity to use the std::vector class. Is there a possibility to include it in my projects? I like this class. It is very easy to use, I think (okay - the parts of it I need). So...Any alternatives for std::vector/STL??? thx! cu

Share this post


Link to post
Share on other sites
Well, if your data is static, you could just use a standard c-array. If you do need the flexibility of a vector, it is pretty easy to make a simple one yourself.

The class contains a templated pointer and the size of the array. Whenever you need more space in the array, copy its contents to another array, re-new the original array to twice the size, then copy the data back. Add in a few functions to push_back and overload the [] operator and you are set...

Share this post


Link to post
Share on other sites
I agree with Sr_Guapo, if you're making a tiny exe, then you'll most likely want to write your own vector class so you have as much control over it as possible. An array would probably result in less code, so long as it doesn't need resized often.

Share this post


Link to post
Share on other sites
You should just write your own vector class, in most cases it is just a linked list. If you need any advice on how to make it just let us know.

theTroll

Share this post


Link to post
Share on other sites
Quote:
Original post by TheTroll
You should just write your own vector class, in most cases it is just a linked list. If you need any advice on how to make it just let us know.


He shouldn't write a vector class as a linked list, he should write a linkedlist (or list/slist as C++ calls it) class as a linked list. Also I agree if you need a small executable, then STL shouldn't be used. Your own, non-templated (templates, in most cases create code for every template class), class might be the best idea.

Share this post


Link to post
Share on other sites
Quote:
Original post by Bregma
What makes you think the standard vector takes up more space than any alternative?


He doesn't mean overhead from the stl-vector implementation,
but space overhead from linking with the stl - which will make
his 64kb demo bigger (eg stlport.lib is 950 kb big).

And it shouldn't be too difficult to make your own custom
vector-template which doesn't depend on anything... Again, usually
I would advice against custom vector/list/... implementation, but
for a 64kb demo I can see whe he wants to do it that way.

Share this post


Link to post
Share on other sites
The reason I said write a "vector" class is so that he would write a class using the same naming convntion and functions that he is used to.

theTroll

Share this post


Link to post
Share on other sites
Quote:
Original post by CTar
Quote:
Original post by TheTroll
You should just write your own vector class, in most cases it is just a linked list. If you need any advice on how to make it just let us know.


He shouldn't write a vector class as a linked list, he should write a linkedlist (or list/slist as C++ calls it) class as a linked list. Also I agree if you need a small executable, then STL shouldn't be used. Your own, non-templated (templates, in most cases create code for every template class), class might be the best idea.

I've read about at least one implementation of the vector class which is incredibly efficient, and rather clever in my book, regarding code size. It specializes std::vector<void*>, I believe, and implements just about all of the code there. Then for every other type of std::vector, it inherits from std::vector<void*>, and the only additional code it needs to add is a few functions that contain a reinterpret_cast<>() call, which takes very little space (possibly no space?) code-wise.

If you do write your own vector class, it wouldn't hurt to look at the code for an already implemented version. You might find some useful things in there.

Share this post


Link to post
Share on other sites
Quote:
Original post by TheTroll
You should just write your own vector class, in most cases it is just a linked list. If you need any advice on how to make it just let us know.

theTroll


Its my understanding that in all cases its continous memory, that's part of the spec. You can't legally implement a vector as a linked list.

Ahh, I see you clarified your point. I'll accept that logic:)

Cheers
Chris

Share this post


Link to post
Share on other sites
Quote:
Original post by TheTroll
The reason I said write a "vector" class is so that he would write a class using the same naming convntion and functions that he is used to.

theTroll


When looking for a class with the same performance characteristics as a linked list he should be used to using std::list or std::slist. Well we should stop discussing this, since it's going off-topic I think.

Share this post


Link to post
Share on other sites
Writing 64k demos is predominantly about minimizing code size. In these conditions using templates is sketchy because it expands binary size very quickly. It may actually be wiser to use type-unsafe void* based containers if you want to fit inside that 64 kilobyte cage.

Share this post


Link to post
Share on other sites
Quote:
Original post by Kitt3n
He doesn't mean overhead from the stl-vector implementation,
but space overhead from linking with the stl - which will make
his 64kb demo bigger (eg stlport.lib is 950 kb big).


When you link to a static library, you don't typically merge the whole library with your program, but only those bits you have used. Furthermore, it is my understanding that stlport.lib only contains precompiled iostream class instanciations (for char and wchar_t); std::vector is still pulled in and compiled from the source that is in the <vector> header.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by TheTroll
You should just write your own vector class, in most cases it is just a linked list.



ROFL a STL vector is NEVER implemented as a linked list. That's just preposterous.

Share this post


Link to post
Share on other sites
Quote:
Original post by TheTroll
You should just write your own vector class, in most cases it is just a linked list. If you need any advice on how to make it just let us know.

theTroll


If you write vector classes as linked lists. How then do you solve the O(1) access time that vectors are supposed to boast...

Share this post


Link to post
Share on other sites
Avoiding STL containers because they could be bloated is a typical premature optimization.
It should be easy to write some code using std::vector and inspect the size of what std::vector specializations compile to; in a 64k demo this kind of analysis is likely to be required anyway.

[Edited by - LorenzoGatti on May 2, 2006 11:59:37 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
It's not the bloat of vector it's from the fact, that you have duplicated code fpr every instanziation. Therefore it is better to use a generic void* vector and then cast it to the right type (this could be in a template, as mentioned some posts before).

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
It's not the bloat of vector it's from the fact, that you have duplicated code fpr every instanziation. Therefore it is better to use a generic void* vector and then cast it to the right type (this could be in a template, as mentioned some posts before).


You don't think partial specialization is good enough? Could you post your profiling results?

Share this post


Link to post
Share on other sites
Quote:
Original post by Bregma
Quote:
Original post by Anonymous Poster
It's not the bloat of vector it's from the fact, that you have duplicated code fpr every instanziation. Therefore it is better to use a generic void* vector and then cast it to the right type (this could be in a template, as mentioned some posts before).


You don't think partial specialization is good enough? Could you post your profiling results?


The point is that even partial specialisation creates more code than using a generic void*. For every type he wants to use, the preprocessor will generate the code to handle that type. That's what templates do, and as remarkably useful as they are, they do increase code-size. It's not about speed (unless you meant code-size when talking about "profiling", in which case, you know that already).

Share this post


Link to post
Share on other sites
Quote:
Original post by Bregma
Could you post your profiling results?


I tried a simple code, where the compiler (VS 2005) most likely have optimized some stuff away. But with the following code:

#include <vector>
#include <iostream>

template<typename T>
void print(const std::vector<T>& p)
{
for( std::vector<T>::const_iterator iter = p.begin();
p.end() != iter;
++iter)
{
std::cout << (*iter) << std::endl;
}
}

int main()
{
#ifdef USE_VOID_PTR
std::vector<void*> a;
std::vector<void*> b;
std::vector<void*> c;
std::vector<void*> d;
std::vector<void*> e;
std::vector<void*> f;
#else
std::vector<char> a;
std::vector<short> b;
std::vector<int> c;
std::vector<long> d;
std::vector<float> e;
std::vector<double> f;
#endif

for( unsigned int i = 0;i<10;++i)
{
a.push_back( 0 );
b.push_back( 0 );
c.push_back( 0 );
d.push_back( 0 );
e.push_back( 0 );
f.push_back( 0 );
}

print( a );
print( b );
print( c );
print( d );
print( e );
print( f );

return 0;
}




If USE_VOID_PTR is defined the generated executable (release mode, optimize for size) is 9728 bytes, but if USE_VOID_PTR isn't defined the generated code is 14848 bytes. So the executable growed with 66% or 5120 bytes.

EDIT: Using my own, simple vector, I was able to get the same executable down to 6656 (no other changes than switching the vector type and removing the include).

[Edited by - CTar on May 2, 2006 8:34:28 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by CTar
If USE_VOID_PTR is defined the generated executable (release mode, optimize for size) is 9728 bytes, but if USE_VOID_PTR isn't defined the generated code is 14848 bytes. So the executable growed with 66% or 5120 bytes.

EDIT: Using my own, simple vector, I was able to get the same executable down to 6656 (no other changes than switching the vector type and removing the include).

The test isn't fair: it instantiates only print<void*>, not the six numeric print<> specializations (which are also likely to pull in something specific from <iostream>).
You also dodge the casts and dereferencing of the void* pointers that are required to actually access the objects.

Share this post


Link to post
Share on other sites
The whole point is kinda moot anyway, 64K demos should be optimized for executable size so linking unnecessary code is out of the question. And when using libraries your executable *will* be contaminated one way or the other, unless you delve into the disassembly and make sure it doesn't. On the other hand there isn't any advantage for resizable arrays either, as the 64k limit doesn't involve the use of memory at runtime, so you could just grab as much memory as you need and access it directly.

Also, C++ requires some bodily libs of itself, so perhaps it isn't the best language to do 64K demos in. There is hardly a way around C or ultimately ASM, I guess, if you'd like to add some data to your file too. Search for a library named libctiny, it offers a minimal C runtime which results in really small .exe's, at the cost of functionality of course. You could link to it from your C++ compiler too.

Share this post


Link to post
Share on other sites
Quote:
Original post by chollida1
Really, it looks like he's using them to me!


If your talking about
Quote:
The test isn't fair: it instantiates only print<void*>, not the six numeric print<> specializations

Then no hes not using them, LorenzoGatti is right, the test is unfair.

Share this post


Link to post
Share on other sites

This topic is 4246 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this