Jump to content

Set (C++): Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
No edit summary
No edit summary
Line 2: Line 2:


==Defination==
==Defination==
A '''set''' is an associative container data structure that is available as part of the [[C++ Standard Library]] (STL), and contains a sorted set of unique objects.<ref name="std">[http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf ISO/IEC 14882:2011 draft specification], p. 806, § 23.4.6</ref>
:A '''set''' is an associative container data structure that is available as part of the [[C++ Standard Library]] (STL), and contains a sorted set of unique objects.<ref name="std">[http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf ISO/IEC 14882:2011 draft specification], p. 806, § 23.4.6</ref>
==Introduction==
==Introduction==
Although the abstract concept of a [[Set (computer science)|set]] does not necessarily imply an ordered collection, the standard library set data structure is always ordered. Its functionality in the STL is provided as a [[template class]], such that any valid C++ object can be used with it.
Although the abstract concept of a [[Set (computer science)|set]] does not necessarily imply an ordered collection, the standard library set data structure is always ordered. Its functionality in the STL is provided as a [[template class]], such that any valid C++ object can be used with it.
Line 9: Line 9:
There are 2 types of sets available in the C++ STL - Sets and Multisets.
There are 2 types of sets available in the C++ STL - Sets and Multisets.
===Set===
===Set===
Every element is unique and insertions of values that are already present in the container are ignored.
::Every element is unique and insertions of values that are already present in the container are ignored.
===Multiset===
===Multiset===
In the multiset container however, multiple occurrences of the same value are allowed.
::In the multiset container however, multiple occurrences of the same value are allowed.
==Characteristic==
==Characteristic==
*Unique element Value :- In a [[Set (computer science)|set]] no two values are same.
*Unique element Value :- In a [[Set (computer science)|set]] no two values are same.

Revision as of 05:41, 3 September 2011

Defination

A set is an associative container data structure that is available as part of the C++ Standard Library (STL), and contains a sorted set of unique objects.[1]

Introduction

Although the abstract concept of a set does not necessarily imply an ordered collection, the standard library set data structure is always ordered. Its functionality in the STL is provided as a template class, such that any valid C++ object can be used with it. Sets are guaranteed to perform operations of insertion, deletion, and testing whether an element is in it, in logarithmic time - O(log n). As such, they are typically implemented using self-balancing binary search trees and support's bidirectional iterator

Types

There are 2 types of sets available in the C++ STL - Sets and Multisets.

Set

Every element is unique and insertions of values that are already present in the container are ignored.

Multiset

In the multiset container however, multiple occurrences of the same value are allowed.

Characteristic

  • Unique element Value :- In a set no two values are same.
  • Element value is itself
  • Elements follow strick weak ordering at all times.

References