Как я могу сдвинуть массив вправо в C ++?
Я пытаюсь реализовать функцию для смещения массива объектов справа от массива. Все, что я нашел в Интернете, — это внедрение циклических сдвигов, но это не то, что я ищу. Я хочу сместить элементы вправо, если на самом деле пустое пространство справа.
Предположим, вы создали массив объекта Packet, и его размер 10
Packet* a[] = { p4 , p3 , p2 , p1, null, null, null, null, null, null }
функция смещения просто сместит все вправо
{ null ,p4 , p3 , p2 , p1, null, null, null, null, null }
и в случае наличия элемента в конце массива
{ p10, p9, p8, p7 ,p6 ,p5 ,p4 , p3 , p2 , p1}
функция просто ничего не меняет.
{ p4 , p3 , p2 , p1, null, null, null, null, null, null }
моя идея реализации состоит в том, чтобы скопировать массив во временную,
сотрите все в исходном массиве, а затем скопируйте в него, но начиная с позиции [1], а не с позиции [0]. но это не кажется очень эффективным.
какие-нибудь другие идеи?
Решение
при условии, что массив имеет n элементов:
if(a[n-1]==null){
memmove(a+1, a, (n-1)*sizeof(Packet*));
a[0]=null;
}
Альтернативой может быть не смещение элементов массива, а индекс, который вы используете для доступа к нему. По сути, вы хотите добавить 1 по модулю n.
Другие решения
Итерируйте массив справа налево, присваивая элемент n-1 стихия n, Когда вы дойдете до первого элемента, назначьте null к этому. (что бы это ни значило)
Если вы собираетесь делать это много (и массив не маленький), подумайте об использовании std::deque, так как это позволяет эффективно вставлять и удалять на обоих концах. Сдвиг вправо для N места можно заменить поппингом N нули со спины и толкая N нули на фронте. Ты можешь использовать std::rotate за это тоже.
Для любого контейнера (включая необработанный массив) для типов POD и не POD используйте следующее:
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());
}
Это для типов POD и не POD, так как copy_backward заботится о категории значения, и если это POD, то он использует memmove (по крайней мере, в библиотеке std, используемой gcc).
std::advance для произвольного доступа итератор использует простое сложение / вычитание.
std::fill также заботится о PODness, как std::copy*,
value_type() для типов указателей просто NULL, для bool false, для целых типов 0 и так далее.
Использование для массивов:
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"); });
Вывод как ожидалось:
null
1
2
null
null
3
-----------------------------------------------------
null
null
null
null
1
2
Очевидный ответ в C ++ заключается в использовании std::vectorв каком случае это
становится чем-то простым:
if ( a.back() == NULL ) {
a.insert( a.begin(), NULL );
a.pop_back();
}
Вы могли бы также рассмотреть std::deque, что позволило бы push_front,
вместо insert, Для таких маленьких массивов просто скопировать
объекты. простота std::vector вообще выигрывает.
Если вам нужно использовать массив в стиле C, что-то вроде:
if ( *(end( a ) - 1) == NULL ) {
std::copy_backwards( begin( a ), end( a ) - 1, end( a ) );
a[0] = NULL;
}
должен сделать свое дело.
Вы можете попробовать реализовать связанный список, который позволит вам сдвигать / снимать с места или вставлять / выталкивать элементы (в этом случае пространство будет освобождено).
Что не так с циркулярным способом сделать это? это довольно эффективно. Например.:
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;
}
В C ++ 11 мы имеем 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);