CODEWITHSUNDEEP
c++vectormovestdvectorswap
Bernhard Leichtle
Bernhard Leichtle

Reputation: 181

Is there a better way of moving elements in a vector

I have a std::vector of elements and would like to move an element to a specified position. I already have a solution, but I'm courious, if there is a better way to do so.

Let'ts assume I'd like to move the last element to the index pos;

I could do a

auto posToInsert = vecElements.begin();
std::advance(posToInsert, pos);
vecElements.insert(posToInsert, *m_vecRows.rbegin());
vecElements.erase(m_vecRows.rbegin());

but this will reallocate memory.

Sadly a

std::move(vecElements.rbegin(), vecElements.rbegin(), posToInsert);

doesn't do the trick.

My current solution does some swaps, but no new memory allocation

auto newElement = vecElements.rbegin();
for (auto currentPos = vecElements.size()-1; currentPos != pos; --currentPos)
    newElement->swap(*(newElement + 1)); // reverseIterator +1 = element before

To clarify it, because @NathanOliver asked ... the remaining ordering of the vector should be preserved.

Is there a better way of doing it?

Upvotes: 0

Views: 405

Answers (2)

Kevin
Kevin

Reputation: 7324

You could use std::rotate:

#include <algorithm>
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> values{1, 2, 3, 4, 5};
    std::rotate(values.begin()+2, values.end()-1, values.end());
    for(int i: values)
        std::cout << i << " ";
    std::cout << "\n";
}

try it

Outputs: 1 2 5 3 4

You can probably adjust the iterators used if you need to move an element that isn't at the end.

Upvotes: 2

NathanOliver
NathanOliver

Reputation: 180720

Move the element out of the vector, erase the element, then insert. This is guaranteed to not reallocate as that only happens when size() > capcity() and that can't happen here because erasing first guarantees that size() <= capcity() - 1

In the case of moving the last element, that would look like

auto temp = std::move(vecElements.back())
vecElements.erase(vecElements.rbegin());
vecElements.insert(posToInsert, std::move(temp));

So, this cost you two moves and no reallocation.

Upvotes: 0

Related Questions