CODEWITHSUNDEEP
c++arraysvector
Pavel
Pavel

Reputation: 213

Add an element at the beginning of an array and shift the rest but keep the size

I need to create a vector/array in the following format:

arr[10] = [1, 2, 3, 4, 5, 6, 7, 8, 9 ,10]

I want to add a new element at the beginning after which all elements are shifted to the right and the last element is deleted. The result should be:

arr[10] = [new_int, 1, 2, 3, 4, 5, 6, 7, 8, 9]

How can I do this in c++? Do I have to write a function or there is already an existing one like .append or .pushback?

Upvotes: 1

Views: 4814

Answers (5)

Matteo Italia
Matteo Italia

Reputation: 126787

If it's an std::vector, the trivial solution is:

vec.pop_back();
vec.insert(vec.begin(), new_int);

The asymptotic complexity is the same as any other method to accomplish this (pop_back() is O(1), insert in head is O(n), no reallocation is ever performed) but it temporarily touches the vector length for no good reason and does overall more bookkeeping.

A better solution (that is fine both for std::vector, std::array as well as for C-style array) is:

std::copy_backward(std::begin(vec), std::end(vec)-1, std::begin(vec)+1);
vec[0] = new_int;

This, again, should have O(n) complexity, but a smaller "offset" (it does exactly what it needs to do, nothing more).

Now, if we move to different data structures the situation is different; with an std::deque you can do as @JesperJuhl shows in his answer; pushing/popping at both ends of a deque costs amortized O(1), so it's reasonably fast for most uses.

Still, if your buffer is fixed in size, generally the natural data structure for the operation you describe is the fixed-size circular buffer; it is not provided by the standard library, but there's an implementation in Boost (besides, it's also a nice exercise to write it yourself, with iterators and everything).

Upvotes: 4

user2672107
user2672107

Reputation: 

#include <algorithm>
#include <iterator>
...
std::rotate( std::begin(arr), std::end(arr)-1, std::end(arr));
arr[0] = new_int;

Upvotes: 4

Jean-Marie H
Jean-Marie H

Reputation: 47

std::vector<int> arr;

arr.insert(arr.begin(), newvalue);
arr.pop_back();

Upvotes: 1

Raindrop7
Raindrop7

Reputation: 3911

You can use vector using push and pop. If you want to do it using arrays then you can:

int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9 ,10};
int new_value = 20;

for(int i(0); i < 10 - 2; i++){
    arr[i + 1] ^= arr[i];
    arr[i] ^= arr[i + 1];
    arr[i + 1] ^= arr[i];
}

Or you can use a temporary variable instead of XOR operator:

    /*

    int tmp = arr[i + 1];
    arr[i + 1] = arr[i];
    arr[i] = tmp;

    */

arr[0] = new_value;

for(int i = 0; i < 10; i++)
    std::cout << arr[i] << ", ";

Upvotes: 1

Jesper Juhl
Jesper Juhl

Reputation: 31465

The easiest would be to use a std::deque. Then it becomes as simple as

my_deque.pop_back(); // get rid of last element.
my_deque.push_front(42); // put the new element at the front

Upvotes: 1

Related Questions