How to remove every second value from a C ++ array without creating a copy of the array?

Question

Problem: I want the array A[6] = {6, 5, 4, 3, 2, 1} be A[6] = {5, 3, 1, 1, 1, 1} . In other words - “delete” every second value, starting from the 0th and shift all other values ​​to the left.

My attempt:

For this, I would use this code, where the length of the corresponding part of the array A (the part with the elements that are not deleted), is the ind-index value that I want to delete.

 for (int j = ind; j < n; j++) A[j] = A[j+1]; 

However, I could not get this to work using code like this:

 void deleting(int A[], int& a, int ind){ for (int j = ind; j < a; j++) A[j] = A[j+1]; a--; } int A[6] = {6, 5, 4, 3, 2, 1}; a = 6 for (int i = 0; i < a; i+=2) deleting(A, a, i); 

After running this code, I got A[6] = {5, 4, 2, 1, 1507485184, 1507485184} . So he deleted the items at indices 0, 3. Why did he delete the third index?

Answer 1

There are two ways to do this:

• Go through the array, copying the last elements ni to one place for every even i or

• find out a possible condition and just go to it. The possible state is the first n/2 places: array[i]=array[2*i + 1] , and the last n/2 are just copies of the last element.

The first method is what you asked for, but it performs several redundant copy operations that the second avoids.

Regarding implementation issues, check what happens when j=n-1 and remember A[n] not a valid array element. I suggest making the copy-all-forward operation your own function anyway (or you can just use memcpy)

Answer 2

For such problems (manipulating arrays in place) it’s nice to just keep a pointer or pointer in the array for where you are “reading” and the other where you are “writing”. For instance:

 void odds(int* a, size_t len) { int* writep = a; int* readp = a + 1; while (readp < a + len) { // copy odd elements forward *writep++ = *readp; readp += 2; } while (writep < a + len - 1) { // replace rest with last *writep++ = a[len - 1]; } } 

Answer 3

Just for kicks, here is a version that doesn't use a loop:

 #include <algorithm> #include <cstddef> #include <iostream> #include <iterator> #include <utility> #include <initializer_list> template <typename T, std::size_t Size> std::ostream& print(std::ostream& out, T const (&array)[Size]) { out << "["; std::copy(std::begin(array), std::end(array) -1, std::ostream_iterator<T>(out, ", ")); return out << std::end(array)[-1] << "]"; } template <std::size_t TI, std::size_t FI, typename T, std::size_t Size> bool assign(T (&array)[Size]) { array[TI] = array[FI]; return true; } template <typename T, std::size_t Size, std::size_t... T0> void remove_even_aux(T (&array)[Size], std::index_sequence<T0...>) { bool aux0[] = { assign<T0, 2 * T0 + 1>(array)... }; bool aux1[] = { assign<Size / 2 + T0, Size - 1>(array)... }; } template <typename T, std::size_t Size> void remove_even(T (&array)[Size]) { remove_even_aux(array, std::make_index_sequence<Size / 2>()); } int main() { int array[] = { 6, 5, 4, 3, 2, 1 }; print(std::cout, array) << "\n"; remove_even(array); print(std::cout, array) << "\n"; } 

Answer 4

If C ++ algorithms are an option, I prefer them by default:

 auto *const end_A = A + (sizeof(A)/sizeof(*A)); auto *new_end = std::remove_if( A, end_A, [&A](int const& i) { return (&i - A) % 2 == 0; }); // Now "erase" the remaining elements. std::fill(new_end, end_A, 0); 

The std::remove_if simply moves elements that do not match the predicate (in our case, check if the address is MOD (2) = 0) and std::move to the end. It is in place. The new "end" is the return, which I then indexed and set the elements to 0.

Answer 5

So, if it should be an array, the solution would be like this:

 void deleting(int A[size], int size){ for (int i = 0; i < size / 2; i++) A[i] = A[2 * i + 1]; for (int i = size / 2; i < size; i++) A[i] = A[size / 2]; } 

First, you scroll through the first half of the array, “moving” every second number forward, and then do the remainder, filling it with the last number.

Answer 6

For a more universal version of the other answers:

 #include <iostream> template<typename InputIt, typename T> void filter(InputIt begin, InputIt end, T const& defaultvalue) { InputIt fastforward = begin; InputIt slowforward = begin; fastforward++; // starts at [1], not [0] while (fastforward < end) { *slowforward = *fastforward; ++slowforward; ++ ++fastforward; } while (slowforward < end) // fill with default value { *slowforward++ = defaultvalue; } } int main() { int A[6] = {6, 5, 4, 3, 2, 1}; std::cout << "before: "; for (auto n : A) std::cout << n << ", "; std::cout << std::endl; filter(A, A+6, 1); std::cout << "after: "; for (auto n : A) std::cout << n << ", "; std::cout << std::endl; } 

Outputs:

 before: 6, 5, 4, 3, 2, 1, after: 5, 3, 1, 1, 1, 1, 

And this works with std::array<bool> , std::vector<std::string> , std::unordered_set<void*>::iterator , etc.

Answer 7

A common way to do this is to save two indexes: one for the record you are editing, and the other for the record that you are going to process.

 const auto size = sizeof(A) / sizeof(int); // Nb if size == 1 entire array is garbage int i = 0; for (int nv = 1; nv < size; ++i, nv += 2) A[i] = A[nv]; --i; // Significative array is now [0;N/2[, fill with last now for (int j = i + 1; j < size; ++j) A[j] = A[i]; 

This provides on-site modification.

Answer 8

you can combine std::remove_if and std::fill to do this

---

code example:

 #include <algorithm> #include <iostream> #include <iterator> int main() { int A[6] = {6, 5, 4, 3, 2, 1}; auto endX = std::remove_if(std::begin(A),std::end(A),[&A](const int& i){return (&i-A)%2==0;}); if(endX!=std::begin(A))//in case nothing remained, although not possible in this case std::fill(endX,std::end(A),*(endX-1)); //else /*something to do if nothing remained*/ for(auto a : A)std::cout<<a<<' '; }