swiftlang/swift

[SR-6865] Sorted collections

Open

#49,414 opened on Jan 29, 2018

View on GitHub
 (1 comment) (0 reactions) (0 assignees)Swift (69,989 stars) (10,719 forks)batch import
featuregood first issuestandard libraryswift evolution proposal needed

Description
Previous ID SR-6865
Radar rdar://problem/20340872
Original Reporter @airspeedswift
Type New Feature
Votes 1
Component/s Standard Library
Labels New Feature, StarterProposal
Assignee None
Priority Medium

md5: 5e738267ffe5dde28ff4e498aac141e3

Issue Description:

It would be useful to have sorted equivalents of Set, Dictionary and Array, that kept their elements in sorted order, and only required Comparable, or could take a custom comparator. SortedSet and SortedDictionary would probably be best represented by a tree, whereas SortedArray would be represented by contiguous storage and would need an API for efficiently adding new entries in bulk.

Contributor guide

Tech stack
swift
Domain
data
Issue type
feature
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
5
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
over 1 week
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
stale
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
clear
Prerequisites
Swiftdata structuresAPI design
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
15
Research direction
Review the Swift standard library source code for existing collection types (e.g., Set, Dictionary) in the 'stdlib/public/core' directory. Search for any prior Swift Evolution proposals or discussions about sorted collections. Assess the feasibility of implementing SortedSet and SortedDictionary using a tree structure, and SortedArray using contiguous storage. This issue requires a deep understanding of Swift's standard library design and performance considerations. Consider proposing a detailed design document before implementation.