An implementation of a deque (double-ended queue). The underlying implementation uses a seq.
If compiled with the boundChecks option, those procs will raise an IndexDefect on such access. This should not be relied upon, as -d:danger or --checks:off will disable those checks and then the procs may return garbage or crash the program.
As such, a check to see if the deque is empty is needed before any access, unless your program logic guarantees it indirectly.
Example:
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]"
See also
- lists module for singly and doubly linked lists and rings
- channels module for inter-thread communication
Procs
proc `$`[T](deq: Deque[T]): string
-
Turns a deque into its string representation.
Example:
let a = [10, 20, 30].toDeque assert $a == "[10, 20, 30]"
Source Edit proc `[]=`[T](deq: var Deque[T]; i: BackwardsIndex; x: sink T) {.inline.}
-
Sets the backwards indexed i-th element of deq to x.
deq[^1] is the last element.
Example:
var a = [10, 20, 30, 40, 50].toDeque a[^1] = 99 a[^3] = 77 assert $a == "[10, 20, 77, 40, 99]"
Source Edit proc `[]=`[T](deq: var Deque[T]; i: Natural; val: sink T) {.inline.}
-
Sets the i-th element of deq to val.
Example:
var a = [10, 20, 30, 40, 50].toDeque a[0] = 99 a[3] = 66 assert $a == "[99, 20, 30, 66, 50]"
Source Edit proc `[]`[T](deq: Deque[T]; i: BackwardsIndex): lent T {.inline.}
-
Accesses the backwards indexed i-th element.
deq[^1] is the last element.
Example:
let a = [10, 20, 30, 40, 50].toDeque assert a[^1] == 50 assert a[^4] == 20 doAssertRaises(IndexDefect, echo a[^9])
Source Edit proc `[]`[T](deq: Deque[T]; i: Natural): lent T {.inline.}
-
Accesses the i-th element of deq.
Example:
let a = [10, 20, 30, 40, 50].toDeque assert a[0] == 10 assert a[3] == 40 doAssertRaises(IndexDefect, echo a[8])
Source Edit proc `[]`[T](deq: var Deque[T]; i: BackwardsIndex): var T {.inline.}
-
Accesses the backwards indexed i-th element and returns a mutable reference to it.
deq[^1] is the last element.
Example:
var a = [10, 20, 30, 40, 50].toDeque inc(a[^1]) assert a[^1] == 51
Source Edit proc `[]`[T](deq: var Deque[T]; i: Natural): var T {.inline.}
-
Accesses the i-th element of deq and returns a mutable reference to it.
Example:
var a = [10, 20, 30, 40, 50].toDeque inc(a[0]) assert a[0] == 11
Source Edit proc addFirst[T](deq: var Deque[T]; item: sink T)
-
Adds an item to the beginning of deq.
See also:
Example:
var a = initDeque[int]() for i in 1 .. 5: a.addFirst(10 * i) assert $a == "[50, 40, 30, 20, 10]"
Source Edit proc addLast[T](deq: var Deque[T]; item: sink T)
-
Adds an item to the end of deq.
See also:
Example:
var a = initDeque[int]() for i in 1 .. 5: a.addLast(10 * i) assert $a == "[10, 20, 30, 40, 50]"
Source Edit proc clear[T](deq: var Deque[T]) {.inline.}
-
Resets the deque so that it is empty.
See also:
Example:
var a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" clear(a) assert len(a) == 0
Source Edit proc contains[T](deq: Deque[T]; item: T): bool {.inline.}
-
Returns true if item is in deq or false if not found.
Usually used via the in operator. It is the equivalent of deq.find(item) >= 0.
Example:
let q = [7, 9].toDeque assert 7 in q assert q.contains(7) assert 8 notin q
Source Edit proc initDeque[T](initialSize: int = defaultInitialSize): Deque[T]
-
Creates a new empty deque.
Optionally, the initial capacity can be reserved via initialSize as a performance optimization (default: defaultInitialSize). The length of a newly created deque will still be 0.
See also:
Source Edit proc peekFirst[T](deq: Deque[T]): lent T {.inline.}
-
Returns the first element of deq, but does not remove it from the deque.
See also:
- peekFirst proc which returns a mutable reference
- peekLast proc
Example:
let a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" assert a.peekFirst == 10 assert len(a) == 5
Source Edit proc peekFirst[T](deq: var Deque[T]): var T {.inline.}
-
Returns a mutable reference to the first element of deq, but does not remove it from the deque.
See also:
Example:
var a = [10, 20, 30, 40, 50].toDeque a.peekFirst() = 99 assert $a == "[99, 20, 30, 40, 50]"
Source Edit proc peekLast[T](deq: Deque[T]): lent T {.inline.}
-
Returns the last element of deq, but does not remove it from the deque.
See also:
- peekLast proc which returns a mutable reference
- peekFirst proc
Example:
let a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" assert a.peekLast == 50 assert len(a) == 5
Source Edit proc peekLast[T](deq: var Deque[T]): var T {.inline.}
-
Returns a mutable reference to the last element of deq, but does not remove it from the deque.
See also:
Example:
var a = [10, 20, 30, 40, 50].toDeque a.peekLast() = 99 assert $a == "[10, 20, 30, 40, 99]"
Source Edit proc popFirst[T](deq: var Deque[T]): T {.inline, discardable.}
-
Removes and returns the first element of the deq.
See also:
Example:
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]"
Source Edit proc popLast[T](deq: var Deque[T]): T {.inline, discardable.}
-
Removes and returns the last element of the deq.
See also:
Example:
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]"
Source Edit proc shrink[T](deq: var Deque[T]; fromFirst = 0; fromLast = 0)
-
Removes fromFirst elements from the front of the deque and fromLast elements from the back.
If the supplied number of elements exceeds the total number of elements in the deque, the deque will remain empty.
See also:
Example:
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]"
Source Edit