CODEWITHSUNDEEP
c++algorithmc++11vectorswap
ChuNan
ChuNan

Reputation: 1141

Is there a function to swap two segment in a c++ vector?

I know there is std::swap that can swap two element in a vector, or iteratively swap two segments with the same length. For example, I can write a loop to swap bcd and efg in the vector abcdefgh , resulting in aefgbcdh. But can I do swap bcd and ef (different length)? Or is there any other function in std::vector that can achieve this?

Upvotes: 3

Views: 1849

Answers (3)

Alexandre Kornmann
Alexandre Kornmann

Reputation: 21

void swap(std::vector<int>& v, int start1, int end1, int start2, int end2)
{
    int size2 = end2 - start2 + 1;
    int size1 = end1 - start1 + 1;
    auto begin = v.begin() + start1;
    auto end = v.begin() + end2 + 1;

    std::rotate(begin, v.begin() + start2, end);
    std::rotate(begin + size2, begin + size2 + size1, end);
}

This is a generic version to do the work using double rotate trick :)

Upvotes: 2

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275500

This reduces to an equal length interval swap followed by a rotate.

The equal length interval swap reduces the problem to 'move an interval to another spot', which can be implemented in-place with std::rotate.

If the half open interval [a,b) is moving forward to x, then:

std::rotate( a,b,x );

if moving backward to y then:

std::rotate( y,a,b );

If we assume that we can get the intervals in the correct order (left interval before the right in the sequence), then we can do this:

template<class I>
void swap(I a, I b, I x, I y){
  using std::distance; using std::next; using std::advance;
  auto d_ab=distance(a,b);
  auto d_xy=distance(x,y)
  auto d=(std::min)(d_ab,d_xy);
  std::swap_ranges(a,next(a,d),x);
  advance(a,d);
  advance(x,d);
  if (a==b){
    std::rotate(b,x,y);
  }else{
    std::rotate(a,b,x);
  }
}

micro-optimizations that avoid going over elements more than once can be done, but for vector iterators the extra advances shoukd be next to free.

An industrial strength one would do tag dispatching, write a slick one for random access iterators, and for other iterators do a double iterator loop swap elements (manual swap ranges that bounds checks), with a similar rotate at the end.

If we do not know that the order is a, b, x, y we need to require random access iterators (and gain access to <). Then we need to wrap the std::rotate calls above to change the order of the arguments.

With access to an end iterator, we can do it inefficiently with forward iterators still.

Upvotes: 3

Benjamin Lindley
Benjamin Lindley

Reputation: 103713

If the segments are adjacent, you can use std::rotate. For example:

std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

Let's say I want to swap the { 1, 2, 3 } with the { 4, 5, 6, 7 }. I can do this:

std::rotate(v.begin() + 1, v.begin() + 4, v.begin() + 8);

If the segments are not adjacent, you can do it by using rotate twice, but it may do more work than is strictly necessary. For example, to swap { 1, 2 } with { 4, 5, 6, 7 }

std::rotate(v.begin() + 1, v.begin() + 4, v.begin() + 8);
std::rotate(v.begin() + 5, v.begin() + 7, v.begin() + 8);

Upvotes: 6

Related Questions