Interest in Boost.Array companion: StaticVector - A statically allocated fixed capacity vector
I've implemented a small companion class to boost.array that functions like a stack allocated vector with fixed capacity. The motivation for this class came when I was using boost.array in an interprocess library, when I realized that I actually desired an adjustable size boost.array, without the complexity of the vector class in the interprocess library. The result is StaticVector, which is boost.array directly modified with a size in front of the array, and added facilities to match std::vector. The Implementation is available at: https://github.com/ahundt/Boost.StaticVector Sample Code: StaticVector<std::size_t,3> three; three.push_back(5); three.push_back(2); // size: 2 capacity: 3 three.push_back(3); three.push_back(1); // throws std::out_of_range exception indicating the capacity has been exceeded So here is the big question: Is there any interest in the class? Cheers! Andrew Hundt
On 14/08/11 11:55, Andrew Hundt wrote:
Sample Code: StaticVector<std::size_t,3> three; three.push_back(5); three.push_back(2); // size: 2 capacity: 3 three.push_back(3);
three.push_back(1); // throws std::out_of_range exception indicating the capacity has been exceeded
Can't this just be done using Boost.Container or any stateful allcoator aware container implementation with a stateful allocator holding the static allocated block of memory ?
It seems I missed the container review, it does look like that would suffice. The simplicity of the StaticVector implementation may still make it useful for cases where all you really need are a simple array and a size, in the same way that boost.array is useful for an array alone. However, its entirely possible that StaticVector is now redundant, and that's why I'm asking if there is any interest. :-) I've also tried to come up with a better name for it, but that is the best I could think of. Any better naming suggestions around? Cheers! Andrew Hundt On Sun, Aug 14, 2011 at 5:59 AM, Joel falcou <joel.falcou@gmail.com> wrote:
On 14/08/11 11:55, Andrew Hundt wrote:
Sample Code: StaticVector<std::size_t,3> three; three.push_back(5); three.push_back(2); // size: 2 capacity: 3 three.push_back(3);
three.push_back(1); // throws std::out_of_range exception indicating the capacity has been exceeded
Can't this just be done using Boost.Container or any stateful allcoator aware container implementation with a stateful allocator holding the static allocated block of memory ?
______________________________**_________________ Unsubscribe & other changes: http://lists.boost.org/** mailman/listinfo.cgi/boost<http://lists.boost.org/mailman/listinfo.cgi/boost>
[rearranging; note that bottom- or inline-posting is preferred, see http://www.boost.org/community/policy.html#quoting] On Sun, Aug 14, 2011 at 10:09 AM, Andrew Hundt <athundt@gmail.com> wrote:
On Sun, Aug 14, 2011 at 5:59 AM, Joel falcou <joel.falcou@gmail.com> wrote:
On 14/08/11 11:55, Andrew Hundt wrote:
Sample Code: StaticVector<std::size_t,3> three; three.push_back(5); three.push_back(2); // size: 2 capacity: 3 three.push_back(3);
three.push_back(1); // throws std::out_of_range exception indicating the capacity has been exceeded
Can't this just be done using Boost.Container or any stateful allcoator aware container implementation with a stateful allocator holding the static allocated block of memory ?
True, but then the type would be syntactically uglier, you'd like have 3 extra pointers (begin, end_size, end_capacity, right?) or so of overhead, and there may be missed optimization opportunities if the compiler can't determine that, e.g., this and begin always point to the same byte in memory (this is just speculation). It seems I missed the container review, it does look like that would
suffice. The simplicity of the StaticVector implementation may still make it useful for cases where all you really need are a simple array and a size, in the same way that boost.array is useful for an array alone. However, its entirely possible that StaticVector is now redundant, and that's why I'm asking if there is any interest. :-)
I've also tried to come up with a better name for it, but that is the best I could think of. Any better naming suggestions around?
I've used a similar object that I called bounded_vector, so I think there are definitely use cases for this. - Jeff
On Sun, Aug 14, 2011 at 5:35 PM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
[rearranging; note that bottom- or inline-posting is preferred, see http://www.boost.org/community/policy.html#quoting]
On Sun, Aug 14, 2011 at 10:09 AM, Andrew Hundt <athundt@gmail.com> wrote:
On Sun, Aug 14, 2011 at 5:59 AM, Joel falcou <joel.falcou@gmail.com> wrote:
On 14/08/11 11:55, Andrew Hundt wrote:
Sample Code: StaticVector<std::size_t,3> three; three.push_back(5); three.push_back(2); // size: 2 capacity: 3 three.push_back(3);
three.push_back(1); // throws std::out_of_range exception indicating the capacity has been exceeded
Can't this just be done using Boost.Container or any stateful allcoator aware container implementation with a stateful allocator holding the static allocated block of memory ?
True, but then the type would be syntactically uglier, you'd like have 3 extra pointers (begin, end_size, end_capacity, right?) or so of overhead, and there may be missed optimization opportunities if the compiler can't determine that, e.g., this and begin always point to the same byte in memory (this is just speculation).
It seems I missed the container review, it does look like that would
suffice. The simplicity of the StaticVector implementation may still make it useful for cases where all you really need are a simple array and a size, in the same way that boost.array is useful for an array alone. However, its entirely possible that StaticVector is now redundant, and that's why I'm asking if there is any interest. :-)
I've also tried to come up with a better name for it, but that is the best I could think of. Any better naming suggestions around?
I've used a similar object that I called bounded_vector, so I think there are definitely use cases for this.
- Jeff _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
I tend to agree with Jeff here. My goal with StaticVector was to match Boost.Array as closely as possible while providing the additional service of tracking the number of elements in the array for simplicity and ease of use. Cheers! Andrew Hundt
On Aug 14, 2011, at 2:55 AM, Andrew Hundt wrote:
I've implemented a small companion class to boost.array that functions like a stack allocated vector with fixed capacity. The motivation for this class came when I was using boost.array in an interprocess library, when I realized that I actually desired an adjustable size boost.array, without the complexity of the vector class in the interprocess library. The result is StaticVector, which is boost.array directly modified with a size in front of the array, and added facilities to match std::vector.
The Implementation is available at: https://github.com/ahundt/Boost.StaticVector
Sample Code: StaticVector<std::size_t,3> three; three.push_back(5); three.push_back(2); // size: 2 capacity: 3 three.push_back(3);
three.push_back(1); // throws std::out_of_range exception indicating the capacity has been exceeded
So here is the big question: Is there any interest in the class?
I took a look at the class, and I have a couple of comments: * Since the underlying storage is "T elems[N]", this means that N different elements get created at construction time. While this is fine for a fixed size array, a variable sized array should start out with no constructions, and create elements as they are added (like vector). * In operator [] (line 234 and 240), you are asserting if the index is out of range. Again, this may be correct for a fixed size array, but not in a variable sized one. Compare with vector. Also, the assertion is incorrect. Consider the case where N = 10, size = 4, and i = 7. I like the idea, but I think you need to revisit how the class works. -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
I took a look at the class, and I have a couple of comments:
* Since the underlying storage is "T elems[N]", this means that N different elements get created at construction time. While this is fine for a fixed size array, a variable sized array should start out with no constructions, and create elements as they are added (like vector).
Good point. I've modified elems to be a char array, and I now reinterpret_cast to the class T as necessary. Elements should only be constructed when they are added now.
* In operator [] (line 234 and 240), you are asserting if the index is out of range. Again, this may be correct for a fixed size array, but not in a variable sized one. Compare with vector. Also, the assertion is incorrect. Consider the case where N = 10, size = 4, and i = 7.
Are you suggesting I simply remove the assert? I know that vectors do not check the size, but BOOST_ASSERT should only be called when compiled in debug mode. I chose to detect when users are accessing what is now uninitialized memory in debug mode, with no effect on release mode. If the convention is different I can remove the assert. Thanks for the help! Cheers! Andrew Hundt On Sun, Aug 14, 2011 at 1:11 PM, Marshall Clow <mclow.lists@gmail.com>wrote:
On Aug 14, 2011, at 2:55 AM, Andrew Hundt wrote:
I've implemented a small companion class to boost.array that functions like a stack allocated vector with fixed capacity. The motivation for this class came when I was using boost.array in an interprocess library, when I realized that I actually desired an adjustable size boost.array, without the complexity of the vector class in the interprocess library. The result is StaticVector, which is boost.array directly modified with a size in front of the array, and added facilities to match std::vector.
The Implementation is available at: https://github.com/ahundt/Boost.StaticVector
Sample Code: StaticVector<std::size_t,3> three; three.push_back(5); three.push_back(2); // size: 2 capacity: 3 three.push_back(3);
three.push_back(1); // throws std::out_of_range exception indicating the capacity has been exceeded
So here is the big question: Is there any interest in the class?
I took a look at the class, and I have a couple of comments:
* Since the underlying storage is "T elems[N]", this means that N different elements get created at construction time. While this is fine for a fixed size array, a variable sized array should start out with no constructions, and create elements as they are added (like vector).
* In operator [] (line 234 and 240), you are asserting if the index is out of range. Again, this may be correct for a fixed size array, but not in a variable sized one. Compare with vector. Also, the assertion is incorrect. Consider the case where N = 10, size = 4, and i = 7.
I like the idea, but I think you need to revisit how the class works.
-- Marshall
Marshall Clow Idio Software <mailto:mclow.lists@gmail.com>
A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 15 August 2011 16:05, Andrew Hundt <athundt@gmail.com> wrote:
Good point. I've modified elems to be a char array, and I now reinterpret_cast to the class T as necessary. Elements should only be constructed when they are added now.
What are you doing about alignment? Take a look at Synyhesizing Types with Specific Alignments in the Type Traits library for a start. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <athundt@gmail.com> wrote:
I've implemented a small companion class to boost.array that functions like a stack allocated vector with fixed capacity. The motivation for this class came when I was using boost.array in an interprocess library, when I realized that I actually desired an adjustable size boost.array, without the complexity of the vector class in the interprocess library. The result is StaticVector, which is boost.array directly modified with a size in front of the array, and added facilities to match std::vector.
The Implementation is available at: https://github.com/ahundt/Boost.StaticVector
Sample Code: StaticVector<std::size_t,3> three; three.push_back(5); three.push_back(2); // size: 2 capacity: 3 three.push_back(3);
three.push_back(1); // throws std::out_of_range exception indicating the capacity has been exceeded
So here is the big question: Is there any interest in the class?
Cheers! Andrew Hundt
On Mon, Aug 15, 2011 at 5:20 PM, Nevin Liber <nevin@eviloverlord.com> wrote:
On 15 August 2011 16:05, Andrew Hundt <athundt@gmail.com> wrote:
Good point. I've modified elems to be a char array, and I now reinterpret_cast to the class T as necessary. Elements should only be constructed when they are added now.
What are you doing about alignment? Take a look at Synyhesizing Types with Specific Alignments in the Type Traits library for a start. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Phil Endecott wrote:
In the case of StativVector<char,N> where N<256, you should consider using uint8_t to store the size - and similar variations. Boost.Integer makes it possible to select a suitable type.
I know its been a while since I sent my first emails regarding StaticVector, but I haven't had a good chance to fix the issues people brought up until now. The solutions seem to be much easier than I expected. - I believe I've resolved the StaticVector alignment using type_traits' aligned_storage. - I've also added the use of Boost.Integer to select the smallest possible type for the internal size value. Any thoughts? Cheers! Andrew Hundt
Andrew Hundt wrote:
I've implemented a small companion class to boost.array that functions like a stack allocated vector with fixed capacity. The motivation for this class came when I was using boost.array in an interprocess library, when I realized that I actually desired an adjustable size boost.array, without the complexity of the vector class in the interprocess library. The result is StaticVector, which is boost.array directly modified with a size in front of the array, and added facilities to match std::vector.
In the case of StativVector<char,N> where N<256, you should consider using uint8_t to store the size - and similar variations. Boost.Integer makes it possible to select a suitable type. I am wondering whether C++11's user string literal stuff could be used to select a suitable max string size at compile time. For example: auto s1( "Hello"S ); // S suffix creates a static_string<5> in this case auto s2( "World"S ); auto s3 = s1 + ' ' + s2; // Result is static_string<11> I could imagine very efficient short string expressions done like this. Phil.
This sounds like it might have significant overlap with Thorsten Ottosen's auto_vector (http://www.cs.aau.dk/~nesotto/boost/auto_buffer.zip), which is in the boost review queue (http://www.boost.org/community/review_schedule.html) but does not yet have dates assigned.
On Sun, Aug 14, 2011 at 6:32 PM, Kim Barrett <kab.conundrums@verizon.net>wrote:
This sounds like it might have significant overlap with Thorsten Ottosen's auto_vector (http://www.cs.aau.dk/~nesotto/boost/auto_buffer.zip), which is in the boost review queue ( http://www.boost.org/community/review_schedule.html) but does not yet have dates assigned.
This does look like it meets many of my goals as well. Am I correct that this would be similar to the vector in the Container library, where the memory would be local to the allocator supplied as a parameter? Sticking as closely as possible to boost.array as possible with added tracking of the size of what is stored inside it as I do here may still be useful. I also had a goal of keeping StaticVector as a POD object. Can that be achieved with a custom allocator? I don't modify allocators frequently so I'm not familiar with all the details and implications of their design. Cheers! Andrew Hundt
On 15 August 2011 15:43, Andrew Hundt <athundt@gmail.com> wrote:
Sticking as closely as possible to boost.array as possible with added tracking of the size of what is stored inside it as I do here may still be useful. I also had a goal of keeping StaticVector as a POD object.
StaticVector is very far away from being POD. It has constructors and different public/private sections. And I don't think you can fix it, since you are going to want to zero m_size. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
participants (7)
-
Andrew Hundt -
Jeffrey Lee Hellrung, Jr. -
Joel falcou -
Kim Barrett -
Marshall Clow -
Nevin Liber -
Phil Endecott