CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Set (abstract data type) - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"639ea3b9-6746-4952-ab5b-ec7fe5c1d5b6","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Set_(abstract_data_type)","wgTitle":"Set (abstract data type)","wgCurRevisionId":1223692548,"wgRevisionId":1223692548,"wgArticleId":201127,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Articles needing additional references from October 2011","All articles needing additional references","Wikipedia articles needing clarification from November 2020","Articles with example Python (programming language) code","Data types","Composite data types","Abstract data types"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext", "wgRelevantPageName":"Set_(abstract_data_type)","wgRelevantArticleId":201127,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1514741","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform", "platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","ext.cite.styles":"ready","ext.pygments":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips", "ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.16"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Set (abstract data type) - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Set_(abstract_data_type)"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Set_(abstract_data_type)&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Set_(abstract_data_type)"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Set_abstract_data_type rootpage-Set_abstract_data_type skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Main menu" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Set+%28abstract+data+type%29" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Set+%28abstract+data+type%29" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Set+%28abstract+data+type%29" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Set+%28abstract+data+type%29" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Type_theory" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Type_theory"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Type theory</span> </div> </a> <ul id="toc-Type_theory-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Operations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Operations"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Operations</span> </div> </a> <button aria-controls="toc-Operations-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Operations subsection</span> </button> <ul id="toc-Operations-sublist" class="vector-toc-list"> <li id="toc-Core_set-theoretical_operations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Core_set-theoretical_operations"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Core set-theoretical operations</span> </div> </a> <ul id="toc-Core_set-theoretical_operations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Static_sets" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Static_sets"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Static sets</span> </div> </a> <ul id="toc-Static_sets-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Dynamic_sets" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Dynamic_sets"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Dynamic sets</span> </div> </a> <ul id="toc-Dynamic_sets-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Additional_operations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Additional_operations"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.4</span> <span>Additional operations</span> </div> </a> <ul id="toc-Additional_operations-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Implementations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Implementations"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Implementations</span> </div> </a> <ul id="toc-Implementations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Language_support" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Language_support"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Language support</span> </div> </a> <ul id="toc-Language_support-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Multiset" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Multiset"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Multiset</span> </div> </a> <button aria-controls="toc-Multiset-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Multiset subsection</span> </button> <ul id="toc-Multiset-sublist" class="vector-toc-list"> <li id="toc-Multisets_in_SQL" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Multisets_in_SQL"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Multisets in SQL</span> </div> </a> <ul id="toc-Multisets_in_SQL-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table of Contents" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Set (abstract data type)</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 23 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-23" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">23 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D9%85%D8%AC%D9%85%D9%88%D8%B9%D8%A9_(%D9%86%D9%88%D8%B9_%D8%A8%D9%8A%D8%A7%D9%86%D8%A7%D8%AA_%D9%85%D8%AC%D8%B1%D8%AF)" title="مجموعة (نوع بيانات مجرد) – Arabic" lang="ar" hreflang="ar" data-title="مجموعة (نوع بيانات مجرد)" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Conjunt_(estructura_de_dades)" title="Conjunt (estructura de dades) – Catalan" lang="ca" hreflang="ca" data-title="Conjunt (estructura de dades)" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Mno%C5%BEina_(datov%C3%A1_struktura)" title="Množina (datová struktura) – Czech" lang="cs" hreflang="cs" data-title="Množina (datová struktura)" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Menge_(Datenstruktur)" title="Menge (Datenstruktur) – German" lang="de" hreflang="de" data-title="Menge (Datenstruktur)" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/Hulk_(andmestruktuur)" title="Hulk (andmestruktuur) – Estonian" lang="et" hreflang="et" data-title="Hulk (andmestruktuur)" data-language-autonym="Eesti" data-language-local-name="Estonian" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Conjunto_(programaci%C3%B3n)" title="Conjunto (programación) – Spanish" lang="es" hreflang="es" data-title="Conjunto (programación)" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Aro_(komputiko)" title="Aro (komputiko) – Esperanto" lang="eo" hreflang="eo" data-title="Aro (komputiko)" data-language-autonym="Esperanto" data-language-local-name="Esperanto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%85%D8%AC%D9%85%D9%88%D8%B9%D9%87_(%D9%86%D9%88%D8%B9_%D8%AF%D8%A7%D8%AF%D9%87_%D8%A7%D9%86%D8%AA%D8%B2%D8%A7%D8%B9%DB%8C)" title="مجموعه (نوع داده انتزاعی) – Persian" lang="fa" hreflang="fa" data-title="مجموعه (نوع داده انتزاعی)" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Ensemble_(informatique)" title="Ensemble (informatique) – French" lang="fr" hreflang="fr" data-title="Ensemble (informatique)" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%A7%91%ED%95%A9_(%EC%B6%94%EC%83%81_%EC%9E%90%EB%A3%8C%ED%98%95)" title="집합 (추상 자료형) – Korean" lang="ko" hreflang="ko" data-title="집합 (추상 자료형)" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Set_(informatica)" title="Set (informatica) – Italian" lang="it" hreflang="it" data-title="Set (informatica)" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A7%D7%91%D7%95%D7%A6%D7%94_(%D7%9E%D7%91%D7%A0%D7%94_%D7%A0%D7%AA%D7%95%D7%A0%D7%99%D7%9D)" title="קבוצה (מבנה נתונים) – Hebrew" lang="he" hreflang="he" data-title="קבוצה (מבנה נתונים)" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Verzameling_(informatica)" title="Verzameling (informatica) – Dutch" lang="nl" hreflang="nl" data-title="Verzameling (informatica)" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%82%BB%E3%83%83%E3%83%88_(%E6%8A%BD%E8%B1%A1%E3%83%87%E3%83%BC%E3%82%BF%E5%9E%8B)" title="セット (抽象データ型) – Japanese" lang="ja" hreflang="ja" data-title="セット (抽象データ型)" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Sett_(abstrakt_datatype)" title="Sett (abstrakt datatype) – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="Sett (abstrakt datatype)" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Zbiorowy_typ_danych" title="Zbiorowy typ danych – Polish" lang="pl" hreflang="pl" data-title="Zbiorowy typ danych" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Conjunto_(tipo_de_dado_abstrato)" title="Conjunto (tipo de dado abstrato) – Portuguese" lang="pt" hreflang="pt" data-title="Conjunto (tipo de dado abstrato)" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE_(%D1%82%D0%B8%D0%BF_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="Множество (тип данных) – Russian" lang="ru" hreflang="ru" data-title="Множество (тип данных)" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%A1%D0%BA%D1%83%D0%BF_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%BF%D0%BE%D0%B4%D0%B0%D1%82%D0%B0%D0%BA%D0%B0)" title="Скуп (структура података) – Serbian" lang="sr" hreflang="sr" data-title="Скуп (структура података)" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-tl mw-list-item"><a href="https://tl.wikipedia.org/wiki/Pangkat_(tipo_ng_abstraktong_datos)" title="Pangkat (tipo ng abstraktong datos) – Tagalog" lang="tl" hreflang="tl" data-title="Pangkat (tipo ng abstraktong datos)" data-language-autonym="Tagalog" data-language-local-name="Tagalog" class="interlanguage-link-target"><span>Tagalog</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B9%80%E0%B8%8B%E0%B8%95_(%E0%B9%82%E0%B8%84%E0%B8%A3%E0%B8%87%E0%B8%AA%E0%B8%A3%E0%B9%89%E0%B8%B2%E0%B8%87%E0%B8%82%E0%B9%89%E0%B8%AD%E0%B8%A1%E0%B8%B9%E0%B8%A5)" title="เซต (โครงสร้างข้อมูล) – Thai" lang="th" hreflang="th" data-title="เซต (โครงสร้างข้อมูล)" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B8%D0%BD%D0%B0_(%D1%82%D0%B8%D0%BF_%D0%B4%D0%B0%D0%BD%D0%B8%D1%85)" title="Множина (тип даних) – Ukrainian" lang="uk" hreflang="uk" data-title="Множина (тип даних)" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E9%9B%86_(%E6%8A%BD%E8%B1%A1%E8%B3%87%E6%96%99%E9%A1%9E%E5%9E%8B)" title="集 (抽象資料類型) – Cantonese" lang="yue" hreflang="yue" data-title="集 (抽象資料類型)" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1514741#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Set_(abstract_data_type)" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Set_(abstract_data_type)" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Set_(abstract_data_type)"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Set_(abstract_data_type)&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Set_(abstract_data_type)"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Set_(abstract_data_type)&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Set_(abstract_data_type)" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Set_(abstract_data_type)" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Set_(abstract_data_type)&oldid=1223692548" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Set_(abstract_data_type)&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Set_%28abstract_data_type%29&id=1223692548&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FSet_%28abstract_data_type%29"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FSet_%28abstract_data_type%29"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Set_%28abstract_data_type%29&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Set_(abstract_data_type)&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1514741" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Abstract data type for storing unique values</div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-More_citations_needed plainlinks metadata ambox ambox-content ambox-Refimprove" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>needs additional citations for <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">verification</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Set_(abstract_data_type)" title="Special:EditPage/Set (abstract data type)">improve this article</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and removed.<br /><small><span class="plainlinks"><i>Find sources:</i> <a rel="nofollow" class="external text" href="https://www.google.com/search?as_eq=wikipedia&q=%22Set%22+abstract+data+type">"Set" abstract data type</a> – <a rel="nofollow" class="external text" href="https://www.google.com/search?tbm=nws&q=%22Set%22+abstract+data+type+-wikipedia&tbs=ar:1">news</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?&q=%22Set%22+abstract+data+type&tbs=bkt:s&tbm=bks">newspapers</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?tbs=bks:1&q=%22Set%22+abstract+data+type+-wikipedia">books</a> <b>·</b> <a rel="nofollow" class="external text" href="https://scholar.google.com/scholar?q=%22Set%22+abstract+data+type">scholar</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.jstor.org/action/doBasicSearch?Query=%22Set%22+abstract+data+type&acc=on&wc=on">JSTOR</a></span></small></span> <span class="date-container"><i>(<span class="date">October 2011</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a>, a <b>set</b> is an <a href="/wiki/Abstract_data_type" title="Abstract data type">abstract data type</a> that can store unique values, without any particular <a href="/wiki/Sequence" title="Sequence">order</a>. It is a computer implementation of the <a href="/wiki/Mathematics" title="Mathematics">mathematical</a> concept of a <a href="/wiki/Finite_set" title="Finite set">finite set</a>. Unlike most other <a href="/wiki/Collection_(abstract_data_type)" title="Collection (abstract data type)">collection</a> types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set. </p><p>Some set data structures are designed for <b>static</b> or <b>frozen sets</b> that do not change after they are constructed. Static sets allow only query operations on their elements — such as checking whether a given value is in the set, or enumerating the values in some arbitrary order. Other variants, called <b>dynamic</b> or <b>mutable sets</b>, allow also the insertion and deletion of elements from the set. </p><p>A <b><a href="/wiki/Multiset" title="Multiset">multiset</a></b> is a special kind of set in which an element can appear multiple times in the set. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Type_theory">Type theory</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=1" title="Edit section: Type theory"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In <a href="/wiki/Type_theory" title="Type theory">type theory</a>, sets are generally identified with their <a href="/wiki/Indicator_function" title="Indicator function">indicator function</a> (characteristic function): accordingly, a set of values of type <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}"></span> may be denoted by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{A}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>A</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{A}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bc6d28a1b787f8c321de35ccc9305fd6cbda9934" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.627ex; height:2.676ex;" alt="{\displaystyle 2^{A}}"></span> or <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {P}}(A)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>A</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}(A)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1757ec21abe0a22f8e91b51fe3e6ac4ea63a9122" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.256ex; height:2.843ex;" alt="{\displaystyle {\mathcal {P}}(A)}"></span>. (Subtypes and subsets may be modeled by <a href="/wiki/Refinement_type" title="Refinement type">refinement types</a>, and <a href="/wiki/Quotient_set" class="mw-redirect" title="Quotient set">quotient sets</a> may be replaced by <a href="/wiki/Setoid" title="Setoid">setoids</a>.) The characteristic function <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/545fd099af8541605f7ee55f08225526be88ce57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}"></span> of a set <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span> is defined as: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(x)={\begin{cases}1,&{\mbox{if }}x\in S\\0,&{\mbox{if }}x\not \in S\end{cases}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>{</mo> <mtable columnalign="left left" rowspacing=".2em" columnspacing="1em" displaystyle="false"> <mtr> <mtd> <mn>1</mn> <mo>,</mo> </mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mtext>if </mtext> </mstyle> </mrow> <mi>x</mi> <mo>∈</mo> <mi>S</mi> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> <mo>,</mo> </mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mtext>if </mtext> </mstyle> </mrow> <mi>x</mi> <mo>∉</mo> <mi>S</mi> </mtd> </mtr> </mtable> <mo fence="true" stretchy="true" symmetric="true"></mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(x)={\begin{cases}1,&{\mbox{if }}x\in S\\0,&{\mbox{if }}x\not \in S\end{cases}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f48c9976184b7c2558d35f7c2fda64afa1443dcb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:22.214ex; height:6.176ex;" alt="{\displaystyle F(x)={\begin{cases}1,&{\mbox{if }}x\in S\\0,&{\mbox{if }}x\not \in S\end{cases}}}"></span></dd></dl> <p>In theory, many other abstract data structures can be viewed as set structures with additional operations and/or additional <a href="/wiki/Axiom" title="Axiom">axioms</a> imposed on the standard operations. For example, an abstract <a href="/wiki/Heap_data_structure" class="mw-redirect" title="Heap data structure">heap</a> can be viewed as a set structure with a <code>min(<i>S</i>)</code> operation that returns the element of smallest value. </p> <div class="mw-heading mw-heading2"><h2 id="Operations">Operations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=2" title="Edit section: Operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Core_set-theoretical_operations">Core set-theoretical operations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=3" title="Edit section: Core set-theoretical operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>One may define the operations of the <a href="/wiki/Algebra_of_sets" title="Algebra of sets">algebra of sets</a>: </p> <ul><li><code>union(<i>S</i>,<i>T</i>)</code>: returns the <a href="/wiki/Union_(set_theory)" title="Union (set theory)">union</a> of sets <i>S</i> and <i>T</i>.</li> <li><code>intersection(<i>S</i>,<i>T</i>)</code>: returns the <a href="/wiki/Intersection_(set_theory)" title="Intersection (set theory)">intersection</a> of sets <i>S</i> and <i>T</i>.</li> <li><code>difference(<i>S</i>,<i>T</i>)</code>: returns the <a href="/wiki/Difference_(set_theory)" class="mw-redirect" title="Difference (set theory)">difference</a> of sets <i>S</i> and <i>T</i>.</li> <li><code>subset(<i>S</i>,<i>T</i>)</code>: a predicate that tests whether the set <i>S</i> is a <a href="/wiki/Subset" title="Subset">subset</a> of set <i>T</i>.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Static_sets">Static sets</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=4" title="Edit section: Static sets"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Typical operations that may be provided by a static set structure <i>S</i> are: </p> <ul><li><code>is_element_of(<i>x</i>,<i>S</i>)</code>: checks whether the value <i>x</i> is in the set <i>S</i>.</li> <li><code>is_empty(<i>S</i>)</code>: checks whether the set <i>S</i> is empty.</li> <li><code>size(<i>S</i>)</code> or <code><a href="/wiki/Cardinality" title="Cardinality">cardinality</a>(<i>S</i>)</code>: returns the number of elements in <i>S</i>.</li> <li><code><a href="/wiki/Iterator" title="Iterator">iterate</a>(<i>S</i>)</code>: returns a function that returns one more value of <i>S</i> at each call, in some arbitrary order.</li> <li><code>enumerate(<i>S</i>)</code>: returns a list containing the elements of <i>S</i> in some arbitrary order.</li> <li><code>build(<i>x</i><sub>1</sub>,<i>x</i><sub>2</sub>,…,<i>x</i><sub><i>n</i></sub>,)</code>: creates a set structure with values <i>x</i><sub>1</sub>,<i>x</i><sub>2</sub>,...,<i>x</i><sub><i>n</i></sub>.</li> <li><code>create_from(<i>collection</i>)</code>: creates a new set structure containing all the elements of the given <a href="/wiki/Collection_(abstract_data_type)" title="Collection (abstract data type)">collection</a> or all the elements returned by the given <a href="/wiki/Iterator" title="Iterator">iterator</a>.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Dynamic_sets">Dynamic sets</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=5" title="Edit section: Dynamic sets"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Dynamic set structures typically add: </p> <ul><li><code>create()</code>: creates a new, initially empty set structure. <ul><li><code>create_with_capacity(<i>n</i>)</code>: creates a new set structure, initially empty but capable of holding up to <i>n</i> elements.</li></ul></li> <li><code>add(<i>S</i>,<i>x</i>)</code>: adds the element <i>x</i> to <i>S</i>, if it is not present already.</li> <li><code>remove(<i>S</i>, <i>x</i>)</code>: removes the element <i>x</i> from <i>S</i>, if it is present.</li> <li><code>capacity(<i>S</i>)</code>: returns the maximum number of values that <i>S</i> can hold.</li></ul> <p>Some set structures may allow only some of these operations. The cost of each operation will depend on the implementation, and possibly also on the particular values stored in the set, and the order in which they are inserted. </p> <div class="mw-heading mw-heading3"><h3 id="Additional_operations">Additional operations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=6" title="Edit section: Additional operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There are many other operations that can (in principle) be defined in terms of the above, such as: </p> <ul><li><code>pop(<i>S</i>)</code>: returns an arbitrary element of <i>S</i>, deleting it from <i>S</i>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></li> <li><code>pick(<i>S</i>)</code>: returns an arbitrary element of <i>S</i>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Functionally, the mutator <code>pop</code> can be interpreted as the pair of selectors <code>(pick, rest),</code> where <code>rest</code> returns the set consisting of all elements except for the arbitrary element.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Can be interpreted in terms of <code>iterate</code>.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>a<span class="cite-bracket">]</span></a></sup></li> <li><code><a href="/wiki/Map_(higher-order_function)" title="Map (higher-order function)">map</a>(<i>F</i>,<i>S</i>)</code>: returns the set of distinct values resulting from applying function <i>F</i> to each element of <i>S</i>.</li> <li><code><a href="/wiki/Filter_(higher-order_function)" title="Filter (higher-order function)">filter</a>(<i>P</i>,<i>S</i>)</code>: returns the subset containing all elements of <i>S</i> that satisfy a given <a href="/wiki/Predicate_(mathematical_logic)" title="Predicate (mathematical logic)">predicate</a> <i>P</i>.</li> <li><code><a href="/wiki/Fold_(higher-order_function)" title="Fold (higher-order function)">fold</a>(<i>A</i><sub>0</sub>,<i>F</i>,<i>S</i>)</code>: returns the value <i>A</i><sub>|<i>S</i>|</sub> after applying <code><i>A</i><sub>i+1</sub> := <i>F</i>(<i>A<sub>i</sub></i>, <i>e</i>)</code> for each element <i>e</i> of <i>S,</i> for some binary operation <i>F.</i> <i>F</i> must be associative and commutative for this to be well-defined.</li> <li><code>clear(<i>S</i>)</code>: delete all elements of <i>S</i>.</li> <li><code>equal(<i>S</i><sub>1</sub>', <i>S</i><sub>2</sub>')</code>: checks whether the two given sets are equal (i.e. contain all and only the same elements).</li> <li><code>hash(<i>S</i>)</code>: returns a <a href="/wiki/Hash_value" class="mw-redirect" title="Hash value">hash value</a> for the static set <i>S</i> such that if <code>equal(<i>S</i><sub>1</sub>, <i>S</i><sub>2</sub>)</code> then <code>hash(<i>S<sub>1</sub></i>) = hash(<i>S<sub>2</sub></i>)</code></li></ul> <p>Other operations can be defined for sets with elements of a special type: </p> <ul><li><code>sum(<i>S</i>)</code>: returns the sum of all elements of <i>S</i> for some definition of "sum". For example, over integers or reals, it may be defined as <code>fold(0, add, <i>S</i>)</code>.</li> <li><code>collapse(<i>S</i>)</code>: given a set of sets, return the union.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> For example, <code>collapse({{1}, {2, 3}}) == {1, 2, 3}</code>. May be considered a kind of <code>sum</code>.</li> <li><code>flatten(<i>S</i>)</code>: given a set consisting of sets and atomic elements (elements that are not sets), returns a set whose elements are the atomic elements of the original top-level set or elements of the sets it contains. In other words, remove a level of nesting – like <code>collapse,</code> but allow atoms. This can be done a single time, or recursively flattening to obtain a set of only atomic elements.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> For example, <code>flatten({1, {2, 3}}) == {1, 2, 3}</code>.</li> <li><code>nearest(<i>S</i>,<i>x</i>)</code>: returns the element of <i>S</i> that is closest in value to <i>x</i> (by some <a href="/wiki/Metric_(mathematics)" class="mw-redirect" title="Metric (mathematics)">metric</a>).</li> <li><code>min(<i>S</i>)</code>, <code>max(<i>S</i>)</code>: returns the minimum/maximum element of <i>S</i>.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Implementations">Implementations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=7" title="Edit section: Implementations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Sets can be implemented using various <a href="/wiki/Data_structure" title="Data structure">data structures</a>, which provide different time and space trade-offs for various operations. Some implementations are designed to improve the efficiency of very specialized operations, such as <code>nearest</code> or <code>union</code>. Implementations described as "general use" typically strive to optimize the <code>element_of</code>, <code>add</code>, and <code>delete</code> operations. A simple implementation is to use a <a href="/wiki/List_(abstract_data_type)" title="List (abstract data type)">list</a>, ignoring the order of the elements and taking care to avoid repeated values. This is simple but inefficient, as operations like set membership or element deletion are <i>O</i>(<i>n</i>), as they require scanning the entire list.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>b<span class="cite-bracket">]</span></a></sup> Sets are often instead implemented using more efficient data structures, particularly various flavors of <a href="/wiki/Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">trees</a>, <a href="/wiki/Trie" title="Trie">tries</a>, or <a href="/wiki/Hash_tables" class="mw-redirect" title="Hash tables">hash tables</a>. </p><p>As sets can be interpreted as a kind of map (by the indicator function), sets are commonly implemented in the same way as (partial) maps (<a href="/wiki/Associative_array" title="Associative array">associative arrays</a>) – in this case in which the value of each key-value pair has the <a href="/wiki/Unit_type" title="Unit type">unit type</a> or a sentinel value (like 1) – namely, a <a href="/wiki/Self-balancing_binary_search_tree" title="Self-balancing binary search tree">self-balancing binary search tree</a> for sorted sets<sup class="noprint Inline-Template" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Please_clarify" title="Wikipedia:Please clarify"><span title="You can help -- (November 2020)">definition needed</span></a></i>]</sup> (which has O(log n) for most operations), or a <a href="/wiki/Hash_table" title="Hash table">hash table</a> for unsorted sets (which has O(1) average-case, but O(n) worst-case, for most operations). A sorted linear hash table<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> may be used to provide deterministically ordered sets. </p><p>Further, in languages that support maps but not sets, sets can be implemented in terms of maps. For example, a common <a href="/wiki/Programming_idiom" title="Programming idiom">programming idiom</a> in <a href="/wiki/Perl" title="Perl">Perl</a> that converts an array to a hash whose values are the sentinel value 1, for use as a set, is: </p> <div class="mw-highlight mw-highlight-lang-perl mw-content-ltr" dir="ltr"><pre><span></span><span class="k">my</span><span class="w"> </span><span class="nv">%elements</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nb">map</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="nv">$_</span><span class="w"> </span><span class="o">=></span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="p">}</span><span class="w"> </span><span class="nv">@elements</span><span class="p">;</span> </pre></div> <p>Other popular methods include <a href="/wiki/Array_data_structure" class="mw-redirect" title="Array data structure">arrays</a>. In particular a subset of the integers 1..<i>n</i> can be implemented efficiently as an <i>n</i>-bit <a href="/wiki/Bit_array" title="Bit array">bit array</a>, which also support very efficient union and intersection operations. A <a href="/wiki/Bloom_map" class="mw-redirect" title="Bloom map">Bloom map</a> implements a set probabilistically, using a very compact representation but risking a small chance of false positives on queries. </p><p>The Boolean set operations can be implemented in terms of more elementary operations (<code>pop</code>, <code>clear</code>, and <code>add</code>), but specialized algorithms may yield lower asymptotic time bounds. If sets are implemented as sorted lists, for example, the naive algorithm for <code>union(<i>S</i>,<i>T</i>)</code> will take time proportional to the length <i>m</i> of <i>S</i> times the length <i>n</i> of <i>T</i>; whereas a variant of the <a href="/wiki/Merge_algorithm" title="Merge algorithm">list merging algorithm</a> will do the job in time proportional to <i>m</i>+<i>n</i>. Moreover, there are specialized set data structures (such as the <a href="/wiki/Union-find_algorithm" class="mw-redirect" title="Union-find algorithm">union-find data structure</a>) that are optimized for one or more of these operations, at the expense of others. </p> <div class="mw-heading mw-heading2"><h2 id="Language_support">Language support</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=8" title="Edit section: Language support"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>One of the earliest languages to support sets was <a href="/wiki/Pascal_programming_language" class="mw-redirect" title="Pascal programming language">Pascal</a>; many languages now include it, whether in the core language or in a <a href="/wiki/Standard_library" title="Standard library">standard library</a>. </p> <ul><li>In <a href="/wiki/C%2B%2B" title="C++">C++</a>, the <a href="/wiki/Standard_Template_Library" title="Standard Template Library">Standard Template Library</a> (STL) provides the <code><a href="/wiki/Set_(C%2B%2B)" class="mw-redirect" title="Set (C++)">set</a></code> template class, which is typically implemented using a binary search tree (e.g. <a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">red–black tree</a>); <a href="/wiki/Silicon_Graphics_International" title="Silicon Graphics International">SGI</a>'s STL also provides the <code>hash_set</code> template class, which implements a set using a hash table. <a href="/wiki/C%2B%2B11" title="C++11">C++11</a> has support for the <code><a href="/wiki/Unordered_set_(C%2B%2B)" class="mw-redirect" title="Unordered set (C++)">unordered_set</a></code> template class, which is implemented using a hash table. In sets, the elements themselves are the keys, in contrast to sequenced containers, where elements are accessed using their (relative or absolute) position. Set elements must have a strict weak ordering.</li> <li>The <a href="/wiki/Rust_(programming_language)" title="Rust (programming language)">Rust</a> standard library provides the generic <code><a rel="nofollow" class="external text" href="https://doc.rust-lang.org/std/collections/struct.HashSet.html">HashSet</a></code> and <code><a rel="nofollow" class="external text" href="https://doc.rust-lang.org/std/collections/struct.BTreeSet.html">BTreeSet</a></code> types.</li> <li><a href="/wiki/Java_(programming_language)" title="Java (programming language)">Java</a> offers the <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/Set.html">Set</a></code> <a href="/wiki/Interface_(computer_science)" class="mw-redirect" title="Interface (computer science)">interface</a> to support sets (with the <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/HashSet.html">HashSet</a></code> class implementing it using a hash table), and the <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/SortedSet.html">SortedSet</a></code> sub-interface to support sorted sets (with the <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/TreeSet.html">TreeSet</a></code> class implementing it using a binary search tree).</li> <li><a href="/wiki/Apple_Inc." title="Apple Inc.">Apple</a>'s <a href="/wiki/Foundation_Kit" title="Foundation Kit">Foundation framework</a> (part of <a href="/wiki/Cocoa_(API)" title="Cocoa (API)">Cocoa</a>) provides the <a href="/wiki/Objective-C" title="Objective-C">Objective-C</a> classes <code><a rel="nofollow" class="external text" href="https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSSet_Class/">NSSet</a></code>, <code><a rel="nofollow" class="external text" href="https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSMutableSet_Class/">NSMutableSet</a></code>, <code><a rel="nofollow" class="external text" href="https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSCountedSet_Class/">NSCountedSet</a></code>, <code><a rel="nofollow" class="external text" href="https://developer.apple.com/library/mac/#documentation/Foundation/Reference/NSOrderedSet_Class/Reference/Reference.html">NSOrderedSet</a></code>, and <code><a rel="nofollow" class="external text" href="https://developer.apple.com/library/mac/#documentation/Foundation/Reference/NSMutableOrderedSet_Class/Reference/Reference.html">NSMutableOrderedSet</a></code>. The <a href="/wiki/CoreFoundation" class="mw-redirect" title="CoreFoundation">CoreFoundation</a> APIs provide the <a rel="nofollow" class="external text" href="https://developer.apple.com/documentation/CoreFoundation/Reference/CFSetRef/">CFSet</a> and <a rel="nofollow" class="external text" href="https://developer.apple.com/documentation/CoreFoundation/Reference/CFMutableSetRef/">CFMutableSet</a> types for use in <a href="/wiki/C_(programming_language)" title="C (programming language)">C</a>.</li> <li><a href="/wiki/Python_(programming_language)" title="Python (programming language)">Python</a> has built-in <a rel="nofollow" class="external text" href="https://docs.python.org/library/stdtypes.html#set-types-set-frozenset"><code>set</code> and <code>frozenset</code> types</a> since 2.4, and since Python 3.0 and 2.7, supports non-empty set literals using a curly-bracket syntax, e.g.: <code>{x, y, z}</code>; empty sets must be created using <code>set()</code>, because Python uses <code>{}</code> to represent the empty dictionary.</li> <li>The <a href="/wiki/.NET_Framework" title=".NET Framework">.NET Framework</a> provides the generic <code><a rel="nofollow" class="external text" href="http://msdn.microsoft.com/en-us/library/bb359438.aspx">HashSet</a></code> and <code><a rel="nofollow" class="external text" href="http://msdn.microsoft.com/en-us/library/dd412070.aspx">SortedSet</a></code> classes that implement the generic <code><a rel="nofollow" class="external text" href="http://msdn.microsoft.com/en-us/library/dd412081.aspx">ISet</a></code> interface.</li> <li><a href="/wiki/Smalltalk" title="Smalltalk">Smalltalk</a>'s class library includes <code>Set</code> and <code>IdentitySet</code>, using equality and identity for inclusion test respectively. Many dialects provide variations for compressed storage (<code>NumberSet</code>, <code>CharacterSet</code>), for ordering (<code>OrderedSet</code>, <code>SortedSet</code>, etc.) or for <a href="/wiki/Weak_reference" title="Weak reference">weak references</a> (<code>WeakIdentitySet</code>).</li> <li><a href="/wiki/Ruby_(programming_language)" title="Ruby (programming language)">Ruby</a>'s standard library includes a <code><a rel="nofollow" class="external text" href="http://ruby-doc.org/stdlib/libdoc/set/rdoc/index.html">set</a></code> module which contains <code>Set</code> and <code>SortedSet</code> classes that implement sets using hash tables, the latter allowing iteration in sorted order.</li> <li><a href="/wiki/OCaml" title="OCaml">OCaml</a>'s standard library contains a <code>Set</code> module, which implements a functional set data structure using binary search trees.</li> <li>The <a href="/wiki/Glasgow_Haskell_Compiler" title="Glasgow Haskell Compiler">GHC</a> implementation of <a href="/wiki/Haskell_(programming_language)" class="mw-redirect" title="Haskell (programming language)">Haskell</a> provides a <code><a rel="nofollow" class="external text" href="https://hackage.haskell.org/package/containers/docs/Data-Set.html">Data.Set</a></code> module, which implements immutable sets using binary search trees.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup></li> <li>The <a href="/wiki/Tcl" title="Tcl">Tcl</a> <a href="/wiki/Tcllib" class="mw-redirect" title="Tcllib">Tcllib</a> package provides a set module which implements a set data structure based upon TCL lists.</li> <li>The <a href="/wiki/Swift_(programming_language)" title="Swift (programming language)">Swift</a> standard library contains a <code>Set</code> type, since Swift 1.2.</li> <li><a href="/wiki/JavaScript" title="JavaScript">JavaScript</a> introduced <code><a rel="nofollow" class="external text" href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set">Set</a></code> as a standard built-in object with the ECMAScript 2015<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> standard.</li> <li><a href="/wiki/Erlang_(programming_language)" title="Erlang (programming language)">Erlang</a>'s standard library has a <code><a rel="nofollow" class="external text" href="http://erlang.org/doc/man/sets.html">sets</a></code> module.</li> <li><a href="/wiki/Clojure" title="Clojure">Clojure</a> has literal syntax for hashed sets, and also implements sorted sets.</li> <li><a href="/wiki/LabVIEW" title="LabVIEW">LabVIEW</a> has native support for sets, from version 2019.</li> <li><a href="/wiki/Ada_(programming_language)" title="Ada (programming language)">Ada</a> provides the <code><a rel="nofollow" class="external text" href="http://www.ada-auth.org/standards/12rm/html/RM-A-18-8.html">Ada.Containers.Hashed_Sets</a></code> and <code><a rel="nofollow" class="external text" href="http://www.ada-auth.org/standards/12rm/html/RM-A-18-9.html">Ada.Containers.Ordered_Sets</a></code> packages.</li></ul> <p>As noted in the previous section, in languages which do not directly support sets but do support <a href="/wiki/Associative_array" title="Associative array">associative arrays</a>, sets can be emulated using associative arrays, by using the elements as keys, and using a dummy value as the values, which are ignored. </p> <div class="mw-heading mw-heading2"><h2 id="Multiset">Multiset</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=9" title="Edit section: Multiset"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Multiset" title="Multiset">Multiset</a></div> <p>A generalization of the notion of a set is that of a <b><a href="/wiki/Multiset" title="Multiset">multiset</a></b> or <b>bag</b>, which is similar to a set but allows repeated ("equal") values (duplicates). This is used in two distinct senses: either equal values are considered <i>identical,</i> and are simply counted, or equal values are considered <i>equivalent,</i> and are stored as distinct items. For example, given a list of people (by name) and ages (in years), one could construct a multiset of ages, which simply counts the number of people of a given age. Alternatively, one can construct a multiset of people, where two people are considered equivalent if their ages are the same (but may be different people and have different names), in which case each pair (name, age) must be stored, and selecting on a given age gives all the people of a given age. </p><p>Formally, it is possible for objects in computer science to be considered "equal" under some <a href="/wiki/Equivalence_relation" title="Equivalence relation">equivalence relation</a> but still distinct under another relation. Some types of multiset implementations will store distinct equal objects as separate items in the data structure; while others will collapse it down to one version (the first one encountered) and keep a positive integer count of the multiplicity of the element. </p><p>As with sets, multisets can naturally be implemented using hash table or trees, which yield different performance characteristics. </p><p>The set of all bags over type T is given by the expression bag T. If by multiset one considers equal items identical and simply counts them, then a multiset can be interpreted as a function from the input domain to the non-negative integers (<a href="/wiki/Natural_number" title="Natural number">natural numbers</a>), generalizing the identification of a set with its indicator function. In some cases a multiset in this counting sense may be generalized to allow negative values, as in Python. </p> <ul><li>C++'s <a href="/wiki/Standard_Template_Library" title="Standard Template Library">Standard Template Library</a> implements both sorted and unsorted multisets. It provides the <code><a href="/wiki/Multiset_(C%2B%2B)" class="mw-redirect" title="Multiset (C++)">multiset</a></code> class for the sorted multiset, as a kind of <a href="/wiki/Associative_containers_(C%2B%2B)" title="Associative containers (C++)">associative container</a>, which implements this multiset using a <a href="/wiki/Self-balancing_binary_search_tree" title="Self-balancing binary search tree">self-balancing binary search tree</a>. It provides the <code>unordered_multiset</code> class for the unsorted multiset, as a kind of <a href="/wiki/Unordered_associative_containers_(C%2B%2B)" title="Unordered associative containers (C++)">unordered associative container</a>, which implements this multiset using a <a href="/wiki/Hash_table" title="Hash table">hash table</a>. The unsorted multiset is standard as of <a href="/wiki/C%2B%2B11" title="C++11">C++11</a>; previously SGI's STL provides the <code>hash_multiset</code> class, which was copied and eventually standardized.</li> <li>For <a href="/wiki/Java_(programming_language)" title="Java (programming language)">Java</a>, third-party libraries provide multiset functionality: <ul><li><a href="/wiki/Apache_Commons" title="Apache Commons">Apache Commons</a> Collections provides the <code><a rel="nofollow" class="external text" href="https://web.archive.org/web/20150109083430/https://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/Bag.html">Bag</a></code> and <code>SortedBag</code> interfaces, with implementing classes like <code>HashBag</code> and <code>TreeBag</code>.</li> <li><a href="/wiki/Google_Guava" title="Google Guava">Google Guava</a> provides the <code><a rel="nofollow" class="external text" href="https://google.github.io/guava/releases/20.0/api/docs/com/google/common/collect/Multiset.html">Multiset</a></code> interface, with implementing classes like <code><a rel="nofollow" class="external text" href="https://guava.dev/releases/20.0/api/docs/com/google/common/collect/HashMultiset.html">HashMultiset</a></code> and <code><a rel="nofollow" class="external text" href="https://guava.dev/releases/20.0/api/docs/com/google/common/collect/TreeMultiset.html">TreeMultiset</a></code>.</li></ul></li> <li>Apple provides the <code><a rel="nofollow" class="external text" href="https://developer.apple.com/documentation/foundation/nscountedset">NSCountedSet</a></code> class as part of <a href="/wiki/Cocoa_(API)" title="Cocoa (API)">Cocoa</a>, and the <code><a rel="nofollow" class="external text" href="https://developer.apple.com/documentation/corefoundation/cfbag-s1l">CFBag</a></code> and <code><a rel="nofollow" class="external text" href="https://developer.apple.com/documentation/corefoundation/cfmutablebag-rqn">CFMutableBag</a></code> types as part of <a href="/wiki/CoreFoundation" class="mw-redirect" title="CoreFoundation">CoreFoundation</a>.</li> <li><a href="/wiki/Python_(programming_language)" title="Python (programming language)">Python's</a> standard library includes <code><a rel="nofollow" class="external text" href="https://docs.python.org/library/collections.html#collections.Counter">collections.Counter</a></code>, which is similar to a multiset.</li> <li><a href="/wiki/Smalltalk" title="Smalltalk">Smalltalk</a> includes the <code>Bag</code> class, which can be instantiated to use either identity or equality as predicate for inclusion test.</li></ul> <p>Where a multiset data structure is not available, a workaround is to use a regular set, but override the equality predicate of its items to always return "not equal" on distinct objects (however, such will still not be able to store multiple occurrences of the same object) or use an <a href="/wiki/Associative_array" title="Associative array">associative array</a> mapping the values to their integer multiplicities (this will not be able to distinguish between equal elements at all). </p><p>Typical operations on bags: </p> <ul><li><code>contains(<i>B</i>, <i>x</i>)</code>: checks whether the element <i>x</i> is present (at least once) in the bag <i>B</i></li> <li><code>is_sub_bag(<i>B</i><sub>1</sub>, <i>B</i><sub>2</sub>)</code>: checks whether each element in the bag <i>B</i><sub>1</sub> occurs in <i>B</i><sub>1</sub> no more often than it occurs in the bag <i>B</i><sub>2</sub>; sometimes denoted as <i>B</i><sub>1</sub> ⊑ <i>B</i><sub>2</sub>.</li> <li><code>count(<i>B</i>, <i>x</i>)</code>: returns the number of times that the element <i>x</i> occurs in the bag <i>B</i>; sometimes denoted as <i>B</i> # <i>x</i>.</li> <li><code>scaled_by(<i>B</i>, <i>n</i>)</code>: given a <a href="/wiki/Natural_number" title="Natural number">natural number</a> <i>n</i>, returns a bag which contains the same elements as the bag <i>B</i>, except that every element that occurs <i>m</i> times in <i>B</i> occurs <i>n</i> * <i>m</i> times in the resulting bag; sometimes denoted as <i>n</i> ⊗ <i>B</i>.</li> <li><code>union(<i>B</i><sub>1</sub>, <i>B</i><sub>2</sub>)</code>: returns a bag containing just those values that occur in either the bag <i>B</i><sub>1</sub> or the bag <i>B</i><sub>2</sub>, except that the number of times a value <i>x</i> occurs in the resulting bag is equal to (<i>B</i><sub>1</sub> # x) + (<i>B</i><sub>2</sub> # x); sometimes denoted as <i>B</i><sub>1</sub> ⊎ <i>B</i><sub>2</sub>.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Multisets_in_SQL">Multisets in SQL</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=10" title="Edit section: Multisets in SQL"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In <a href="/wiki/Relational_database_management_system" class="mw-redirect" title="Relational database management system">relational databases</a>, a table can be a (mathematical) set or a multiset, depending on the presence of unicity constraints on some columns (which turns it into a <a href="/wiki/Candidate_key" title="Candidate key">candidate key</a>). </p><p><a href="/wiki/SQL" title="SQL">SQL</a> allows the selection of rows from a relational table: this operation will in general yield a multiset, unless the keyword <code>DISTINCT</code> is used to force the rows to be all different, or the selection includes the primary (or a candidate) key. </p><p>In <a href="/wiki/SQL#Standardization_history" title="SQL">ANSI SQL</a> the <code>MULTISET</code> keyword can be used to transform a subquery into a collection expression: </p> <div class="mw-highlight mw-highlight-lang-sql mw-content-ltr" dir="ltr"><pre><span></span><span class="k">SELECT</span><span class="w"> </span><span class="n">expression1</span><span class="p">,</span><span class="w"> </span><span class="n">expression2</span><span class="p">...</span><span class="w"> </span><span class="k">FROM</span><span class="w"> </span><span class="k">table_name</span><span class="p">...</span> </pre></div> <p>is a general select that can be used as <i><a href="/w/index.php?title=Subquery_expression&action=edit&redlink=1" class="new" title="Subquery expression (page does not exist)">subquery expression</a></i> of another more general query, while </p> <div class="mw-highlight mw-highlight-lang-sql mw-content-ltr" dir="ltr"><pre><span></span><span class="n">MULTISET</span><span class="p">(</span><span class="k">SELECT</span><span class="w"> </span><span class="n">expression1</span><span class="p">,</span><span class="w"> </span><span class="n">expression2</span><span class="p">...</span><span class="w"> </span><span class="k">FROM</span><span class="w"> </span><span class="k">table_name</span><span class="p">...)</span> </pre></div> <p>transforms the subquery into a <i><a href="/w/index.php?title=Collection_expression&action=edit&redlink=1" class="new" title="Collection expression (page does not exist)">collection expression</a></i> that can be used in another query, or in assignment to a column of appropriate collection type. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=11" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Bloom_filter" title="Bloom filter">Bloom filter</a></li> <li><a href="/wiki/Disjoint_set_(data_structure)" class="mw-redirect" title="Disjoint set (data structure)">Disjoint set</a></li> <li><a href="/wiki/Set_(mathematics)" title="Set (mathematics)">Set (mathematics)</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=12" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-lower-alpha"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">For example, in Python <code>pick</code> can be implemented on a derived class of the built-in <code>set</code> as follows: <div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre><span></span><span class="k">class</span> <span class="nc">Set</span><span class="p">(</span><span class="nb">set</span><span class="p">):</span> <span class="k">def</span> <span class="nf">pick</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="nb">next</span><span class="p">(</span><span class="nb">iter</span><span class="p">(</span><span class="bp">self</span><span class="p">))</span> </pre></div></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text">Element insertion can be done in <i>O</i>(1) time by simply inserting at an end, but if one avoids duplicates this takes <i>O</i>(<i>n</i>) time.</span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Set_(abstract_data_type)&action=edit&section=13" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239543626"><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Python: <a rel="nofollow" class="external text" href="https://docs.python.org/3/library/stdtypes.html#set.pop">pop()</a></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><i>Management and Processing of Complex Data Structures: Third Workshop on Information Systems and Artificial Intelligence, Hamburg, Germany, February 28 - March 2, 1994. Proceedings,</i> ed. Kai v. Luck, Heinz Marburger, <a rel="nofollow" class="external text" href="https://books.google.com/books?id=ymhoQ3y0vccC&q=pick&pg=PA76">p. 76</a></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">Python <a rel="nofollow" class="external text" href="http://bugs.python.org/issue7212">Issue7212</a>: Retrieve an arbitrary element from a set without removing it; see <a rel="nofollow" class="external text" href="http://bugs.python.org/issue7212#msg106593">msg106593</a> regarding standard name</span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">Ruby <a rel="nofollow" class="external text" href="https://bugs.ruby-lang.org/issues/4553">Feature #4553</a>: Add Set#pick and Set#pop</span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><i>Inductive Synthesis of Functional Programs: Universal Planning, Folding of Finite Programs, and Schema Abstraction by Analogical Reasoning,</i> <a href="/wiki/Ute_Schmid" title="Ute Schmid">Ute Schmid</a>, Springer, Aug 21, 2003, <a rel="nofollow" class="external text" href="https://books.google.com/books?id=p-Fy25LE4lMC&q=pick&pg=PA240">p. 240</a></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><i>Recent Trends in Data Type Specification: 10th Workshop on Specification of Abstract Data Types Joint with the 5th COMPASS Workshop, S. Margherita, Italy, May 30 - June 3, 1994. Selected Papers, Volume 10,</i> ed. Egidio Astesiano, Gianna Reggio, Andrzej Tarlecki, <a rel="nofollow" class="external text" href="https://books.google.com/books?id=LkvQYL23v1sC&q=collapse&pg=PA38">p. 38</a></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">Ruby: <a rel="nofollow" class="external text" href="http://www.ruby-doc.org/stdlib-2.1.2/libdoc/set/rdoc/Set.html#method-i-flatten">flatten()</a></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFWang1997" class="citation cs2">Wang, Thomas (1997), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20060112115812/http://www.concentric.net/~Ttwang/tech/sorthash.htm"><i>Sorted Linear Hash Table</i></a>, archived from <a rel="nofollow" class="external text" href="http://www.concentric.net/~Ttwang/tech/sorthash.htm">the original</a> on 2006-01-12</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Sorted+Linear+Hash+Table&rft.date=1997&rft.aulast=Wang&rft.aufirst=Thomas&rft_id=http%3A%2F%2Fwww.concentric.net%2F~Ttwang%2Ftech%2Fsorthash.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASet+%28abstract+data+type%29" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">Stephen Adams, <a rel="nofollow" class="external text" href="http://www.swiss.ai.mit.edu/~adams/BB">"<i>Efficient sets: a balancing act</i>"</a>, Journal of Functional Programming 3(4):553-562, October 1993. Retrieved on 2015-03-11.</span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.ecma-international.org/ecma-262/6.0/#sec-set-objects">"ECMAScript 2015 Language Specification – ECMA-262 6th Edition"</a>. <i>www.ecma-international.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2017-07-11</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=www.ecma-international.org&rft.atitle=ECMAScript+2015+Language+Specification+%E2%80%93+ECMA-262+6th+Edition&rft_id=http%3A%2F%2Fwww.ecma-international.org%2Fecma-262%2F6.0%2F%23sec-set-objects&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASet+%28abstract+data+type%29" class="Z3988"></span></span> </li> </ol></div></div> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Data_types177" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Data_types" title="Template:Data types"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Data_types" title="Template talk:Data types"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Data_types" title="Special:EditPage/Template:Data types"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Data_types177" style="font-size:114%;margin:0 4em"><a href="/wiki/Data_type" title="Data type">Data types</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Units_of_information" title="Units of information">Uninterpreted</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bit" title="Bit">Bit</a></li> <li><a href="/wiki/Byte" title="Byte">Byte</a></li> <li><a href="/wiki/Ternary_numeral_system" title="Ternary numeral system">Trit</a></li> <li><a href="/wiki/Ternary_numeral_system#Tryte" title="Ternary numeral system">Tryte</a></li> <li><a href="/wiki/Word_(computer_architecture)" title="Word (computer architecture)">Word</a></li> <li><a href="/wiki/Bit_array" title="Bit array">Bit array</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Numeric</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Arbitrary-precision_arithmetic" title="Arbitrary-precision arithmetic">Arbitrary-precision or bignum</a></li> <li><a href="/wiki/Complex_data_type" title="Complex data type">Complex</a></li> <li><a href="/wiki/Decimal_data_type" title="Decimal data type">Decimal</a></li> <li><a href="/wiki/Fixed-point_arithmetic" title="Fixed-point arithmetic">Fixed point</a></li> <li><a href="/wiki/Floating-point_arithmetic" title="Floating-point arithmetic">Floating point</a> <ul><li>Reduced precision <ul><li><a href="/wiki/Minifloat" title="Minifloat">Minifloat</a></li> <li><a href="/wiki/Half-precision_floating-point_format" title="Half-precision floating-point format">Half precision</a></li> <li><a href="/wiki/Bfloat16_floating-point_format" title="Bfloat16 floating-point format">bfloat16</a></li></ul></li> <li><a href="/wiki/Single-precision_floating-point_format" title="Single-precision floating-point format">Single precision</a></li> <li><a href="/wiki/Double-precision_floating-point_format" title="Double-precision floating-point format">Double precision</a></li> <li><a href="/wiki/Quadruple-precision_floating-point_format" title="Quadruple-precision floating-point format">Quadruple precision</a></li> <li><a href="/wiki/Octuple-precision_floating-point_format" title="Octuple-precision floating-point format">Octuple precision</a></li> <li><a href="/wiki/Extended_precision" title="Extended precision">Extended precision</a> <ul><li><a href="/wiki/Long_double" title="Long double">Long double</a></li></ul></li></ul></li> <li><a href="/wiki/Integer_(computer_science)" title="Integer (computer science)">Integer</a> <ul><li><a href="/wiki/Signedness" title="Signedness">signedness</a></li></ul></li> <li><a href="/wiki/Interval_arithmetic#Implementations" title="Interval arithmetic">Interval</a></li> <li><a href="/wiki/Rational_data_type" title="Rational data type">Rational</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Pointer_(computer_programming)" title="Pointer (computer programming)">Pointer</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Memory_address" title="Memory address">Address</a> <ul><li><a href="/wiki/Physical_address" title="Physical address">physical</a></li> <li><a href="/wiki/Virtual_address_space" title="Virtual address space">virtual</a></li></ul></li> <li><a href="/wiki/Reference_(computer_science)" title="Reference (computer science)">Reference</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Plain_text" title="Plain text">Text</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Character_(computing)" title="Character (computing)">Character</a></li> <li><a href="/wiki/String_(computer_science)" title="String (computer science)">String</a> <ul><li><a href="/wiki/Null-terminated_string" title="Null-terminated string">null-terminated</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Composite_data_type" title="Composite data type">Composite</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Algebraic_data_type" title="Algebraic data type">Algebraic data type</a> <ul><li><a href="/wiki/Generalized_algebraic_data_type" title="Generalized algebraic data type">generalized</a></li></ul></li> <li><a href="/wiki/Array_data_type" class="mw-redirect" title="Array data type">Array</a></li> <li><a href="/wiki/Associative_array" title="Associative array">Associative array</a></li> <li><a href="/wiki/Class_(computer_programming)" title="Class (computer programming)">Class</a></li> <li><a href="/wiki/Dependent_type" title="Dependent type">Dependent</a></li> <li><a href="/wiki/Intuitionistic_type_theory#Equality_type" title="Intuitionistic type theory">Equality</a></li> <li><a href="/wiki/Inductive_type" title="Inductive type">Inductive</a></li> <li><a href="/wiki/Intersection_type" title="Intersection type">Intersection</a></li> <li><a href="/wiki/List_(abstract_data_type)" title="List (abstract data type)">List</a></li> <li><a href="/wiki/Object_(computer_science)" title="Object (computer science)">Object</a> <ul><li><a href="/wiki/Metaobject" title="Metaobject">metaobject</a></li></ul></li> <li><a href="/wiki/Option_type" title="Option type">Option type</a></li> <li><a href="/wiki/Product_type" title="Product type">Product</a></li> <li><a href="/wiki/Record_(computer_science)" title="Record (computer science)">Record or Struct</a></li> <li><a href="/wiki/Refinement_type" title="Refinement type">Refinement</a></li> <li><a class="mw-selflink selflink">Set</a></li> <li><a href="/wiki/Union_type" title="Union type">Union</a> <ul><li><a href="/wiki/Tagged_union" title="Tagged union">tagged</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Boolean_data_type" title="Boolean data type">Boolean</a></li> <li><a href="/wiki/Bottom_type" title="Bottom type">Bottom type</a></li> <li><a href="/wiki/Container_(abstract_data_type)" title="Container (abstract data type)">Collection</a></li> <li><a href="/wiki/Enumerated_type" title="Enumerated type">Enumerated type</a></li> <li><a href="/wiki/Exception_handling" title="Exception handling">Exception</a></li> <li><a href="/wiki/Function_type" title="Function type">Function type</a></li> <li><a href="/wiki/Opaque_data_type" title="Opaque data type">Opaque data type</a></li> <li><a href="/wiki/Recursive_data_type" title="Recursive data type">Recursive data type</a></li> <li><a href="/wiki/Semaphore_(programming)" title="Semaphore (programming)">Semaphore</a></li> <li><a href="/wiki/Stream_(computing)" title="Stream (computing)">Stream</a></li> <li><a href="/wiki/Strongly_typed_identifier" title="Strongly typed identifier">Strongly typed identifier</a></li> <li><a href="/wiki/Top_type" title="Top type">Top type</a></li> <li><a href="/wiki/Type_class" title="Type class">Type class</a></li> <li><a href="/wiki/Empty_type" title="Empty type">Empty type</a></li> <li><a href="/wiki/Unit_type" title="Unit type">Unit type</a></li> <li><a href="/wiki/Void_type" title="Void type">Void</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related<br />topics</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Abstract_data_type" title="Abstract data type">Abstract data type</a></li> <li><a href="/wiki/Boxing_(computer_science)" class="mw-redirect" title="Boxing (computer science)">Boxing</a></li> <li><a href="/wiki/Data_structure" title="Data structure">Data structure</a></li> <li><a href="/wiki/Generic_programming" title="Generic programming">Generic</a></li> <li><a href="/wiki/Kind_(type_theory)" title="Kind (type theory)">Kind</a> <ul><li><a href="/wiki/Metaclass" title="Metaclass">metaclass</a></li></ul></li> <li><a href="/wiki/Parametric_polymorphism" title="Parametric polymorphism">Parametric polymorphism</a></li> <li><a href="/wiki/Primitive_data_type" title="Primitive data type">Primitive data type</a></li> <li><a href="/wiki/Interface_(object-oriented_programming)" title="Interface (object-oriented programming)">Interface</a></li> <li><a href="/wiki/Subtyping" title="Subtyping">Subtyping</a></li> <li><a href="/wiki/Type_constructor" title="Type constructor">Type constructor</a></li> <li><a href="/wiki/Type_conversion" title="Type conversion">Type conversion</a></li> <li><a href="/wiki/Type_system" title="Type system">Type system</a></li> <li><a href="/wiki/Type_theory" title="Type theory">Type theory</a></li> <li><a href="/wiki/Variable_(computer_science)" title="Variable (computer science)">Variable</a></li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox" aria-labelledby="Data_structures216" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Data_structures" title="Template:Data structures"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Data_structures" title="Template talk:Data structures"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Data_structures" title="Special:EditPage/Template:Data structures"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Data_structures216" style="font-size:114%;margin:0 4em"><a href="/wiki/Data_structure" title="Data structure">Data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</a></li> <li><a href="/wiki/Container_(abstract_data_type)" title="Container (abstract data type)">Container</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Abstract_data_type" title="Abstract data type">Abstract</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Associative_array" title="Associative array">Associative array</a> <ul><li><a href="/wiki/Multimap" title="Multimap">Multimap</a></li> <li><a href="/wiki/Retrieval_Data_Structure" title="Retrieval Data Structure">Retrieval Data Structure</a></li></ul></li> <li><a href="/wiki/List_(abstract_data_type)" title="List (abstract data type)">List</a></li> <li><a href="/wiki/Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li> <li><a href="/wiki/Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a> <ul><li><a href="/wiki/Double-ended_queue" title="Double-ended queue">Double-ended queue</a></li></ul></li> <li><a href="/wiki/Priority_queue" title="Priority queue">Priority queue</a> <ul><li><a href="/wiki/Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a></li></ul></li> <li><a class="mw-selflink selflink">Set</a> <ul><li><a class="mw-selflink-fragment" href="#Multiset">Multiset</a></li> <li><a href="/wiki/Disjoint-set_data_structure" title="Disjoint-set data structure">Disjoint-set</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Array_(data_structure)" title="Array (data structure)">Arrays</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bit_array" title="Bit array">Bit array</a></li> <li><a href="/wiki/Circular_buffer" title="Circular buffer">Circular buffer</a></li> <li><a href="/wiki/Dynamic_array" title="Dynamic array">Dynamic array</a></li> <li><a href="/wiki/Hash_table" title="Hash table">Hash table</a></li> <li><a href="/wiki/Hashed_array_tree" title="Hashed array tree">Hashed array tree</a></li> <li><a href="/wiki/Sparse_matrix" title="Sparse matrix">Sparse matrix</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Linked_data_structure" title="Linked data structure">Linked</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Association_list" title="Association list">Association list</a></li> <li><a href="/wiki/Linked_list" title="Linked list">Linked list</a></li> <li><a href="/wiki/Skip_list" title="Skip list">Skip list</a></li> <li><a href="/wiki/Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li> <li><a href="/wiki/XOR_linked_list" title="XOR linked list">XOR linked list</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Trees</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/B-tree" title="B-tree">B-tree</a></li> <li><a href="/wiki/Binary_search_tree" title="Binary search tree">Binary search tree</a> <ul><li><a href="/wiki/AA_tree" title="AA tree">AA tree</a></li> <li><a href="/wiki/AVL_tree" title="AVL tree">AVL tree</a></li> <li><a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li> <li><a href="/wiki/Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</a></li> <li><a href="/wiki/Splay_tree" title="Splay tree">Splay tree</a></li></ul></li> <li><a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heap</a> <ul><li><a href="/wiki/Binary_heap" title="Binary heap">Binary heap</a></li> <li><a href="/wiki/Binomial_heap" title="Binomial heap">Binomial heap</a></li> <li><a href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a></li></ul></li> <li><a href="/wiki/R-tree" title="R-tree">R-tree</a> <ul><li><a href="/wiki/R*_tree" class="mw-redirect" title="R* tree">R* tree</a></li> <li><a href="/wiki/R%2B_tree" title="R+ tree">R+ tree</a></li> <li><a href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a></li></ul></li> <li><a href="/wiki/Trie" title="Trie">Trie</a> <ul><li><a href="/wiki/Hash_tree_(persistent_data_structure)" title="Hash tree (persistent data structure)">Hash tree</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a></li> <li><a href="/wiki/Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a></li> <li><a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <ul><li><a href="/wiki/List_of_data_structures" title="List of data structures">List of data structures</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Set_(abstract_data_type)&oldid=1223692548">https://en.wikipedia.org/w/index.php?title=Set_(abstract_data_type)&oldid=1223692548</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Data_types" title="Category:Data types">Data types</a></li><li><a href="/wiki/Category:Composite_data_types" title="Category:Composite data types">Composite data types</a></li><li><a href="/wiki/Category:Abstract_data_types" title="Category:Abstract data types">Abstract data types</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_October_2011" title="Category:Articles needing additional references from October 2011">Articles needing additional references from October 2011</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li><li><a href="/wiki/Category:Wikipedia_articles_needing_clarification_from_November_2020" title="Category:Wikipedia articles needing clarification from November 2020">Wikipedia articles needing clarification from November 2020</a></li><li><a href="/wiki/Category:Articles_with_example_Python_(programming_language)_code" title="Category:Articles with example Python (programming language) code">Articles with example Python (programming language) code</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 13 May 2024, at 19:07<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Set_(abstract_data_type)&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" lang="en" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Set (abstract data type)</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>23 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-7c5dd74596-sqc26","wgBackendResponseTime":141,"wgPageParseReport":{"limitreport":{"cputime":"0.332","walltime":"0.484","ppvisitednodes":{"value":1287,"limit":1000000},"postexpandincludesize":{"value":43973,"limit":2097152},"templateargumentsize":{"value":1664,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":8,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":34901,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 352.957 1 -total"," 25.69% 90.678 2 Template:Reflist"," 21.27% 75.063 2 Template:Navbox"," 20.66% 72.906 1 Template:Data_types"," 19.95% 70.414 1 Template:Citation"," 19.80% 69.869 1 Template:More_citations_needed"," 18.50% 65.284 1 Template:Ambox"," 16.49% 58.192 1 Template:Short_description"," 10.10% 35.662 2 Template:Pagetype"," 5.55% 19.602 1 Template:Main"]},"scribunto":{"limitreport-timeusage":{"value":"0.190","limit":"10.000"},"limitreport-memusage":{"value":4606068,"limit":52428800}},"cachereport":{"origin":"mw-api-int.codfw.main-6c4b4c4bd6-xb4x9","timestamp":"20250210050419","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Set (abstract data type)","url":"https:\/\/en.wikipedia.org\/wiki\/Set_(abstract_data_type)","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1514741","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1514741","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-03-25T01:59:33Z","dateModified":"2024-05-13T19:07:52Z","headline":"abstract data type in computer science"}</script> </body> </html>