Spec-Zone.ru › Nim 1

deques

Реализация двусторонней очереди (deque). В основе реализации используется seq.

Ни один из методов, получающих значение из очереди, не может быть использован с пустой очередью. Если скомпилировать с опцией boundChecks, эти методы будут генерировать IndexDefect при таком доступе. На это не стоит полагаться, так как -d:danger или --checks:off отключат эти проверки, и могут вернуть мусор или привести к сбою программы.

Поэтому перед любым доступом нужна проверка на пустоту очереди, если ваша логика программы её косвенно не гарантирует.

import deques

var a = initDeque[int]()

doAssertRaises(IndexDefect, echo a[0])

for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"

assert a.peekFirst == 10
assert a.peekLast == 50
assert len(a) == 5

assert a.popFirst == 10
assert a.popLast == 50
assert len(a) == 3

a.addFirst(11)
a.addFirst(22)
a.addFirst(33)
assert $a == "[33, 22, 11, 20, 30, 40]"

a.shrink(fromFirst = 1, fromLast = 2)
assert $a == "[22, 11, 20]"

См. также:

  • модуль lists для односвязных и двусвязных списков и колец
  • модуль channels для межпотоковой коммуникации

Импорты

since, math

Типы

Deque[T] = object
  data: seq[T]
  head, tail, count, mask: int

Двусторонняя очередь, основанная на кольцевом буфере.

Для инициализации пустой очереди используйте процедуру initDeque.

Исходный код Редактировать

Константы

defaultInitialSize = 4
Исходный код Редактировать

Процедуры

proc initDeque[T](initialSize: int = 4): Deque[T]

Создаёт новую пустую очередь с возможностью предварительного выделения памяти для оптимизации производительности с помощью initialSize. Длина новой очереди по-прежнему будет 0.

См. также:

  • процедуру toDeque
Исходный код Редактировать 
proc toDeque[T](x: openArray[T]): Deque[T]

Создаёт новую очередь, содержащую элементы из x (в том же порядке).

См. также:

  • процедуру initDeque

Пример:

var a = toDeque([7, 8, 9])
assert len(a) == 3
assert a.popFirst == 7
assert len(a) == 2
Исходный код Редактировать 
proc len[T](deq: Deque[T]): int {...}{.inline.}
Возвращает количество элементов в deq. Исходный код Редактировать 
proc `[]`[T](deq: Deque[T]; i: Natural): T {...}{.inline.}
Получает доступ к i-му элементу deq.

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert a[0] == 10
assert a[3] == 40
doAssertRaises(IndexDefect, echo a[8])
Исходный код Редактировать 
proc `[]`[T](deq: var Deque[T]; i: Natural): var T {...}{.inline.}
Получает доступ к i-му элементу deq и возвращает мутабельную ссылку на него.

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert a[0] == 10
assert a[3] == 40
doAssertRaises(IndexDefect, echo a[8])
Исходный код Редактировать 
proc `[]=`[T](deq: var Deque[T]; i: Natural; val: T) {...}{.inline.}
Изменяет i-й элемент deq.

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
a[0] = 99
a[3] = 66
assert $a == "[99, 20, 30, 66, 50]"
Исходный код Редактировать 
proc `[]`[T](deq: Deque[T]; i: BackwardsIndex): T {...}{.inline.}

Получает доступ к i-му элементу с обратной индексацией.

deq[^1] — это последний элемент.

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert a[^1] == 50
assert a[^4] == 20
doAssertRaises(IndexDefect, echo a[^9])
Исходный код Редактировать 
proc `[]`[T](deq: var Deque[T]; i: BackwardsIndex): var T {...}{.inline.}

Получает доступ к i-му элементу с обратной индексацией.

deq[^1] — это последний элемент.

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert a[^1] == 50
assert a[^4] == 20
doAssertRaises(IndexDefect, echo a[^9])
Исходный код Редактировать 
proc `[]=`[T](deq: var Deque[T]; i: BackwardsIndex; x: T) {...}{.inline.}

Изменяет i-й элемент с обратной индексацией.

deq[^1] — это последний элемент.

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
a[^1] = 99
a[^3] = 77
assert $a == "[10, 20, 77, 40, 99]"
Исходный код Редактировать 
proc contains[T](deq: Deque[T]; item: T): bool {...}{.inline.}

Возвращает true, если item содержится в deq, или false, если не найдено.

Обычно используется с оператором in. Эквивалентно deq.find(item) >= 0.

if x in q:
  assert q.contains(x)
Исходный код Редактировать 
proc addFirst[T](deq: var Deque[T]; item: T)

Добавляет item в начало deq.

См. также:

  • процедуру addLast
  • процедуру peekFirst
  • процедуру peekLast
  • процедуру popFirst
  • процедуру popLast

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addFirst(10*i)
assert $a == "[50, 40, 30, 20, 10]"
Исходный код Редактировать 
proc addLast[T](deq: var Deque[T]; item: T)

