如何从C++数组中删除每个第二个值而不复制数组？

Question

问题：我想得到一个数组A[6] = {6, 5, 4, 3, 2, 1}为A[6] = {5, 3, 1, 1, 1, 1}。换句话说 - “删除”从0开始的每个第二个值并将所有其他值向左移。

我尝试：

为了做到这一点，我会用这个代码，其中一个 - 的阵列A（与未删除的元素的部分），IND的相关部分的长度 - 值的索引我想删除。

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

但是，我不能得到这个工作，用这样的代码：

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); 

运行此代码我得到A[6] = {5, 4, 2, 1, 1507485184, 1507485184}后。所以，它删除了索引0,3的元素。为什么它删除了第三个索引？

Answer 1

有两种方法可以做到这一点：

1. 走阵列，复制过去的n-i元素向前一个地方，每甚至i，或

2. 搞清楚最终状态，只是去直接的。最后的状态是第一个n/2的地方是array[i]=array[2*i + 1]，而最后的n/2地方只是最后一个元素的副本。

第一种方法是您要求的方法，但它执行多个冗余复制操作，第二种方法避免了第二种方法。

至于您的实施问题，请检查j=n-1发生了什么，并记住A[n]不是数组的有效元素。 无论如何，我建议使copy-everything-forward操作自己的功能（或者你可以使用memcpy）

Answer 2

对于这些类型的问题（就地数组操作），最好只保留一个索引或指向数组的指针，指向“正在阅读”的位置以及正在“正在写入”的另一个位置。例如：

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

因此，如果它必须是一个数组的解决办法是这样的：

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]; 
} 

您通过阵列“移动”每第二数目到前的前半第一环路，然后你循环填充最后一个数字。

Answer 4

对于一个更通用的版本，其他的答案：

#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; 
} 

输出：

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

而这一点也适用std::array<bool>，std::vector<std::string>，std::unordered_set<void*>::iterator，等等。

Answer 5

这样做的常见方式是保持两个指标：一个是你正在修改的条目和其他的进入你打算过程

const auto size = sizeof(A)/sizeof(int); 

// N.b. 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]; 

这将授予的In-地方 - 修改时尚。

Answer 6

你可以结合std::remove_if和std::fill做到这一点

---

示例代码：

#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<<' '; 
} 

Answer 7

如果C++算法是一种选择，我倾向于在默认情况下喜欢他们：

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); 

std::remove_if算法简单地移动元素与谓词不匹配（在我们的例子中，测试地址是否为MOD（2）= 0），并且std::move将它们结束。这是到位的。新的“结束”再来，我则在索引和设置元素设置为0

Answer 8

只是踢，在这里是不使用循环的一个版本：

#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"; 
}