std/deques

Search:
Source   Edit  

An implementation of a deque (double-ended queue). The underlying implementation uses a seq.

Note: None of the procs that get an individual value from the deque should be used on an empty deque.

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

Types

Deque[T] = object

A double-ended queue backed with a ringed seq buffer.

To initialize an empty deque, use the initDeque proc.

Source   Edit  

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   
func `==`[T](deq1, deq2: Deque[T]): bool
The == operator for Deque. Returns true if both deques contains the same values in the same order.

Example:

var a, b = initDeque[int]()
a.addFirst(2)
a.addFirst(1)
b.addLast(1)
b.addLast(2)
doAssert a == b
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 `[]=`[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 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   
func hash[T](deq: Deque[T]): Hash
Hashing of Deque. 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   
func len[T](deq: Deque[T]): int {.inline.}
Returns the number of elements of deq. 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:

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:

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   
proc toDeque[T](x: openArray[T]): Deque[T]

Creates a new deque that contains the elements of x (in the same order).

See also:

Example:

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

Iterators

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

Yields every element of deq.

See also:

Example:

from std/sequtils import toSeq

let a = [10, 20, 30, 40, 50].toDeque
assert toSeq(a.items) == @[10, 20, 30, 40, 50]
Source   Edit   
iterator mitems[T](deq: var Deque[T]): var T

Yields every element of deq, which can be modified.

See also:

Example:

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]"
Source   Edit   
iterator pairs[T](deq: Deque[T]): tuple[key: int, val: T]
Yields every (position, value)-pair of deq.

Example:

from std/sequtils import toSeq

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

Made with Nim. Generated: 2025-03-29 22:17:00 UTC