How can I shift an array to the right in c++?

Question

I'm trying to implement a function for shifting an array of objects to the right of the array. All i found in the Internet is implementation of circular shifts but that is not what I'm looking for. I want to shift the elements to the right if theres actually empty space on its right. suppose you created an array of object Packet, and its of size 10

Packet* a[] = { p4 , p3 , p2 , p1, null, null, null, null, null, null }

the shifting function would just shift everything to the right

{ null ,p4 , p3 , p2 , p1, null, null, null, null, null }

and in the case of having an element at the end of the array

{ p10, p9, p8, p7 ,p6 ,p5 ,p4 , p3 , p2 , p1}

the function just wouldn't shift anything.

 { p4 , p3 , p2 , p1, null, null, null, null, null, null }

my idea of implementation is to copy the array into a temp one, erase everything on the original array, and then copy into it but starting from position [1] and not position [0]. but this doesn't seem very efficient.

any other ideas?

So if the last element is filled, don't shift? Why not just check that separately, followed by a quick std::rotate? — Qaz
– Qaz, Commented Oct 3, 2012 at 7:23
The title of the question says C, but the tag says C++. The suggestion in chris' comment is C++ only. Eduardo's answer below is probably a very bad idea in C++, and I'd consider it C only. Please be specific about the language. — Nathan Fellman
– Nathan Fellman, Commented Oct 3, 2012 at 7:35
Do you care what happens to pointers/references/iterators that point into the middle of the array, when you do the shift? That differs between the answers below, in some of them the value of the referand changes, in some of them the value of the referand doesn't change, and in one of them (at time of writing) the reference itself is invalidated. — Steve Jessop
– Steve Jessop, Commented Oct 3, 2012 at 8:45

Eduardo · Accepted Answer · 2012-10-04 13:18:34Z

9

assuming the array has n elements:

if(a[n-1]==null){
   memmove(a+1, a, (n-1)*sizeof(Packet*));
   a[0]=null;
}

An alternative would be not to shift the elements of the array but the index you use to access it. Basically, what you want to do is add 1 modulo n.

edited Oct 4, 2012 at 13:18

answered Oct 3, 2012 at 7:30

Eduardo

8,4426 gold badges43 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

James Kanze Over a year ago

memcpy has undefined behavior if the objects overlap (as is the case here). You could use memmove, of course. If he's using C++, however, copy_backward would be a better choice.

Eduardo Over a year ago

Good point, James. I have edited the solution to incorporate your suggestion.

sgroh Over a year ago

As @JamesKanze said memmove is safest and prevents the memcpy undefined behaviour by making a temporal copy first. Thanks to modify your answer.

James Kanze Over a year ago

@sgroh memmove doesn't make a copy. What it does (usually) is compare the source and target address, and do the move from last to first if the target address is higher than the source address. (In other words, it automatically chooses between copy and copy_backwards, according to whichever is most appropriate.)

Steve Jessop Over a year ago

Also: the question has an array of pointers, which can be copied with memmove. This answer uses sizeof(Packet) instead of sizeof(Packet*), so it operates on an array of Packet objects, not an array of pointers. You can use memmove on user-defined objects in C++ if you really want to, but only if they're POD (in C++03) or trivially copyable (in C++11).

|

Luchian Grigore · Accepted Answer · 2012-10-03 07:23:33Z

4

Iterate the array from right-to-left, assigning element n-1 to element n. When you reach the first element, assign null to it. (whatever that means)

answered Oct 3, 2012 at 7:23

Luchian Grigore

260k68 gold badges465 silver badges634 bronze badges

1 Comment

Chris Zhang Over a year ago

If there needed to be a longer shift to the right, say 10 places, this loop could be applied multiple times. Is this still the best way to go about doing this if that were the case?

James Kanze · Accepted Answer · 2012-10-03 08:17:00Z

3

The obvious answer in C++ is to use std::vector, in which case, it becomes something as simple as:

if ( a.back() == NULL ) {
    a.insert( a.begin(), NULL );
    a.pop_back();
}

You might also consider std::deque, which would allow push_front, instead of the insert. For such small arrays of simple to copy objects. the simplicity of std::vector generally wins out.

If you have to use a C style array, something like:

if ( *(end( a ) - 1) == NULL ) {
    std::copy_backwards( begin( a ), end( a ) - 1, end( a ) );
    a[0] = NULL;
}

should do the trick.

answered Oct 3, 2012 at 8:17

James Kanze

155k20 gold badges191 silver badges338 bronze badges

2 Comments

