deque :: insert () по индексу? - PullRequest
Новая
       10

deque :: insert () по индексу?

3 голосов
/ 23 октября 2011

Как мне insert() связать предметы до середины deque по линейному времени?

(элементы, которые я вставляю, не доступны через итератор в стиле STL.)

Ответы [ 4 ]

6 голосов
/ 23 октября 2011

Существует функция deque::insert(iterator pos, const T&x), принимающая позицию pos как deque::iterator и один элемент. Используя этот метод, вы можете вставить все элементы один за другим. pos можно легко получить (если у вас есть индекс, перед которым вы хотите вставить элемент) с помощью deque.begin()+index. Метод insert возвращает итератор для вновь вставленного элемента, просто увеличьте этот возвращенный итератор, чтобы получить следующую позицию: 

deque::iterator it = myDeque.begin()+index;
while(n--) {
  it = myDeque.insert(it, currentElement);
  it++;
  currentElement = ... // However you get your next element ...
}

Это, однако, может занять O(n*k) время, так как вставка одного элемента является (iirc) линейной операцией времени iirc.

Вторая перегрузка - deque::insert(iterator pos, InputIterator f, InputIterator l): помните, что простые указатели также удовлетворяют требованиям итератора ввода STL, поэтому, если у вас есть массив C-Style T array[] длины n, содержащий ваши элементы, вы можете вставить все элементы из этого массива с 

d.insert(pos, array, array+n);

Эта операция может быть выполнена за линейное время, т.е. O(n+k). Я не уверен, гарантируется ли это стандартом, но я полагаю, что большинство реализаций сделает это эффективно.

РЕДАКТИРОВАТЬ

Я быстро сверился с реализацией Microsoft, они делают это с помощью последовательности push_back или push_front, что ближе к pos, а затем поворачивают элементы на их окончательное место, что гарантирует вышеуказанное O(n+k) сложность. Конечно, это также можно сделать «вручную», например: 

size_type _Off = pos - d.begin();
size_type _Oldsize = d.size();
if (_Off <= d.size() / 2)
{   // closer to front, push to front then rotate
  while (hasMoreElements())
    push_front(nextElement()); // prepend flipped

  size_type _Num = d.size() - _Oldsize;
  std::reverse(d.begin(), d.begin() + _Num); // flip new stuff in place
  std::rotate(d.begin(), d.begin() + _Num, begin() + _Num + _Off);
}
else
{ // closer to back
  while (hasMoreElements())
    push_front(nextElement()); // prepend flipped

  std::rotate(begin() + _Off, begin() + _Oldsize, end());
}

(Я скопировал код из реализации Microsoft 1066 *, удалив отладочный код и обработав исключение,

1 голос
/ 23 октября 2011

Вызовите метод вставки, который принимает последовательность элементов для вставки, см. Третий метод, перечисленный здесь:

http://msdn.microsoft.com/en-us/library/zcww84w5(v=vs.71).aspx

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

Пользовательский итератор в C ++

0 голосов
/ 23 октября 2011

Добавить все элементы после точки вставки в вектор.
Удалить все элементы после точки вставки.
Добавить новый диапазон в deque.
Добавить вектор в deque.

ЭтоO (2n) наихудший случай вместо O (n ^ 2).

0 голосов
/ 23 октября 2011

Ввод:

Deque: lengtl = l,

Новые элементы (m = количество новых элементов)

Algo:

создать новую деку (1)

Скопировать все элементы из оригинальной декы до места, где вы хотите вставить новые (p)

Добавить новые элементы (m)

Добавление элементов из старой deque (mp)

Возможно, вы можете просто использовать новую deque, но в худшем случае:

Скопировать новый deque на старый (после завершенияclear:):

Стоимость (l + m)

Таким образом, наихудшая стоимость: origsize * 2 + newitems, которая является линейной.

"Clear deck" isn 'здесь считается, но оно также линейно (в худшем случае).

...