0

Background: this is a followup to @pari's answer to Constant-sized vector.

My type, metadata_t does not have a default constructor.

I use std::make_unique for fixed-size arrays that the size is not available in compile-time. (ie const size).

typedef std::unique_ptr<metadata_t[]> fixedsize_metadata_t;
fixedsize_metadata_t consolidate(const std::vector<metadata_t> &array) {

    // note: this is run-time:
    auto n = array.size();

    return fixedsize_side_metadata_t(array.begin(), array.end());  // error
    return fixedsize_side_metadata_t(array);  // error
    return std::unique_ptr<metadata_t[]>(0); // no error, but not useful
    return std::unique_ptr<metadata_t[]>(n); // error
}

However, the constructor of unique_ptr<...[]> only accepts a size (integer). How do I initialise and copy my vector into my unique_ptr<[]>?

I tried std::unique_ptr<metadata_t[]>(array.size()); to prepare and then copy/populate the contents in the next step, but it shows a compile error.

Note: I use C++20 (or higher if it was available). Could make_unique_for_overwrite be useful? ( C++23 ).

Note: At first I thought generate (as in this answer) can do it, but it does not solve my problem because n is a run-time information.

The size of my vector is determined at run-time.

The whole point of this function is to convert my std::vector into a fixed-size data structure (with run-time size).

The data structure does not have to be unique_ptr<T[]>. The old title referred to unique_ptr but I am really looking for a solution for a fixed-size data structure. So far, it is the only data structure I found as a "constant-size indexed container with size defined at runtime".

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Sohail Si
  • 2,750
  • 2
  • 22
  • 36
  • Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackoverflow.com/rooms/246372/discussion-on-question-by-sohail-si-how-to-fill-in-a-c-container-with-fixed-si). – Machavity Jul 12 '22 at 13:28

3 Answers3

2

You can't initialize the elements of a unique_ptr<T[]> array with the elements of a vector<T> array when constructing the new array (UPDATE: apparently you can, but it is still not going to be a solution solved with a single statement, as you are trying to do).

You will have to allocate the T[] array first, and then copy the vector's elements into that array one at a time, eg:

typedef std::unique_ptr<metadata_t[]> fixedsize_metadata_t;

fixedsize_metadata_t consolidate(const std::vector<metadata_t> &array) {
    fixedsize_metadata_t result = std::make_unique<metadata_t[]>(array.size());
    std::copy(array.begin(), array.end(), result.get());
    return result;
}

UPDATE: you updated your question to say that metadata_t does not have a default constructor. Well, that greatly complicates your situation.

