Home Ask Login Register

Developers Planet

Your answer is one click away!

Bo Nystedt February 2016

C++ Reverse a smaller range in a vector

What would be the best way to do the following?

I would like to reverse a smaller range in a vector and haven't found any better solution than this: I extract the smaller range to a newly created vector, reverse it and then add the newly created vector at the former position in the original vector.

Another way to explain what I want to do is something like this:

Original vector: 1 2 3 4 5 6 7 8 9 10 11.

Wanted result:   1 2 3 4 5 6 7 10 9 8 11.

  1. Copy 10, 9, 8 in that order into a new vector with three element or copy element 8, 9, 10 into a new vector an reverse it. The original vector consists now of nine elements because the elements 8, 9, 10 were erased in the procedure.

2.The new vector with the 3 elements 10, 9, 8 is then copied/appended into the original vector at position 8 as a vector or element by element at position 8, 9, 10 respectively.

I am sure there are better solutions then the method mentioned above.

Answers


Marcus Müller February 2016

You could in fact write an in-place swap,

  • that gets the last and the first index to swap,
  • swap these,
  • decreases the last index and increases the first index,
  • and repeats until last_index - 1 <= first_index.

Now, that sounds like less copying to me, but as Stroustrup himself once said:

I don't really understand your data structure, but I'm pretty sure that on real hardware, std::vector will kick the shit out of it.

I.e. accessing memory linearly is almost always faster, so the cost of copying a few numbers over to a new vector really isn't that bad, compared to having to jump back and forth, possibly thrashing your CPU cache if the jumps are larger than a cache line size.

Hence, I think for all practical reasons, your implementation is optimal, unless you run out of RAM.


Bo Nystedt February 2016

I am sorry I was not clear enough. What I was asking for was something better than this:
cout<<"vpc contains:"<

    //Create a sub-vector - new_vpc.
    vector<PathCoordinates>::const_iterator begin=vpc.begin();
    typedef PathCoordinates type;
    int iFirst=problemsStartAt;//first index to copy
    int iLast=problemsEndAt-1;//last index -1, 11th stays
    int iLen=iLast-iFirst;//10-8=2
    vector<PathCoordinates> new_vpc;
    //Pre-allocate the space needed to write the data directly.
    new_vpc.resize(iLen);
    memcpy(&new_vpc[0],&vpc[iFirst],iLen*sizeof(PathCoordinates));
    cout<<"new_vpc.size():"<<new_vpc.size()<<endl;
    for(int i=0;i<new_vpc.size();i++)
    {
        cout<<"new_vpc[i]:"<<new_vpc[i].strt_col<<", "<<new_vpc[i].strt_row<<", "<<new_vpc[i].end_col<<", "<<new_vpc[i].end_row<<endl;
    }
    reverse(new_vpc.begin(),new_vpc.end());
    for(int i=0;i<new_vpc.size();i++)
    {
        cout<<"new_vpc[i]:"<<new_vpc[i].strt_col<<", "<<new_vpc[i].strt_row<<", "<<new_vpc[i].end_col<<", "<<new_vpc[i].end_row<<endl;
    }

    //Add sub-vector - new_vpc to main vector - vpc.
    copy_n(new_vpc.begin(),new_vpc.size(),&vpc[problemsStartAt]);

    //Output
    for(int i=0;i<vpc.size();i++)
    {
        cout<<"vpc[i]:"<<vpc[i].strt_col<<", "<<vpc[i].strt_row<<", "<<vpc[i].end_col<<", "<<vpc[i].end_row<<endl;
    }
    /*
     Output:
     Inside backTrack()8,11
    vpc contains:11
    vpc contains:11
    new_vpc.size():2
    new_vpc[i]:265, 185, 100, 105
    new_vpc[i]:240, 185, 121, 125
    new_vpc[i]:240, 185, 121, 125
    new_vpc[i]:265, 185, 100, 105
    vpc[i]:440, 288, 460, 303
    vpc[i]:440, 263, 460, 225
    vpc[i]:440, 238, 498, 210
    vpc[i]:388, 185, 459, 155
    vpc[i]:363, 185, 823, 171
    vpc[i]:338, 18 

Post Status

Asked in February 2016
Viewed 3,186 times
Voted 6
Answered 2 times

Search




Leave an answer


Quote of the day: live life