1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2021 - 2024 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
/// A collection implementing a double-ended queue. `Deque` (pronounced "deck")
/// implements an ordered random-access collection that supports efficient
/// insertions and removals from both ends.
///
/// var colors: Deque = ["red", "yellow", "blue"]
///
/// Deques implement the same indexing semantics as arrays: they use integer
/// indices, and the first element of a nonempty deque is always at index zero.
/// Like arrays, deques conform to `RangeReplaceableCollection`,
/// `MutableCollection` and `RandomAccessCollection`, providing a familiar
/// interface for manipulating their contents:
///
/// print(colors[1]) // "yellow"
/// print(colors[3]) // Runtime error: Index out of range
///
/// colors.insert("green", at: 1)
/// // ["red", "green", "yellow", "blue"]
///
/// colors.remove(at: 2) // "yellow"
/// // ["red", "green", "blue"]
///
/// Like all variable-size collections on the standard library, `Deque`
/// implements value semantics: each deque has an independent value that
/// includes the values of its elements. Modifying one deque does not affect any
/// others:
///
/// var copy = deque
/// copy[1] = "violet"
/// print(copy) // ["red", "violet", "blue"]
/// print(deque) // ["red", "green", "blue"]
///
/// This is implemented with the copy-on-write optimization. Multiple copies of
/// a deque share the same underlying storage until you modify one of the
/// copies. When that happens, the deque being modified replaces its storage
/// with a uniquely owned copy of itself, which is then modified in place.
///
/// `Deque` stores its elements in a circular buffer, which allows efficient
/// insertions and removals at both ends of the collection; however, this comes
/// at the cost of potentially discontiguous storage. In contrast, `Array` is
/// (usually) backed by a contiguous buffer, where new data can be efficiently
/// appended to the end, but inserting at the front is relatively slow, as
/// existing elements need to be shifted to make room.
///
/// This difference in implementation means that while the interface of a deque
/// is very similar to an array, the operations have different performance
/// characteristics. Mutations near the front are expected to be significantly
/// faster in deques, but arrays may measure slightly faster for general
/// random-access lookups.
///
/// Deques provide a handful of additional operations that make it easier to
/// insert and remove elements at the front. This includes queue operations such
/// as `popFirst` and `prepend`, including the ability to directly prepend a
/// sequence of elements:
///
/// colors.append("green")
/// colors.prepend("orange")
/// // colors: ["orange", "red", "blue", "yellow", "green"]
///
/// colors.popLast() // "green"
/// colors.popFirst() // "orange"
/// // colors: ["red", "blue", "yellow"]
///
/// colors.prepend(contentsOf: ["purple", "teal"])
/// // colors: ["purple", "teal", "red", "blue", "yellow"]
///
/// Unlike arrays, deques do not currently provide direct unsafe access to their
/// underlying storage. They also lack a `capacity` property -- the size of the
/// storage buffer at any given point is an unstable implementation detail that
/// should not affect application logic. (However, deques do provide a
/// `reserveCapacity` method.)
@frozen
public struct Deque<Element> {
@usableFromInline
internal typealias _Slot = _DequeSlot
@usableFromInline
internal var _storage: _Storage
@inlinable
internal init(_storage: _Storage) {
self._storage = _storage
}
/// Creates and empty deque with preallocated space for at least the specified
/// number of elements.
///
/// - Parameter minimumCapacity: The minimum number of elements that the
/// newly created deque should be able to store without reallocating its
/// storage buffer.
@inlinable
public init(minimumCapacity: Int) {
self._storage = _Storage(minimumCapacity: minimumCapacity)
}
}
|
