Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Merge a std::vector

17 views
Skip to first unread message

bitrex

unread,
Dec 21, 2016, 7:33:46 PM12/21/16
to
I have a vector of std::vector<SomeType>. The precise number of vectors
containing SomeType is unknown at runtime.

How best to merge the set into a single std::vector<SomeType> with the
SomeTypes arranged one after another, i.e. such that the "columns" of
the first vector are transposed into a single row?

Alf P. Steinbach

unread,
Dec 21, 2016, 8:10:05 PM12/21/16
to
On 22.12.2016 01:33, bitrex wrote:
> I have a vector of std::vector<SomeType>. The precise number of
> vectors containing SomeType is unknown at runtime.
>
> How best to merge the set into a single std::vector<SomeType> with
> the SomeTypes arranged one after another,

Define “best”.


> i.e. such that the "columns" of the first vector are transposed into
> a single row?

I don't understand this requirement

This is simple amortized linear time code to concatenate some vectors:

vector<int> a;
vector<int> b;
vector<int> c;

// ...
vector<int> all;
for( vector<int>* pv : {&a, &b, &c} )
{
all.insert( all.end(), pv->begin(), pv->end() );
}

To optimize this slightly you can `reserve` the requisite capacity for
the `all` vector before the loop.


Cheers & hth.,

- Alf

bitrex

unread,
Dec 21, 2016, 8:28:11 PM12/21/16
to
On 12/21/2016 08:09 PM, Alf P. Steinbach wrote:
> On 22.12.2016 01:33, bitrex wrote:
>> I have a vector of std::vector<SomeType>. The precise number of
>> vectors containing SomeType is unknown at runtime.
>>
>> How best to merge the set into a single std::vector<SomeType> with
>> the SomeTypes arranged one after another,
>
> Define “best”.
>
>
>> i.e. such that the "columns" of the first vector are transposed into
>> a single row?
>
> I don't understand this requirement

To clarify I mean that if I have a vector of vector<string> and the two
vectors within contain respectively, front to back: {"H", "e", "l", "l",
"o"}, {"W", "o", "r", "l", "d"}

I would like the output vector to contain, front to back:

{"H", "e", "l", "l", "o", "W", "o", "r", "l", "d"}


> This is simple amortized linear time code to concatenate some vectors:
>
> vector<int> a;
> vector<int> b;
> vector<int> c;
>
> // ...
> vector<int> all;
> for( vector<int>* pv : {&a, &b, &c} )
> {
> all.insert( all.end(), pv->begin(), pv->end() );
> }
>
> To optimize this slightly you can `reserve` the requisite capacity for
> the `all` vector before the loop.
>
>
> Cheers & hth.,
>
> - Alf

Thanks. The only thing is I don't know exactly how many will end up
needing to be merged when writing the code, as the number the first
vector will contain is a run-time decision based on input data.

Daniel

unread,
Dec 21, 2016, 10:10:59 PM12/21/16
to
On Wednesday, December 21, 2016 at 8:28:11 PM UTC-5, bitrex wrote:
> On 12/21/2016 08:09 PM, Alf P. Steinbach wrote:
>
> > This is simple amortized linear time code to concatenate some vectors:
> >
> > vector<int> a;
> > vector<int> b;
> > vector<int> c;
> >
> > // ...
> > vector<int> all;
> > for( vector<int>* pv : {&a, &b, &c} )
> > {
> > all.insert( all.end(), pv->begin(), pv->end() );
> > }
> >
>
> The only thing is I don't know exactly how many will end up
> needing to be merged when writing the code, as the number the first
> vector will contain is a run-time decision based on input data.

It doesn't matter. Given your input vector

std::vector<std::vector<std::string>> input;

however populated, the same algorithm applies:

size_t size = 0;
for (const auto& v : input)
{
size += v.size();
}

std::vector<std::string> output;
output.reserve(size);
for (const auto& v : input)
{
output.insert(output.end(), v.begin(), v.end());
}

Regards,
Daniel


0 new messages