Алгоритм эффективного перемещения содержимого вектора
У меня есть вектор размерности 3, который будет постоянно менять значение, например, если я удалю содержимое позиции 0, я хочу переместить содержимое оставшихся ячеек в оставшиеся ячейки, чтобы начать с 0.
В настоящее время я делаю это таким образом (Java-код), но считаю, что это очень неэффективно.
aux = posy[1];
posy[0] = aux;
aux = posy[2];
posy[1] = aux;
posy[2] = 0;
Есть ли другой, более эффективный способ сделать это?
Просто сохраните указатели на голову и хвост, и вам не нужно будет ничего вращать.
Я сомневаюсь, что вы заметите, что всего для трех элементов цикл может быть немного менее эффективным. Для многих элементов вам следует рассмотреть класс ArrayDeque, но, насколько я понимаю, здесь дело обстоит не так.
Ответы 1
Никаких дополнительных переменных не требуется.
posy[0] = posy[1];
posy[1] = posy[2];
posy[2] = 0;
Чтобы двигаться в обратном направлении, вам нужно будет сделать это в обратном порядке.
Никакое другое улучшение невозможно.
Если бы у вас было много элементов (скажем, пять элементов), я бы порекомендовал вам изучить класс ArrayDeque. Это позволяет вставлять и удалять с обоих концов без смещения элементов. Вероятно, он реализован с указателем, указывающим на каждый конец как @Jacob G. в комментарии, предложенном сделать. Всего для трех элементов это можно считать излишним.
Я имею в виду, вот как это делается. Это всегда займет время O (n). Лучшее, что вы можете сделать, это использовать петлю.