Добавляет item в конец deq.

См. также:

  • процедуру addFirst
  • процедуру peekFirst
  • процедуру peekLast
  • процедуру popFirst
  • процедуру popLast

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
Исходный код Редактировать 
proc peekFirst[T](deq: Deque[T]): T {...}{.inline.}

Возвращает первый элемент deq, но не удаляет его из очереди.

См. также:

  • процедуру addFirst
  • процедуру addLast
  • процедуру peekLast
  • процедуру popFirst
  • процедуру popLast

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
assert a.peekFirst == 10
assert len(a) == 5
Исходный код Редактировать 
proc peekLast[T](deq: Deque[T]): T {...}{.inline.}

Возвращает последний элемент deq, но не удаляет его из очереди.

См. также:

  • процедуру addFirst
  • процедуру addLast
  • процедуру peekFirst
  • процедуру popFirst
  • процедуру popLast

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
assert a.peekLast == 50
assert len(a) == 5
Исходный код Редактировать 
proc peekFirst[T](deq: var Deque[T]): var T {...}{.inline.}

Возвращает первый элемент deq, но не удаляет его из очереди.

См. также:

  • процедуру addFirst
  • процедуру addLast
  • процедуру peekLast
  • процедуру popFirst
  • процедуру popLast

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
assert a.peekFirst == 10
assert len(a) == 5
Исходный код Редактировать 
proc peekLast[T](deq: var Deque[T]): var T {...}{.inline.}

Возвращает последний элемент deq, но не удаляет его из очереди.

См. также:

  • процедуру addFirst
  • процедуру addLast
  • процедуру peekFirst
  • процедуру popFirst
  • процедуру popLast

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
assert a.peekLast == 50
assert len(a) == 5
Исходный код Редактировать 
proc popFirst[T](deq: var Deque[T]): T {...}{.inline, discardable.}

Удаляет и возвращает первый элемент deq.

См. также:

  • процедуру addFirst
  • процедуру addLast
  • процедуру peekFirst
  • процедуру peekLast
  • процедуру popLast
  • процедуру clear
  • процедуру shrink

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
assert a.popFirst == 10
assert $a == "[20, 30, 40, 50]"
Исходный код Редактировать 
proc popLast[T](deq: var Deque[T]): T {...}{.inline, discardable.}

Удаляет и возвращает последний элемент deq.

См. также:

  • процедуру addFirst
  • процедуру addLast
  • процедуру peekFirst
  • процедуру peekLast
  • процедуру popFirst
  • процедуру clear
  • процедуру shrink

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
assert a.popLast == 50
assert $a == "[10, 20, 30, 40]"
Исходный код Редактировать 
proc clear[T](deq: var Deque[T]) {...}{.inline.}

Очищает очередь, делая её пустой.

См. также:

  • процедуру clear
  • процедуру shrink

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addFirst(10*i)
assert $a == "[50, 40, 30, 20, 10]"
clear(a)
assert len(a) == 0
Исходный код Редактировать 
proc shrink[T](deq: var Deque[T]; fromFirst = 0; fromLast = 0)

Удаляет элементы fromFirst с начала очереди и fromLast с конца.

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

См. также:

  • процедуру clear

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addFirst(10*i)
assert $a == "[50, 40, 30, 20, 10]"
a.shrink(fromFirst = 2, fromLast = 1)
assert $a == "[30, 20]"
Исходный код Редактировать 
proc `$`[T](deq: Deque[T]): string
Преобразует очередь в её строковое представление. Исходный код Редактировать

Итераторы

iterator items[T](deq: Deque[T]): T

Возвращает каждый элемент deq.

Примеры:

var a = initDeque[int]()
for i in 1 .. 3:
  a.addLast(10*i)

for x in a:  # the same as: for x in items(a):
  echo x

# 10
# 20
# 30
Исходный код Редактировать 
iterator mitems[T](deq: var Deque[T]): var T
Возвращает каждый элемент deq, который можно изменить.

Пример:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
for x in mitems(a):
  x = 5*x - 1
assert $a == "[49, 99, 149, 199, 249]"
Исходный код Редактировать 
iterator pairs[T](deq: Deque[T]): tuple[key: int, val: T]

Возвращает каждую (позицию, значение) deq.

Примеры:

var a = initDeque[int]()
for i in 1 .. 3:
  a.addLast(10*i)

for k, v in pairs(a):
  echo "key: ", k, ", value: ", v

# key: 0, value: 10
# key: 1, value: 20
# key: 2, value: 30
Исходный код Редактировать

© 2006–2021 Andreas Rumpf
Licensed under the MIT License.
https://nim-lang.org/docs/deques.html

Spec-Zone.ru

Настройки Оффлайн Что нового Помощь О нас
Spec-Zone .ru
спецификации, руководства, описания, API