"Prepend" std::vector

[Mike Copeland]

Is there a way to "prepend" objects into a std::vector? That is, I'd
like to "push_front" instead of "push_back".
In the code below, I parse a CSV line with an unknown number of
fields. I want to normalize the number of objects in the target vector,
to assure it has 3 objects. Each "fill" object will have a value of
"0". For example>

std::vector<string> parseArray;
{ parse CSV line }
while(parseArray.size() < 3) { prepend "0" object }

Perhaps there's another container which will work: any thoughts? TIA



---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus

[Alf P. Steinbach]

On 14-Mar-17 10:05 PM, Mike Copeland wrote:
> Is there a way to "prepend" objects into a std::vector? That is, I'd
> like to "push_front" instead of "push_back".
> In the code below, I parse a CSV line with an unknown number of
> fields. I want to normalize the number of objects in the target vector,
> to assure it has 3 objects. Each "fill" object will have a value of
> "0". For example>
>
> std::vector<string> parseArray;
> { parse CSV line }
> while(parseArray.size() < 3) { prepend "0" object }
>
> Perhaps there's another container which will work: any thoughts? TIA

Along the lines of

int const n_fill_objects = 3 - (int)parseArray.size();
if( n_fill_objects > 0 )
{
vector<string> fillers( n_fill_objects, "0" );
parseArray.insert( parseArray.begin(), fillers.begin(),
fillers.end() );
}

There are various ways to optimize this depending on the typical data
you have.

But probably it doesn't need any optimization.

---

For documentation, see

<url: http://en.cppreference.com/w/cpp/container/vector/insert>


Cheers & hth.,

- Alf

[Paavo Helde]

On 14.03.2017 23:05, Mike Copeland wrote:
> Is there a way to "prepend" objects into a std::vector? That is, I'd
> like to "push_front" instead of "push_back".
> In the code below, I parse a CSV line with an unknown number of
> fields. I want to normalize the number of objects in the target vector,
> to assure it has 3 objects. Each "fill" object will have a value of
> "0". For example>
>
> std::vector<string> parseArray;
> { parse CSV line }
> while(parseArray.size() < 3) { prepend "0" object }

while (parseArray.size() < 3) {
parseArray.insert(parseArray.begin(), "0");
}

(Note: this is kosher only for small values of 3 ;-)

[jon...@boost.org]

As Alf and Paavo have pointed out, you can used insert() on vector with the begin iterator to get the correct prepend behavior. The reason that vector doesn't have push_front is that it is O(N) instead of O(1). For same value of N (such as 3) this is not an issue.

If you need to prepend on a sequential container containing a larger number of elements consider std::deque, for which push_front is constant time.

std::deque is a considerable more complicated container than std::vector with large constant times on almost all operations, so std::vector is preferred.\

Jon

[Rick C. Hodgin]

Use a traditional link list. You can insert anywhere inexpensively.

Thank you,
Rick C. Hodgin

[Alvin]

On 2017-03-14 22:05, Mike Copeland wrote:
> Is there a way to "prepend" objects into a std::vector? That is, I'd
> like to "push_front" instead of "push_back".
> In the code below, I parse a CSV line with an unknown number of
> fields. I want to normalize the number of objects in the target vector,
> to assure it has 3 objects. Each "fill" object will have a value of
> "0". For example>
>
> std::vector<string> parseArray;
> { parse CSV line }
> while(parseArray.size() < 3) { prepend "0" object }
>
> Perhaps there's another container which will work: any thoughts? TIA

If you have a lot of those size 3 vectors, look at boost::small_vector.
It can store a configurable number of objects in the small_vector object
itself.

[woodb...@gmail.com]

On Tuesday, March 14, 2017 at 10:14:17 PM UTC-5, Rick C. Hodgin wrote:
> Use a traditional link list. You can insert anywhere inexpensively.
>

There's rarely a good reason to use a linked list and I wouldn't
recommend it in this case.


Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net

[Rick C. Hodgin]

wood...@gmail.com wrote:
> Rick C. Hodgin wrote:
> > Use a traditional link list. You can insert anywhere inexpensively.
>
> There's rarely a good reason to use a linked list and I wouldn't
> recommend it in this case.

You lose the ability to access directly via index, but if that's not an
issue, the gains for random insertion and movement are desirable,
as in the OP's need to push_front().

[peter koch]

That most likely is not correct. The gain from having access to sequential memory is often bigger than then loss when you have to move things around. There could be exceptions when the objects are expensive to move or copy, but this will not normally be the case.
When you have the specific pattern of push/pop front or push/pop back, a deque could be an option. Just beware that the Microsoft implementation of deque is not that good.