The only way to create an array of objects that don't support default construction is to allocate an array of raw bytes of sufficient size and then use placement-new to construct the individual objects within those bytes. But now, you are having to manage not only the objects in the array, but also the byte array itself. By itself, unique_ptr<T[]> won't be able to free that byte array, so you would have to provide it with a custom deleter that frees the objects and the byte array. Which also means, you will have to keep track of how many objects are in the array (something new[] does for you so delete[] works, but you can't access that counter, so you will need your own), eg:

struct metadata_arr_deleter
{
    void operator()(metadata_t *arr){
        size_t count = *(reinterpret_cast<size_t*>(arr)-1);
        for (size_t i = 0; i < count; ++i) {
            arr[i]->~metadata_t();
        }
        delete[] reinterpret_cast<char*>(arr);
    }
};

typedef std::unique_ptr<metadata_t[], metadata_arr_deleter> fixedsize_metadata_t;

fixedsize_metadata_t consolidate(const std::vector<metadata_t> &array) {

    const auto n = array.size();
    const size_t element_size = sizeof(std::aligned_storage_t<sizeof(metadata_t), alignof(metadata_t)>);

    auto raw_bytes = std::make_unique<char[]>(sizeof(size_t) + (n * element_size));

    size_t *ptr = reinterpret_cast<size_t*>(raw_bytes.get());
    *ptr++ = n;
    auto *uarr = reinterpret_cast<metadata_t*>(ptr);
    size_t i = 0;

    try {
        for (i = 0; i < n; ++i) {
            new (&uarr[i]) metadata_t(array[i]);
        }
    }
    catch (...) {
        for (size_t j = 0; j < i; ++j) {
            uarr[j]->~metadata_t();
        }
        throw;
    }

    raw_bytes.release();
    return fixedsize_metadata_t(uarr);
}

Needless to say, this puts much more responsibility on you to allocate and free memory correctly, and it is really just not worth the effort at this point. std::vector already supports everything you need. It can create an object array using a size known at runtime, and it can create non-default-constructable objects in that array, eg.

std::vector<metadata_t> consolidate(const std::vector<metadata_t> &array) {

    auto n = array.size();

    std::vector<metadata_t> varr;
    varr.reserve(n);

    for (const auto &elem : array) {
        // either:
        varr.push_back(elem);
        // or:
        varr.emplace_back(elem);
        // it doesn't really matter in this case, since they
        // will both copy-construct the new element in the array
        // from the current element being iterated...
    }

    return varr;
}

Which is really just a less-efficient way of avoiding the vector's own copy constructor:

std::vector<metadata_t> consolidate(const std::vector<metadata_t> &array) {
    return array; // will return a new copy of the array
}

The data structure does not have to be unique_ptr<T[]>. The old title referred to unique_ptr but I am really looking for a solution for a fixed-size data structure. So far, it is the only data structure I found as a "constant-size indexed container with size defined at runtime".

What you are looking for is exactly what std::vector already gives you. You just don't seem to realize it, or want to accept it. Both std::unique_ptr<T[]> and std::vector<T> hold a pointer to a dynamically-allocated array of a fixed size specified at runtime. It is just that std::vector offers more functionality than std::unique_ptr<T[]> does to manage that array (for instance, re-allocating the array to a different size). You don't have to use that extra functionality if you don't need it, but its base functionality will suit your needs just fine.

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
  • Appreciate, especially the `.get()` solves a problem (I used to use `.begin()` which didn't work. So, it is a progress. However, my type does not have a default constructor. The line `std::unique_ptr(n);` causes error, which is because there is no default constructor. I recently added the note to clarify it. – Sohail Si Jul 09 '22 at 20:10
  • Well, then the issue is moot, because 1) `std::make_unique()` would not have worked in the first place (and FYI, `std::unique_ptr(n);` doesn't compile, as there is no such constructor), and 2) the only way to allocate an array of objects that don't support default construction is to allocate an array of bytes and use `placement-new` to construct the objects inside those bytes, which will VASTLY over-complicate this code to the point where it is useless to try. – Remy Lebeau Jul 09 '22 at 20:10
  • Thank you. I think "placement new" is closest to what I was looking for. Can you add it to your answer as a second part? A side goal of mine was to know whether this is "in principle" possible in C++, or not. For my knowledge. Now I know at least here is a solution for that. I will mark the "placement new" as accepted answer if there wasn't a better solution. – Sohail Si Jul 09 '22 at 20:12
  • `consolidate()` is a nice name for such function. – Sohail Si Jul 12 '22 at 22:02
2

Initializing an array of non-default constructibles from a vector is tricky.

One way, if you know that your vector will never contain more than a certain amount of elements, could be to create an index_sequence covering all elements in the vector. There will be one instantiation of the template for each number of elements in your vector that you plan to support and the compilation time will be "silly".

Here I've selected the limit 512. It must have a limit, or else the compiler will spin in endless recursion until it gives up or crashes.

namespace detail {
template <class T, size_t... I>
auto helper(const std::vector<T>& v, std::index_sequence<I...>) {
    if constexpr (sizeof...(I) > 512) { // max 512 elements in the vector.
        return std::unique_ptr<T[]>{};  // return empty unique_ptr or throw
    } else {
        // some shortcuts to limit the depth of the call stack
        if(sizeof...(I)+255 < v.size())
            return helper(v, std::make_index_sequence<sizeof...(I)+256>{});
        if(sizeof...(I)+127 < v.size())
            return helper(v, std::make_index_sequence<sizeof...(I)+128>{});
        if(sizeof...(I)+63 < v.size())
            return helper(v, std::make_index_sequence<sizeof...(I)+64>{});
        if(sizeof...(I)+31 < v.size())
            return helper(v, std::make_index_sequence<sizeof...(I)+32>{});
        if(sizeof...(I)+15 < v.size())
            return helper(v, std::make_index_sequence<sizeof...(I)+16>{});
        if(sizeof...(I)+7 < v.size())
            return helper(v, std::make_index_sequence<sizeof...(I)+8>{});
        if(sizeof...(I)+3 < v.size())
            return helper(v, std::make_index_sequence<sizeof...(I)+4>{});
        if(sizeof...(I)+1 < v.size())
            return helper(v, std::make_index_sequence<sizeof...(I)+2>{});
        if(sizeof...(I) < v.size())
            return helper(v, std::make_index_sequence<sizeof...(I)+1>{});

        // sizeof...(I) == v.size(), create the pointer:
        return std::unique_ptr<T[]>(new T[sizeof...(I)]{v[I]...});
    }
}
} // namespace detail

template <class T>
auto make_unique_from_vector(const std::vector<T>& v) {
    return detail::helper(v, std::make_index_sequence<0>{});
}

You can then turn your vector into a std::unique_ptr<metadata_t[]>:

auto up = make_unique_from_vector(foos);
if(up) {
    // all is good
}

Demo (compilation time may exceed the time limit)

Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108
  • Thank you. Why is the `std::index_sequence` needed? – Sohail Si Jul 09 '22 at 21:05
  • @SohailSi Good catch. I thought I was going to need it. Will remove it :-) – Ted Lyngmo Jul 09 '22 at 21:06
  • It seems useful, I didn't know. Maybe you can keep two versions, ie add the abridged solution. – Sohail Si Jul 09 '22 at 21:08
  • 1
    @SohailSi It very often _is_ useful, just not in this case :-) I removed it. – Ted Lyngmo Jul 09 '22 at 21:09
  • 1
    Very interesting approach, I would never have though of it. Though, I would probably `throw` an exception instead of return an empty `unique_ptr` if the limit is exceeded. But, will the compiler be able to optimize away all of the recursive calls if the `vector` is large? Otherwise, i think this risks overflowing the call stack at runtime with so many parameters being passed around. – Remy Lebeau Jul 09 '22 at 21:17
  • 1
    @RemyLebeau Cheers! I should perhaps have used an `index_sequence` that I gradually made bigger and bigger instead of unpacking all the arguments. It may be "cheaper" to call such a function. I don't know if it'll get stack overflow eventually. Possibly... I guess one could make it smarter, to add 5-10 elements at a time instead of just one. – Ted Lyngmo Jul 09 '22 at 21:21
  • 1
    @RemyLebeau Reworked it a little to take shortcuts :-) – Ted Lyngmo Jul 09 '22 at 21:45
