There may not be as many internal allocations as one would expect when appending an item at a time. It is documented that for list.append(), the average and amortized worst case complexity is constant.
Boost.Python does a fairly good job at allowing Python-ish code to be written in C++. As such, one could use the Python idiom, [None] * n for allocating a list to a given size:
/// @brief Construct list with `n` elements. each element is a copy
/// of `value`.
/// @param n Iniitail container size.
/// @param item Item with which to fill the container.
boost::python::list make_list(
const std::size_t n,
boost::python::object item = boost::python::object() /* none */)
{
namespace python = boost::python;
// >>> [None] * n;
python::list result;
result.append(item);
result *= n;
return result;
}
I cannot find documentation that explicitly states the implementation behavior of such operation, but the idiom often out performs over append. Nevertheless, while Boost.Python does not expose all of the Python/C API capabilities, one could guarantee a single allocation by using PyList_New(len) to create the list, then manage and manipulate it via Boost.Python. As noted in the documentation, when len is greater than zero, all items must be set to real objects via PyList_SetItem() before exposing the list object to Python code, or in this case, a boost::python::list object:
If len is greater than zero, the returned list object’s items are set to NULL. Thus you cannot use abstract API functions such as PySequence_SetItem() or expose the object to Python code before setting all items to a real object with PyList_SetItem().
Auxiliary functions may help hide these details. For instance, one could use a factory function with fill-like behavior:
/// @brief Construct list with `n` elements. each element is a copy
/// of `value`.
/// @param n Iniitail container size.
/// @param item Item with which to fill the container.
boost::python::list make_list(
const std::size_t n,
boost::python::object item = boost::python::object() /* none */)
{
namespace python = boost::python;
python::handle<> list_handle(PyList_New(n));
for (std::size_t i=0; i < n; ++i)
{
// PyList_SetItem will steal the item reference. As Boost.Python is
// managing the item, explicitly increment the item's reference count
// so that the stolen reference remains alive when this Boost.Python
// object's scope ends.
Py_XINCREF(item.ptr());
PyList_SetItem(list_handle.get(), i, item.ptr());
}
return python::list{list_handle};
}
Or a factory function that works on a range:
/// @brief Construct a list from a given range of [first,last). The
/// copied range includes all elements between `first` to `last`,
/// including `first`.
/// @param first Input iterator to the initial item to copy.
/// @param last Input iterator to one after the final item to be copied.
template <typename Iterator>
boost::python::list make_list(Iterator first, Iterator last)
{
namespace python = boost::python;
const auto size = std::distance(first, last);
python::handle<> list_handle{PyList_New(size)};
for (auto i=0; i < size; ++i, ++first)
{
python::object item{*first};
// PyList_SetItem will steal the item reference. As Boost.Python is
// managing the item, explicitly increment the item's reference count
// so that the stolen reference remains alive when this Boost.Python
// object's scope ends.
Py_XINCREF(item.ptr());
PyList_SetItem(list_handle.get(), i, item.ptr());
}
return boost::python::list{list_handle};
}
Here is a complete example demonstrating with mocked up COBS_WORST_LEN() and cobs_decode() functions that decode by accumulating pairs. As the decoded values are known when the list being returned is constructed, I have opted to use a range factory function to prevent having to iterate over the list and setting the values twice:
#include <boost/python.hpp>
#include <iostream>
#include <vector>
#include <boost/python/stl_iterator.hpp>
/// Mockup that halves the list, rounding up.
std::size_t COBS_WORST_LEN(const std::size_t len)
{
return (len / 2) + (len % 2);
}
/// Mockup that just adds adjacent elements together.
void cobs_decode(
const boost::uint8_t* input,
const std::size_t size,
boost::uint8_t* output)
{
for (std::size_t i=0; i < size; ++i, ++input)
{
if (i % 2 == 0)
{
*output = *input;
}
else
{
*output += *input;
++output;
}
}
}
/// @brief Construct a list from a given range of [first,last). The
/// copied range includes all elements between `first` to `last`,
/// including `first`.
/// @param first Input iterator to the initial value to copy.
/// @param last Input iterator to one after the final element to be copied.
template <typename Iterator>
boost::python::list make_list(Iterator first, Iterator last)
{
namespace python = boost::python;
const auto size = std::distance(first, last);
python::handle<> list_handle{PyList_New(size)};
for (auto i=0; i < size; ++i, ++first)
{
python::object item{*first};
// PyList_SetItem will steal the item reference. As Boost.Python is
// managing the item, explicitly increment the item's reference count
// so that the stolen reference remains alive when this Boost.Python
// object's scope ends.
Py_XINCREF(item.ptr());
PyList_SetItem(list_handle.get(), i, item.ptr());
}
return boost::python::list{list_handle};
}
/// @brief Decode a list, returning the aggregation of paired items.
boost::python::list decode(boost::python::list py_data)
{
namespace python = boost::python;
// Clone the list.
std::vector<boost::uint8_t> data(len(py_data));
std::copy(
python::stl_input_iterator<boost::uint8_t>{py_data},
python::stl_input_iterator<boost::uint8_t>{},
begin(data));
// Decode the list.
std::vector<boost::uint8_t> decoded(COBS_WORST_LEN(data.size()));
cobs_decode(&data[0], data.size(), &decoded[0]);
return make_list(begin(decoded), end(decoded));
}
BOOST_PYTHON_MODULE(example)
{
namespace python = boost::python;
python::def("decode", &decode);
}
Interactive usage:
>>> import example
>>> assert(example.decode([1,2,3,4]) == [3,7])
Also, as Boost.Python can throw exceptions, it may be worth considering using memory-managed containers, such as std::vector, or smart pointers, rather than the raw dynamic arrays.