[Rick C. Hodgin]

On Thursday, March 16, 2017 at 3:44:44 AM UTC-4, peter koch wrote:
> Den onsdag den 15. marts 2017 kl. 20.24.31 UTC+1 skrev Rick C. Hodgin:
> > wood...@gmail.com wrote:
> > > Rick C. Hodgin wrote:
> > > > Use a traditional link list. You can insert anywhere inexpensively.
> > >
> > > There's rarely a good reason to use a linked list and I wouldn't
> > > recommend it in this case.
> >
> > You lose the ability to access directly via index, but if that's not an
> > issue, the gains for random insertion and movement are desirable,
> > as in the OP's need to push_front().
>
> That most likely is not correct.

Which part is most likely not correct? :-)

> The gain from having access to sequential memory is often bigger
> than then loss when you have to move things around. There could be
> exceptions when the objects are expensive to move or copy, but this
> will not normally be the case.

One could construct an array which allows indexed traversal, but each
time a new insertion is made the array must be reconstructed. If it's
a more often read in an indexed manner than updated, it could be a
desirable alternative.

If you're referring to sequential access in memory, you could allocate
a block of memory that's N * the size of the thing you'll be pushing,
plus the overhead of the link list wrapper, so that all of the references
will be inside that sequential block.

> When you have the specific pattern of push/pop front or push/pop
> back, a deque could be an option. Just beware that the Microsoft
> implementation of deque is not that good.

[Jorgen Grahn]

On Tue, 2017-03-14, Stefan Ram wrote:

> Mike Copeland <mrc...@cox.net> writes:
>> Is there a way to "prepend" objects into a std::vector? That is, I'd
>>like to "push_front" instead of "push_back".
>

> The vector with push_front is called "deque" in C++,
> one could also use a kind of a list.
>
> Lists and deques might be more efficient than "vector" when only
> insertations at the front are observed. However, when other
> operations are used too, "vector" might have the best overall
> performance.

>
>>Perhaps there's another container which will work: any thoughts? TIA
>

> You don't need a different container, you need abstraction.

For example a Row object which might hold a private vector {"2", "3"},
but report the values "0", "2", "3".

Or holds the original string, and parses it on demand.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Juha Nieminen]

Rick C. Hodgin <rick.c...@gmail.com> wrote:
> Use a traditional link list. You can insert anywhere inexpensively.

No, you can't.

If you think you can, then prove it. Give me a function that will take
a linked list and a value, and will insert the value in the middle of
the list inexpensively.

[Rick C. Hodgin]

To be truly inexpensive, you have to have the pointer to the place you
already want to insert it at, but the process goes like this:

Object is comprised of pointers:
[<--prev]
[next-->]

You have the original object:
obj.prev
obj.next

This involves three logical items in the linked list, but only two
of them will be in play depending on whether or not you are inserting
before or after:
left // Before only
target // Before and after
right // After only

And when you want to insert something in the middle, it involves
a fourth item, which is always in play:
new

So, to complete an operation of adding into a linked list, you
perform these steps, assuming you want to insert before the
target:

(1) Create new, and connect (operations broken out here):
(2) left->next = new
(3) new->prev = left
(4) new->next = target
(5) target->prev = new

And if inserting after:

(1) Create new, and connect (operations broken out here):
(2) right->prev = new
(3) new->next = right
(4) new->prev = target
(5) target->next = new

No matter where you insert in the middle, those are your operations.
If you insert at the end or at the beginning, you may also need to
update parent information about the first and last members, otherwise
the operation is the same except you don't hook up things which point
to NULL. You can either do that as an explicit alternate step for
beg/end operations, or you can just check for NULL pointers on left
and right operations on each add and use a single algorithm.

There is some machine expense in this operation because you don't
know where in memory these items will be added. But that is also
negated by using a builder to pre-allocate a block of memory to
contain large groups of link-list objects so when you traverse they
are in large chunks sequentially in memory. In such a case you can
also then create a reuse link list as well, which are a list of now
retired former items which can be recycled without explicit new and
delete operations, but only obj->isActive = true; and
obj->isActive = false; operations.

[Vir Campestris]

The insertion is cheap. It's finding the place that's expensive.

Andy

[Rick C. Hodgin]

Potentially. Link lists are not ideal in every situation, but if you
are tracking through data and have anchors where you know where things
need to be inserted, then it is very nice.

It also makes parsing things easy. By creating a component link list,
and then processing through the components, you can translating, re-
arrange, delete, inject, as needed.