Перестановка структуры фиксированной длины: использовать массив или связанный список?

Question

Эта структура будет содержать только 256 символов без знака. Единственная возможная операция - взять из нее случайные символы и поместить их перед структурой. Например:

A= 'abcdef'

Переместить символ 2 вперед

A= 'cabdef'

Сначала я подумал об использовании связанной ссылки, чтобы она могла работать как очередь. Дело в том, что я слышал, что массивы намного быстрее, чем связанные списки для этих операций. Это правда?

Answer 1

Связанный список будет O (1), а массив будет O (n) для операции перемещения, как вы описали.Для небольших n массив, вероятно, будет быстрее, но единственный способ узнать наверняка - это тестированиеузкое место.

PS Я сделал предположение, что у вас уже есть указатель на персонажа, которого вы хотите переместить.Если это не так, то поиск символа будет O (n) в связанном списке, и вы потеряете все его преимущества.

Answer 2

Использовать массив. Связанный список будет огромным и громоздким для хранения данных char.

Answer 3

Связанный список будет хорошим подходом, поскольку вам не нужно перемещать все промежуточные элементы. std::list работает просто отлично, в сочетании с splice(). Вам понадобится итератор для элемента, который вы хотите переместить на передний план:

#include <list>
#include <iostream>
#include "prettyprint.hpp"

int main()
{
  std::list<int> x { 1, 4, 6, 7, 2 };
  auto i = x.begin(); std::advance(i, 2);  // i points to 6

  std::cout << x << std::endl;  //  [1, 4, 6, 7, 2]

  x.splice(x.begin(), x, i);

  std::cout << x << std::endl;  //  [6, 1, 4, 7, 2]
}

(Использование быстрого принтера для быстрой демонстрации.)

Как уже говорили другие, будет ли эффективнее, если контейнер произвольного доступа зависит от того, как вы отслеживаете элемент, который хотите переместить.

---

Обновление: В свете замечаний Стива я также хотел бы предложить решение с необработанным C-массивом. Преимущество состоит в том, что вы можете получить к нему доступ по положению за время O (1) и что ему требуется минимальное пространство:

char y[] = { 'a', 'c', 'Q', '%', '5' };
std::cout << pretty_print_array(y) << std::endl; // [a, c, Q, %, 5]
std::rotate(y, y + 2, y + sizeof(y));
std::cout << pretty_print_array(y) << std::endl; // [Q, %, 5, a, c]

Вызов rotate может быть заключен в функцию:

template <typename T, size_t N>
void bring_forward(T (& a)[N], size_t p) { std::rotate(a, a + p, a + N); }

Answer 4

В C ++ вы можете использовать vector вместо массива или связанного списка. Сложность связанного списка - O (1), как сказал @Mark Ransom. С вектором вы можете использовать команду rotate , чтобы выполнить желаемое действие. Сложность определяется количеством свопов.

Из MSDN, как использовать rotate:

   const int VECTOR_SIZE = 8;

   // Define a template class vector of strings
   typedef vector<string> StrVector;

   //Define an iterator for template class vector of strings
   typedef StrVector::iterator StrVectorIt;

   StrVector Tongue_Twister(VECTOR_SIZE);

   StrVectorIt start, end, middle, it;

   // location of first element of Tongue_Twister
   start = Tongue_Twister.begin();   

   // one past the location last element of Tongue_Twister
   end = Tongue_Twister.end();       


   // Initialize vector Tongue_Twister
   Tongue_Twister[0] = "she";
   Tongue_Twister[1] = "sells";
   Tongue_Twister[2] = "sea";
   Tongue_Twister[3] = "shells";
   Tongue_Twister[4] = "by";
   Tongue_Twister[5] = "the";
   Tongue_Twister[6] = "sea";
   Tongue_Twister[7] = "shore";

   middle = start + 3;  // start position for rotating elements

   cout << "Before calling rotate" << endl;

   // print content of Tongue_Twister
   cout << "Try this Tongue Twister:";
   for (it = start; it != end; it++)
      cout << " " << *it;

   // rotate the items in the vector Tongue_Twister by 3 positions
   rotate(start, middle, end);

Или вы можете сделать это с массивами:

// create an array of 9 elements and rotate the entire array.
int myArray[SIZE] = { 7, 8, 9, 1, 2, 3, 4, 5, 6,  };
std::rotate(myArray, myArray + 3, myArray + SIZE);

Как быстро это? Я не знаю. Я не тестировал это. Но это гораздо проще, чем вручную менять элементы массива.

Answer 5

Массив будет O (1), чтобы найти элемент, и O (n), чтобы переместить его и другие элементы в правильную позицию.Связанный список будет O (n), чтобы найти элемент и O (1), чтобы переместить все в правильную позицию.Сложность одинакова в любом случае.

Они оба просты в реализации, поэтому реализуйте их оба и запустите тесты, чтобы увидеть, какой из них позволяет вашей программе работать быстрее с данными реального мира.

Answer 6

C ++ массивы являются связанными списками, поэтому перемещение элемента в начало списка стоит дешево, если вы уже знаете, где находится этот элемент (т.е. у вас есть итератор).Использование вектора приведет к смещению всего списка каждый раз, когда перед ним передается элемент.