std/deques

Реализация очереди с двумя концами (double-ended queue). Основная реализация использует seq.

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

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

Пример:

import std/deques
var a = [10, 20, 30, 40].toDeque

doAssertRaises(IndexDefect, echo a[4])

a.addLast(50)
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 для односвязных и двусвязных списков и колец

Импорты

since, assertions, hashes, math

Типы

Deque[T] = object

Очередь с двумя концами, поддерживаемая кольцевым seq буфером.

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

Source Edit

Константы

defaultInitialSize = 4

Source Edit

Процедуры

proc `$`[T](deq: Deque[T]): string

Преобразует очередь в её строковое представление.

Пример:

let a = [10, 20, 30].toDeque
assert $a == "[10, 20, 30]"

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

func `==`[T](deq1, deq2: Deque[T]): bool

Оператор сравнения для очереди. Возвращает == если обе очереди содержат одинаковые значения в том же порядке.

Пример:

var a, b = initDeque[int]()
a.addFirst(2)
a.addFirst(1)
b.addLast(1)
b.addLast(2)
doAssert a == b

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

proc `[]`[T](deq: Deque[T]; i: BackwardsIndex): lent T {.inline.}

Доступ к элементу с обратным индексом i.

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

Пример:

let a = [10, 20, 30, 40, 50].toDeque
assert a[^1] == 50
assert a[^4] == 20
doAssertRaises(IndexDefect, echo a[^9])

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

proc `[]`[T](deq: Deque[T]; i: Natural): lent T {.inline.}

Доступ к i-му элементу deq.

Пример:

let a = [10, 20, 30, 40, 50].toDeque
assert a[0] == 10
assert a[3] == 40
doAssertRaises(IndexDefect, echo a[8])

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

proc `[]`[T](deq: var Deque[T]; i: BackwardsIndex): var T {.inline.}

Доступ к элементу с обратным индексом i и получение изменяемой ссылки на него.

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

Пример:

var a = [10, 20, 30, 40, 50].toDeque
inc(a[^1])
assert a[^1] == 51

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

proc `[]`[T](deq: var Deque[T]; i: Natural): var T {.inline.}

Доступ к i-му элементу deq и получение изменяемой ссылки на него.

Пример:

var a = [10, 20, 30, 40, 50].toDeque
inc(a[0])
assert a[0] == 11

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

proc `[]=`[T](deq: var Deque[T]; i: BackwardsIndex; x: sink T) {.inline.}

Устанавливает значение обратного индекса i элемента deq на x.

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

Пример:

var a = [10, 20, 30, 40, 50].toDeque
a[^1] = 99
a[^3] = 77
assert $a == "[10, 20, 77, 40, 99]"

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

proc `[]=`[T](deq: var Deque[T]; i: Natural; val: sink T) {.inline.}

Устанавливает i-й элемент deq на val.

Пример:

var a = [10, 20, 30, 40, 50].toDeque
a[0] = 99
a[3] = 66
assert $a == "[99, 20, 30, 66, 50]"

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

proc addFirst[T](deq: var Deque[T]; item: sink T)

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

См. также:

• addLast proc

Пример:

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: sink T)

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

См. также:

• addFirst proc

Пример:

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

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

proc clear[T](deq: var Deque[T]) {.inline.}

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

См. также:

• shrink proc

Пример:

var a = [10, 20, 30, 40, 50].toDeque
assert $a == "[10, 20, 30, 40, 50]"
clear(a)
assert len(a) == 0

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

proc contains[T](deq: Deque[T]; item: T): bool {.inline.}

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

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

Пример:

let q = [7, 9].toDeque
assert 7 in q
assert q.contains(7)
assert 8 notin q

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

func hash[T](deq: Deque[T]): Hash

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

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

Создаёт новую пустую очередь.

Необязательно, начальный размер может быть зарезервирован с помощью initialSize в качестве оптимизации производительности (по умолчанию: defaultInitialSize). Длина созданной очереди будет всё равно 0.

См. также:

• toDeque proc

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

func len[T](deq: Deque[T]): int {.inline.}

Возвращает количество элементов в deq. Исходный код Редактировать

proc peekFirst[T](deq: Deque[T]): lent T {.inline.}

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

См. также:

• peekFirst proc, которая возвращает изменяемую ссылку
• peekLast proc

Пример:

let a = [10, 20, 30, 40, 50].toDeque
assert $a == "[10, 20, 30, 40, 50]"
assert a.peekFirst == 10
assert len(a) == 5

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

proc peekFirst[T](deq: var Deque[T]): var T {.inline.}

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

См. также:

• peekFirst proc
• peekLast proc

Пример:

var a = [10, 20, 30, 40, 50].toDeque
a.peekFirst() = 99
assert $a == "[99, 20, 30, 40, 50]"

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

proc peekLast[T](deq: Deque[T]): lent T {.inline.}

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

См. также:

• peekLast proc которая возвращает изменяемую ссылку
• peekFirst proc

Пример:

let a = [10, 20, 30, 40, 50].toDeque
assert $a == "[10, 20, 30, 40, 50]"
assert a.peekLast == 50
assert len(a) == 5

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

proc peekLast[T](deq: var Deque[T]): var T {.inline.}

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

См. также:

• peekFirst proc
• peekLast proc

Пример:

var a = [10, 20, 30, 40, 50].toDeque
a.peekLast() = 99
assert $a == "[10, 20, 30, 40, 99]"

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

proc popFirst[T](deq: var Deque[T]): T {.inline, discardable.}

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

См. также:

• метод popLast
• метод shrink

Пример:

var a = [10, 20, 30, 40, 50].toDeque
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.

См. также:

• метод popFirst
• метод shrink

Пример:

var a = [10, 20, 30, 40, 50].toDeque
assert $a == "[10, 20, 30, 40, 50]"
assert a.popLast == 50
assert $a == "[10, 20, 30, 40]"

Исходный код Изменить

proc shrink[T](deq: var Deque[T]; fromFirst = 0; fromLast = 0)

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

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

См. также:

• метод clear
• метод popFirst
• метод popLast

Пример:

var a = [10, 20, 30, 40, 50].toDeque
assert $a == "[10, 20, 30, 40, 50]"
a.shrink(fromFirst = 2, fromLast = 1)
assert $a == "[30, 40]"

Исходный код Изменить

proc toDeque[T](x: openArray[T]): Deque[T]

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

См. также:

• метод initDeque

Пример:

let a = toDeque([7, 8, 9])
assert len(a) == 3
assert $a == "[7, 8, 9]"

Исходный код Изменить

Итераторы

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

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

См. также:

• итератор mitems

Пример:

from std/sequtils import toSeq

let a = [10, 20, 30, 40, 50].toDeque
assert toSeq(a.items) == @[10, 20, 30, 40, 50]

Исходный код Изменить

iterator mitems[T](deq: var Deque[T]): var T

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

См. также:

• итератор items

Пример:

var a = [10, 20, 30, 40, 50].toDeque
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]

Возвращает каждую (position, value)-пару deq.

Пример:

from std/sequtils import toSeq

let a = [10, 20, 30].toDeque
assert toSeq(a.pairs) == @[(0, 10), (1, 20), (2, 30)]

Исходный код Изменить