stl

• STL - Container Classes:
  • Sequence Container
    • Vector
    • List
    • Double-ended Queue(Deque)
  • Container Adaptor
    • Stack
    • Queue
    • Priority Queue
  • Associative Container
    • Set
    • Map

STL - Container Classes:

• Calling a function that accesses a element of a container while the container is empty is UB(undefined behavior).

Sequence Container

Vector

• A vector is a fixed length group of elements of uniform type, indexed by integer keys. Vectors can be considered to be a generalization of the built-in C++ array type.
• Vectors are useful when:

  • the number of items to be maintained by a collection is at least approximately known in advance.

  • As with arrays, vector elements can be directly indexed.

  • The sorting operation can be used to place the elements of a vector in order.

  • Accessing an element of a vector, read/write, can be performed in constant that is O(1) time.

  • Searching an unordered vector can be accomplished in O(n) time.

  • Searching a sorted vector can be accomplished in O(log n) time using binary search.

  • A notable operation on vectors, not possible with arrays, is that the size of the vector can dynamically be increased or decrease. Such operation may take O(n) worst case scenario.

    Operation	Capacity	Cost
    push_back(1)	1	1	1
    push_back(2)	2	1+1	1 2
    push_back(3)	4	2+1	1 2 3 ⠀
    push_back(4)	4	1	1 2 3 4
    push_back(5)	8	4+1	1 2 3 4 5 ⠀ ⠀ ⠀
    push_back(6)	8	1	1 2 3 4 5 6 ⠀ ⠀
    push_back(7)	8	1	1 2 3 4 5 6 7 ⠀
    push_back(8)	8	1	1 2 3 4 5 6 7 8
    push_back(9)	16	8+1	1 2 3 4 5 6 7 8 9 ⠀ ⠀ ⠀ ⠀ ⠀ ⠀ ⠀

    • amortized O(n)

    Amortized analysis is an analysis technique that examines a sequence of n operations. If the whole sequence runs in T(n) time, then each operation in the sequence runs in T(n)/n. The idea is that while a few operations in the sequence might be costly, they can't happen often enough to weigh down the program. It's important to note that this is different from average case analysis over some input distribution or randomized analysis. Amortized analysis established a worst case bound for the performance of an algorithm irrespective of the inputs. It's most commonly used to analyse data structures, which have a persistent state throughout the program.

    • Assume that you call push_back(x) N times.
    • The total cost comprises of:
      • Cost of adding an element
        • 1 operation per push_back(x)
        • Total N operations for N push_back(x)
      • Cost of moving elements when vector is full
        • 1, 2, 4, 8, ..., 2^k (where 2^k < N)
        • The sum of above = 2^k+1-1 < 2N
    • Total cost for N push_back(x) = N + (<2N) < 3N, and therefore is O(N).
    • We can say that push_back(x) is amortized O(1)

List

• A list is a data structure of choice when the number of elements in a collection cannot be bounded, or varies widely during the course of execution.
• Like a vector, a list maintains values of uniform type. Lists are not indexed, instead elements must be examined one by one in sequence.

Double-ended Queue(Deque)

• A deque or double ended queue is a data structure of an arbitrary size, growing and shrinking as elements are added or removed. The deque is optimized for insertion or removal of elements from either end. This operation can be performed in constant time.
• Like a vector dequeue is an indexed structure, allowing rapid access to any element. As values are inserted into the front of the structure, the index positions by which an element is accessed will constantly change to reflect the inclusion of the new values. Deques can be ordered and use binary search to locate a specific element, otherwise linear search is necessary.

---

Container Adaptor

Stack

• Elements in a stack obey the last-in first-out, or LIFO protocol, in that elements can be added or removed only from the front of the stack.

Queue

• A queue maintains a first-in, first-out protocol or FIFO. Elements are inserted in the back of the queue and removed from the front. The element removed from the queue is the one that was held the longest.

Priority Queue

• A priority queue is optimized for insertion of arbitrary new elements and for removal of the largest element, both operations can be performed in O(log n) time.

---

Associative Container

Set

• A set is a simple collection of unique values. The set data structure maintains values in an ordered representation. This permits rapid insertion, removal and testing for inclusion of a specific element. All operations can be performed in O(log n) time. In addition, operations are provided for forming the intersection and union of two sets.

Map

• A map (sometimes called a dictionary or a table) is, like a vector, an indexed collection. However, unlike a vector, the index values need not be integer, but can be any ordered data values. A map can therefore be thought of as a collection of associations of keys and value pairs.

---

Selecting a container:

How are values going to be accessed?

• If random access is important, then vector or deque should be used.
• If values are going to be accessed in order then set should be used.
• If sequential access is sufficient then any other structure is suitable.

Is the order in which values are maintained important?

• If strict ordering is important, then set is the best choice.
• If the order that values are held in the structure is related to the order of insertion, then stack, queue or list may be the best choice.

Will the size of the structure vary widely over the course of execution?

• If true, then list or set may be suitable, as they only use memory to hold currently stored values, while a vector or deque will continue to maintain a large buffer even after elements have been removed.

Is it possible to estimate the size of the collection of values?

• vector provides a way to pre-allocate a block of memory of a given size (reserve()).

Is testing whether a value is contained in the collection a frequent operation?

• If so, then the set or map would be a good choice. Testing to see whether a value is contained in set or map can be performed in a very small number of steps.

Is the collection indexed: Can it be viewed as a series of key/value pairs?

• If the keys are between 0 and some upper limit, then vector or deque should be employed. If on the other hand, the key values are some other ordered data type, then map can be used.

Can values be related to each other?

• If values cannot be ordered using ≤ operator, then we should use set or map.

Is finding and removing the largest value from the collection a frequent operation?

• priority_queue

At what positions are values inserted into or removed from the structure?

• Insertion/removal from the middle: list
• Insertion from beginning: list or deque
• Insertion/deletion from the end: stack or queue

Is the merging of two or more sequences into one a frequent operation?

• set or list are best choice.

---

이전 - Array	목록	다음 - BFS & DFS