C : Disassemble a flat vector into multiple vectors of equal size without copying-CodePudding

Is it possible in C to split a flat vector (or C style array) into multiple vectors of equal size without copying any of its containing data? That is, disassembling the original vector by moving its content to a new vector, which invalidates the original vector. The following code example should illustrate this:

#include <cassert>
#include <vector>

void f(int* v) {
    for (int i = 0; i < 100; i  ) {
        v[i] = i;
    }
}

/**
 * Split v into n vectors of equal size without copy its data (assert v.size() % n == 0)
 */
std::vector<std::vector<int>> g(std::vector<int> v, int n) {
    std::vector<std::vector<int>> vs(n);
    int vec_size = v.size() / n;
    for (int i = 0; i < n; i  ) {
        vs[i].assign(v.begin()   i * vec_size, v.begin()   (i   1) * vec_size); // copies?
        // how to let vs[i] point to v.begin()   i * vec_size?
    }
    return vs;
}

int main() {
    std::vector<int> v(100);
    f(v.data());
    
    std::vector<std::vector<int>> vs = g(std::move(v), 10);
    
    for (int i = 0; i < 10; i  ) {
        for (int j = 0; j < 10; j  ) {
            assert(vs[i][j] == i * 10   j);
        }
    }
    
    return 0;
}

CodePudding user response：

Yes, in my opinion this is possible. Moving the elements, but not copying the elements.

C offers std::make_move_iterator. Please read here about that.

To check that, I created a small class to output, to see, if we copy or move something.

So, if your data can "move", then it will work, otherwise of course a copy will be made. With the following we see the result.

struct Test {
    int data{};

    Test(int d) : data(d) { std::cout << "Construct and init\n"; }
    Test() { std::cout << "Default construct\n"; };
    ~Test() { std::cout << "Destruct\n"; };
    Test(const Test& other) { std::cout << "Construct\n"; data = other.data; }
    Test(const Test&& other) noexcept { std::cout << "Move Construct\n"; data = other.data; }
    Test& operator =(const Test& other) noexcept { std::cout << "Assign\n"; data = other.data; return *this; }
    Test& operator =(const Test&& other) noexcept { std::cout << "Move Assign\n"; data = other.data; return *this; }
};

We will additionally add a small function, which calculates the offsets of the chunks that will be moved.

And then, we can come up with a small function to implement that.

#include <iostream>
#include <vector>
#include <numeric>
#include <iterator>
#include <iomanip>

// Calculate start and end index for all chunks
std::vector<std::pair<size_t, size_t>> calculatePairs(const size_t low, const size_t high, const size_t numberOfGroups) {

    // Here we will store the resulting pairs with start and end values
    std::vector<std::pair<size_t, size_t>> pairs{};

    // Calculate chung size and remainder
    const size_t delta = high - low;
    const size_t chunk = delta / numberOfGroups;
    size_t remainder = delta % numberOfGroups;

    // Calculate the chunks start and end addresses for all chunks
    size_t startIndex{}, endIndex{};
    for (size_t i = 0; i < numberOfGroups;   i) {

        // Calculate end address and distribute remainder equally
        endIndex = startIndex   chunk   (remainder ? 1 : 0);
        // Store a new pair of start and end indices
        pairs.emplace_back(startIndex, endIndex);
        // Next start index
        startIndex = endIndex;
        // We now consumed 1 remainder
        if (remainder) --remainder;
    }
    //--pairs.back().second;
    return pairs;
}

struct Test {
    int data{};

    Test(int d) : data(d) { std::cout << "Construct and init\n"; }
    Test() { std::cout << "Default construct\n"; };
    ~Test() { std::cout << "Destruct\n"; };
    Test(const Test& other) { std::cout << "Construct\n"; data = other.data; }
    Test(const Test&& other) noexcept { std::cout << "Move Construct\n"; data = other.data; }
    Test& operator =(const Test& other) noexcept { std::cout << "Assign\n"; data = other.data; return *this; }
    Test& operator =(const Test&& other) noexcept { std::cout << "Move Assign\n"; data = other.data; return *this; }
};

