Sunday, July 8, 2012

set


set

<set>
Set
Sets are a kind of associative container that stores unique elements, and in which the elements themselves are the keys. Associative containers are containers especially designed to be efficient accessing its elements by their key (unlike sequence containers, which are more efficient accessing elements by their relative or absolute position).  Internally, the elements in a set are always sorted from lower to higher following a specific strict weak ordering criterion set on container construction.Sets are typically implemented as binary search trees. Therefore, the main characteristics of set as an associative container are:
  • Unique element values: no two elements in the set can compare equal to each other. For a similar associative container allowing for multiple equivalent elements, see multiset.
  • The element value is the key itself. For a similar associative container where elements are accessed using a key, but map to a value different than this key, see map.
  • Elements follow a strict weak ordering at all times. Unordered associative arrays, like unordered_set, are available in implementations following TR1.
This container class supports bidirectional iterators. In their implementation in the C++ Standard Template Library, set containers take three template parameters:
1
2
template < class Key, class Compare = less<Key>,
           class Allocator = allocator<Key> > class set;
Where the template parameters have the following meanings:
  • Key: Key type: type of the elements contained in the container. Each elements in a set is also its key.
  • Compare: Comparison class: A class that takes two arguments of the same type as the container elements and returns a bool. The expression comp(a,b), where comp is an object of this comparison class and a and bare elements of the container, shall return true if a is to be placed at an earlier position than b in a strict weak ordering operation. This can either be a class implementing a function call operator or a pointer to a function (see constructor for an example). This defaults to less<Key>, which returns the same as applying the less-than operator (a<b). The set object uses this expression to determine the position of the elements in the container. All elements in a set container are ordered following this rule at all times.
  • Allocator: Type of the allocator object used to define the storage allocation model. By default, theallocator class template for type Key is used, which defines the simplest memory allocation model and is value-independent.
Construct set
Constructs a set container object, initializing its contents depending on the constructor version used:

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// constructing sets
#include <iostream>
#include <set>
using namespace std;

bool fncomp (int lhs, int rhs) {return lhs<rhs;}

struct classcomp {
  bool operator() (const int& lhs, const int& rhs) const
  {return lhs<rhs;}
};

int main ()
{
  set<int> first;                           // empty set of ints

  int myints[]= {10,20,30,40,50};
  set<int> second (myints,myints+5);        // pointers used as iterators

  set<int> third (second);                  // a copy of second

  set<int> fourth (second.begin(), second.end());  // iterator ctor.

  set<int,classcomp> fifth;                 // class as Compare

  bool(*fn_pt)(int,int) = fncomp;
  set<int,bool(*)(int,int)> sixth (fn_pt);  // function pointer as Compare

  return 0;
}
The code does not produce any output, but demonstrates some ways in which a set container can be constructed.

set::begin

iterator begin ();
const_iterator begin () const;
Return iterator to beginning
Returns an iterator referring to the first element in the set container.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// set::begin/end
#include <iostream>
#include <set>
using namespace std;

int main ()
{
  int myints[] = {75,23,65,42,13};
  set<int> myset (myints,myints+5);

  set<int>::iterator it;

  cout << "myset contains:";
  for ( it=myset.begin() ; it != myset.end(); it++ )
    cout << " " << *it;

  cout << endl;

  return 0;
}
Output:
myset contains: 13 23 42 65 75

set::clear

void clear ( );
Clear content
All the elements in the set container are dropped: their destructors are called, and then they are removed from the container, leaving it with a size of 0.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// set::clear
#include <iostream>
#include <set>
using namespace std;

int main ()
{
  set<int> myset;
  set<int>::iterator it;

  myset.insert (100);
  myset.insert (200);
  myset.insert (300);

  cout << "myset contains:";
  for (it=myset.begin(); it!=myset.end(); ++it)
    cout << " " << *it;

  myset.clear();
  myset.insert (1101);
  myset.insert (2202);

  cout << "\nmyset contains:";
  for (it=myset.begin(); it!=myset.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}
Output:
myset contains: 100 200 300
myset contains: 1101 2202

set::count

size_type count ( const key_type& x ) const;
Count elements with a specific key
Searches the container for an element with a key of x and returns the number of times the element appears in the container. Because set containers do not allow for duplicate keys, this means that the function actually returns 1 if the element is found, and zero otherwise.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// set::count
#include <iostream>
#include <set>
using namespace std;

int main ()
{
  set<int> myset;
  int i;

  // set some initial values:
  for (i=1; i<5; i++) myset.insert(i*3);    // set: 3 6 9 12

  for (i=0;i<10; i++)
  {
    cout << i;
    if (myset.count(i)>0)
      cout << " is an element of myset.\n";
    else 
      cout << " is not an element of myset.\n";
  }

  return 0;
}
Output:
0 is not an element of myset.
1 is not an element of myset.
2 is not an element of myset.
3 is an element of myset.
4 is not an element of myset.
5 is not an element of myset.
6 is an element of myset.
7 is not an element of myset.
8 is not an element of myset.
9 is an element of myset.

set::empty

bool empty ( ) const;
Test whether container is empty
Returns whether the set container is empty, i.e. whether its size is 0.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// set::empty
#include <iostream>
#include <set>
using namespace std;

int main ()
{
  set<int> myset;

  myset.insert(20);
  myset.insert(30);
  myset.insert(10);

  cout << "myset contains:";
  while (!myset.empty())
  {
     cout << " " << *myset.begin();
     myset.erase(myset.begin());
  }
  cout << endl;

  return 0;
}
Output:
myset contains: 10 20 30

set::end

iterator end ();
const_iterator end () const;
Return iterator to end
Returns an iterator referring to the past-the-end element in the set container.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// set::begin/end
#include <iostream>
#include <set>
using namespace std;

int main ()
{
  int myints[] = {75,23,65,42,13};
  set<int> myset (myints,myints+5);

  set<int>::iterator it;

  cout << "myset contains:";
  for ( it=myset.begin() ; it != myset.end(); it++ )
    cout << " " << *it;

  cout << endl;

  return 0;
}
Output:
myset contains: 13 23 42 65 75
at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)