Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a class for storing memory on the stack when possible or in std::vector when it grows too much.

Note: Using std::vector with custom stack allocator would be arguably better but I did not want to depend on 3rd party allocators (and could not find one for C++11 that compiles cleanly).

#include <array>
#include <vector>
#include <algorithm>
#include <cstring>

template<std::size_t STACK_SIZE = 128>
class stack_buf
{    
public:
    using bufpair_t = std::pair<const char*, std::size_t>;
    stack_buf() :_v(), _stack_array(), _stack_size(0) {}
    ~stack_buf() {};

    stack_buf& operator=(const stack_buf& other) = delete;

    stack_buf(const stack_buf& other)
    {
        _stack_size = other._stack_size;
        if (!other._v.empty())
            _v = other._v;
        else if (_stack_size)
            std::copy(other._stack_array.begin(), other._stack_array.begin() + _stack_size, _stack_array.begin());
    }

    stack_buf(stack_buf&& other)
    {
        _stack_size = other._stack_size;
        if (!other._v.empty())
            _v = std::move(other._v);
        else if (_stack_size)
            std::copy(other._stack_array.begin(), other._stack_array.begin() + _stack_size, _stack_array.begin());
        other.clear();
    }

    void append(const char* buf, std::size_t buf_size)
    {
        //If we are aleady using _v, forget about the stack
        if (!_v.empty())
        {
            _v.insert(_v.end(), buf, buf + buf_size);
        }
        //Try use the stack
        else
        {
            if (_stack_size + buf_size <= STACK_SIZE)
            {
                std::memcpy(&_stack_array[_stack_size], buf, buf_size);
                _stack_size += buf_size;
            }
            //Not enough stack space. Copy all to _v
            else
            {
                _v.reserve(_stack_size + buf_size);
                if (_stack_size)
                    _v.insert(_v.end(), _stack_array.begin(), _stack_array.begin() + _stack_size);
                _v.insert(_v.end(), buf, buf + buf_size);
            }
        }
    }

    void append(const bufpair_t &buf)
    {
        append(buf.first, buf.second);
    }

    void clear()
    {
        _stack_size = 0;
        _v.clear();
    }

    bufpair_t get() const
    {
        if (!_v.empty())
            return bufpair_t(_v.data(), _v.size());
        else
            return bufpair_t(_stack_array.data(), _stack_size);
    }

    std::size_t size() const
    {
        if (!_v.empty())
            return _v.size();
        else
            return _stack_size;
    }

private:
    std::vector<char> _v;
    std::array<char, STACK_SIZE> _stack_array;
    std::size_t _stack_size;
};   
share|improve this question
    
Leading underscores are reserved. – Jamal May 9 '14 at 18:11
    
@Jamal A leading underscore followed by a capital letter and double underscores are "reserved". In the global namespace, leading underscores are "reserved" – dyp May 9 '14 at 20:32
    
@GamiMe Looks like a small string optimization. Why don't you just use the std::string of your Standard Library implementation? – dyp May 9 '14 at 20:34
    
@dyp. SSO is implementation dependent and won't give me the option to choose stack size as far as I know – GabiMe May 9 '14 at 22:36
    
Why is the assignment-operator deleted? – dyp May 10 '14 at 14:51
up vote 4 down vote accepted

1. Leading underscores

As Jamal pointed out in the comments, using a leading _ is dangerous, since it easily uses a reserved identifier (for example, when followed by a capital letter). I think the leading underscores are not a problem here, but I'd advise against using them. Some people use trailing underscores for data members for this reason.

2. Includes

#include <algorithm>
#include <array>
#include <cstddef> // or <cstring>; for std::size_t
#include <vector>

I sorted them alphabetically (thanks, Morwenn) so you can see if you include them multiple times.

3. Template parameters

template<typename T = char, std::size_t N = 50>
class stack_buf

I don't see any reason why should constrain this class to char. It works perfectly fine for other types, and doesn't use any string assumptions/functionality.

4. Publishing information

public:
    using value_type = T;
    using iterator = T const*;
    using bufpair_t = std::pair<iterator, std::size_t>;
    static constexpr std::size_t stack_size = N;

I think it's typically a good idea to publish the information about the type of your class, since you can infer this via partial specialization anyway. The iterator typedef increases compatibility with StdLib container classes.

5. Reducing code duplication

The copy constructor and move constructor are almost equivalent. With some function templates, we can reduce the code duplication:

private:
    struct delegate_copy_move{};
    template<class T1>
    stack_buf(T1&& other, delegate_copy_move)
        : _stack_size( other._stack_size )
    {
        if (other.uses_vector())
            _v = std::forward<T1>(other)._v;
        else
            std::copy_n(other._stack_array.begin(), _stack_size, _stack_array.begin());
    }

    bool uses_vector() const
    {
        return ! _v.empty();
    }

public:
    stack_buf(stack_buf const& other)
        : stack_buf(other, delegate_copy_move{})
    {}

    stack_buf(stack_buf&& other)
        : stack_buf(std::move(other), delegate_copy_move{})
    {
        other.clear();
    }

Note that I also replaced std::copy with std::copy_n, and removed the redundant check if (_stack_size): both algorithms work correctly with empty ranges. For arbitrary types, we should replace the copy_n with a move, dependent on whether T1 is an lvalue ref (something like a forward_n).

The uses_vector() helper function IMO increases readability, and becomes more important in an optimization (see below).

6. Default constructor and destructor

    stack_buf() : _stack_size(0) {}
    ~stack_buf() = default;