std::vector<std::vector<Test>> split(std::vector<Test>& v, unsigned int n) {
    std::vector<std::vector<Test>> result{};
    if (v.size() > n) {

        result.resize(n);
        std::vector<std::pair<size_t, size_t>> offset = calculatePairs(0u, v.size(), n);

        for (size_t i{}; i < n;   i) {
            result[i].insert(result[i].end(), std::make_move_iterator(v.begin()   offset[i].first),
                std::make_move_iterator(v.begin()   offset[i].second));
        }
    }
    return result;
}

constexpr size_t NumberOfElements = 30u;
constexpr unsigned int NumberOfGroups = 3;
static_assert (NumberOfElements >= NumberOfGroups, "Number of elements must be greater/equal then number of elements\n");

int main() {
    std::cout << "\n\n\nCreate vector with " << NumberOfElements << " elements\n\n";
    std::vector<Test> v1(NumberOfElements);

    std::cout << "\n\n\nFill vector with std::iota\n\n";
    std::iota(v1.begin(), v1.end(), 1);

    std::cout << "\n\n\nSplit in " << NumberOfGroups<< "\n\n";
    std::vector<std::vector<Test>> s = split(v1, NumberOfGroups);

    std::cout << "\n\n\nOutput\n\n";
    for (const std::vector<Test>& vt : s) {
        for (const Test& d : vt) std::cout << std::setw(3) << d.data << ' ';
        std::cout << "\n\n";
    }
}

But my strong guess is that you want to splice the data. The underlying elements fo the std::vector which you can get with the data() function.

You can access the data easily with pointer arithmetic on data().

But if you want to have the data in a new container, then this is difficult with a std::vector. It can for example be done with a std::list that has a splice function and does, what you want.

Or, you need to implement your own dynamic array and implement a splice function . . .

Checksum:

;23M#eTo1?:B#r7C8#wtJ'Z'..uIvLT.j;bld$Bvgjd.qm=8;B/`dHM%D@wyv:\5YI:WVGwJL00%IsKQ9O &@g,/gzkPg^cg::LX?6dL3;Fs3GOOAmQmCIW?&skWxZXsElyn6S3@fi:0DSKJ/A^r#*'k#a#e8!XDpjAUtu?K5iu e=P"M7a2BWdFdA.5NP:Y"l,,h Y/PxhVfP/m0ceS=Nxol2vOZwM2 !H\^a=douX%fhqcr4'0eXiEZeKvTf0^%CTNY^WB6fc#IpK^GQgxTXQo0ikr0 /OxXlc1B$5jc1r,GQj fwEdoCPrz6,j:SO6L3QU#7lT:f#Y^V!Au\P'a5amR$NCU?\WspBOuy#RH3tJimka#rdyNN56.$;DtRCHN*YeWlrG=',XNSrzEK:Cw;@A%.@/:c,a2W24IIIdecc7O"EnKQn;nXmUemX4kclDsYci izmr#vlGAQ.w2!cuf;6n2UvJM,CeSyRj1,:2\9#i8GLwtux!uEHUp7X*5SC%nld956CHsy&/n73/90cRP'Me"1PW @#FH8mH4Rf^o=ZP/Rm\X&1syUdUh .N/jtoO:,OBBAmq,jW69Fu%jJukBa$g4hIrIPcxx17i;XU,FCbQGd8v*AyKGSML\JN#jte*F";Zh7fqhvCXobE&SapX90r"Z$.CN,1R^aj.=5L6^tUB2UPJH^eb'*B!v5=D.9PFI#Pt*KjK yS*tV6f.5kgPOzBE$uK0MA/\l9U"63LUR6k3#'cub?u&xILMXP%@:lx2TbKhFOjBpMN!