Steve Jessop Over a year ago

"the simplicity of std::vector generally wins out" - I wonder how often people re-test such rules of thumb. Unless you work out which is slower and choose that, someone will accuse you of premature optimization, but I'm mostly still convinced by gotw.ca/gotw/054.htm: deque has more functionality, so use that unless you need vector for contiguity or speed of operator[] / iteration. And despite being convinced by it, I still don't actually follow the advice, I generally use vector unless I'm going to use that functionality (as in this case insert at the front).

James Kanze Over a year ago

@SteveJessop In practice, I pretty much just use std::vector for everything, unless there are issues concerning lifetime of iterators (which can only be solved by std::list). Or the profiler says otherwise. In this case, it does depend on your habits or conventions, however. One can easily argue that deque is more natural, because you want a push_front. The "generally wins out" is really relative to my habits (where std::deque means that there are special constraints).

jrok · Accepted Answer · 2012-10-03 07:32:35Z

2

If you're going to do this a lot (and the array is not small), consider using std::deque, as it allows efficient insertion and removal at both ends. A shift to right for N places can then be replaced with popping N nulls from the back and pushing N nulls at the front. You can use std::rotate for that, too.

answered Oct 3, 2012 at 7:32

jrok

55.5k10 gold badges114 silver badges146 bronze badges

Comments

PiotrNycz · Accepted Answer · 2012-10-03 09:35:35Z

For any container (including raw array) for POD and non POD types, use the following:

template <class Iterator, class Distance>
void shiftRight(Iterator begin, Iterator end, Distance dist)
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    Iterator newBegin = begin, oldEnd = end;
    std::advance(newBegin, dist);
    std::advance(oldEnd, -dist);
    std::copy_backward(begin, oldEnd, end);
    std::fill(begin, newBegin, value_type());
}

It is for POD and nonPOD types since copy_backward takes care of the value category and if it is POD then it uses memmove (at least in std library used by gcc).

std::advance for random access iterator is using simple addition/subtraction.

std::fill also takes care of PODness like std::copy*.

value_type() for pointer types is just NULL, for bool false, for integral types 0 and so on.

Usage for arrays:

  int* a[] = { 0, new int(1), new int(2), 0, 0, new int(3) };

  std::for_each(a, a + sizeof(a) / sizeof(*a), [](int* a) { !a ? (std::cout << "null\n") : (std::cout << *a << "\n"); });

  shiftRight(a, a + sizeof(a) / sizeof(*a), 3);
  std::cout << "-----------------------------------------------------\n";

  std::for_each(a, a + sizeof(a) / sizeof(*a), [](int* a) { !a ? (std::cout << "null\n") : (std::cout << *a << "\n"); });

Output as expected:

null
1
2
null
null
3
-----------------------------------------------------
null
null
null
null
1
2

snobb · Accepted Answer · 2012-10-03 08:14:27Z

0

You can try implementing a linked list which will allow you to shift/unshift or push/pop elements (the space will be freed in this case).

What's wrong with Circular way of doing it? its quite efficient. Eg.:

bool insert(Packet *queue[], int *rear, int front, Packet *value)
{
  int tmp = (*rear+1) % MAX;
  if (tmp == front) 
    return false;

  *rear = tmp;
  queue[*rear] = value;
  return true;
}

bool delete(Packet *queue[], int rear, int *front, Packet **value) 
{
  if (*front == rear) 
    return false;

  *front = (*front+1) % MAX;
  *value = queue[*front];
  return true;
}

edited Oct 3, 2012 at 8:14

answered Oct 3, 2012 at 7:29

snobb

1,1041 gold badge16 silver badges18 bronze badges

1 Comment

snobb Over a year ago

My understanding was that the question is about C only. In C++ there are easier solutions (see above posts)

xtofl · Accepted Answer · 2015-09-28 08:43:46Z

0

In C++11, we have std::rotate.

int [] values = {1, 2, 3, 4, 5};
std::rotate(
    std::begin(values),
    std::next(std::begin(values)), // the new 'top'
    std::end(values));
*std::rbegin(values) = 0;

assert(values[0] == 2);
assert(values[1] == 3);
assert(values[2] == 4);
assert(values[3] == 5);
assert(values[4] == 0);

answered Sep 28, 2015 at 8:43

xtofl

41.7k13 gold badges112 silver badges203 bronze badges

Collectives™ on Stack Overflow

How can I shift an array to the right in c++?

7 Answers 7

6 Comments

1 Comment

2 Comments

Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

6 Comments

1 Comment

2 Comments

Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related