I'd advise against explicitly initializing the _stack_array data member. This will perform value-initialization, which zeroes the array. The user of the class then doesn't have any way to create an uninitialized stack_buf. However, by leaving out the value-init, the user still can write stack_buf<> s{}; or auto s = stack_buf<>{}; for value-initialization.

The destructor should be defaulted or left out completely.

7. The `append` function

    void append(value_type const* buf, std::size_t buf_size)
    {
        if (uses_vector())
        {
            _v.insert(_v.end(), buf, buf + buf_size);
        }
        else
        {
            if (_stack_size + buf_size <= stack_size)
            {
                std::copy_n(buf, buf_size, _stack_array.begin() + _stack_size);
                _stack_size += buf_size;
            }
            //Not enough stack space. Copy all to _v
            else
            {
                _v.reserve(_stack_size + buf_size);
                try
                {
                    _v.insert(_v.end(), _stack_array.begin(),
                              _stack_array.begin() + _stack_size);
                    _v.insert(_v.end(), buf, buf + buf_size);
                }catch(...)
                {
                    _v.clear();
                    throw;
                }
            }
        }
    }

I replaced the std::memcpy with a std::copy_n. As far as I know, there's no reason to use use std::memcpy at all. Again, I removed the redundant check if(_stack_size).

With the try-catch-clause, the append function now doesn't "lose" any data: When an exception occurs, we still have the data in the stack array, but the user cannot access it. By clearing the vector, we restore access to this data.

Instead of the try-catch-clause, you could also introduce a temporary vector (see below).

For arbitrary element types, we should probably use move_if_noexcept to move the elements from the array to the vector. If this is successful, we should destroy the elements in the stack array (since they might have been copied). This requires replacing the copy_n with some placement-new calls.

8. Accessors

    bufpair_t get() const
    {
        if (uses_vector())
            return bufpair_t(_v.data(), _v.size());
        else
            return bufpair_t(_stack_array.data(), _stack_size);
    }
    iterator begin() const
    {
        return get().first;
    }
    iterator end() const
    {
        return get().first + get().second;
    }

    std::size_t size() const
    {
        return get().second;
    }

I added the usual begin and end accessors so your stack_buf can be used in range-based for loops etc. All of them, including size, now rely on get, which is intended to reduce code duplication.


On the data structure itself

It is not optimal: it uses too much stack space. A first optimization is to share the space between the vector and the array, and to reduce the size of the _stack_size member. This saves you up to 31 byte on a 64-bit machine (a vector is typically 3 pointers in size, and _stack_size doesn't need to be greater than a byte typically).

This is still not optimal, as we do not use 7 of the 8 bits of _stack_size when the vector is active.

Here are the basic ideas:

template<typename T = char, std::size_t N = 128, typename S = std::size_t>
class stack_buf
{
public:
    using stack_size_t = S;
    static constexpr stack_capacity = N;

    static_assert(   stack_capacity < std::numeric_limits<stack_size_t>::max()
                  || (   stack_capacity == std::numeric_limits<stack_size_t>::max()
                      && std::is_signed<stack_size_t>())
                  , "The stack size type is too small.");

Let the user determine what type is used as the stack size type, or just use a uint8_t or unsigned char.

bool uses_vector() const
{
    return static_cast<stack_size_t>(-1) == _stack_size;
}

Use a single bit to store the information whether the stack or the array is in use.

union
{
    vector_t _v;
    array_t _stack_array;
};
stack_size_t _stack_size;

Combine the vector and the array.

template<class T1>
stack_buf(T1&& other, delegate_copy_move)
    : _stack_size( other._stack_size )
{
    if (other.uses_vector())
        new ((void*)&_v) vector_t( std::forward<T1>(other)._v );
    else
    {
        new ((void*)&_stack_array) array_t;
        std::copy_n(other._stack_array.begin(), _stack_size, _stack_array.begin());
    }
}

Use placement-new to construct the vector or array.

append is a bit tricky, since you cannot just copy from the array to the vector (they share the same memory). However, moving a vector is cheap:

void append(value_type const* buf, std::size_t buf_size)
{
    if (uses_vector())
    {
        _v.insert(_v.end(), buf, buf + buf_size);
    }
    else
    {
        if (_stack_size + buf_size <= stack_size)
        {
            std::copy_n(_buf, buf_size, _stack_array+_stack_size);
            _stack_size += buf_size;
        }
        //Not enough stack space. Copy all to _v
        else
        {
            vector_t tmp;
            tmp.reserve(_stack_size + buf_size);
            tmp.insert(tmp.end(), _stack_array.begin(),
                       _stack_array.begin() + _stack_size);
            tmp.insert(tmp.end(), buf, buf + buf_size);

            _stack_array.~array_t();
            new ((void*)&_v) vector_t( std::move(tmp) );
            _stack_size = static_cast<stack_size_t>(-1);
        }
    }
}
share|improve this answer
    
You could also replace the try-catch-clause with the technique used in the optimization (construct another vector and move after construction). – dyp May 10 '14 at 15:35
    
Thank you for this superb review. I've learned a lot! – GabiMe May 10 '14 at 21:33
    
About the static cast to -1:wouldn't that introduce a bug if the _stack_size==maxval? uses_vector() would return true – GabiMe May 10 '14 at 22:20
    
@GabiMe True, I've inserted a static_assert to cover that case, but failed to copy it into my answer. – dyp May 10 '14 at 22:42
    
Another question: Does _v = std::forward<T1>(other)._v ensures that _v get moved if T1 is rvalue? – GabiMe May 10 '14 at 23:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.