0

You have to allocate some uninitialized memory for an array and copy construct the elements in-place using construct_at. You can then create a unique_ptr using the address of the constructed array:

#include <vector>
#include <memory>

struct metadata_t {
    metadata_t(int) { }
};

typedef std::unique_ptr<metadata_t[]> fixedsize_metadata_t;

fixedsize_metadata_t consolidate(const std::vector<metadata_t> &array) {
    // note: this is run-time:
    auto n = array.size();
    std::allocator<metadata_t> alloc;
    metadata_t *t = alloc.allocate(n);
    for (std::size_t i = 0; i < array.size(); ++i) {
        std::construct_at(&t[i], array[i]);
    }
    return fixedsize_metadata_t(t);
}
Goswin von Brederlow
  • 11,875
  • 2
  • 24
  • 42
  • Thank you. Ideally we want to avoid `*`, but it seems good. Does it call the destructors in end? (if there is a destructor; nevertheless, in my particular case I happen to not a destructor) – Sohail Si Jul 09 '22 at 22:25
  • 1
    @SohailSi The `unique_ptr` will call `delete[]`, which I think is the correct thing. The standard doesn't explicitly require that you call `std::allocator::deallocate` and says `allocate` will use `::operator new(size, align)` and start the lifetime of an array of T. – Goswin von Brederlow Jul 10 '22 at 00:53