DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK
 
No More Array Errors (Part II) - Array_alg(3C++)

Array_set membership

The Array_set operation contains() tests whether an Array_set contains an element with a given value. If such an element exists, contains() returns a pointer to it; otherwise, it returns zero. We can implement contains() easily using the Array Algorithm bin_search(), described in bin_search(3C++):

        const T* contains(const T& t)const{
           check();
           return bin_search(t,&b[0],&b[n]);
       }

bin_search() performs a binary search on a sorted array. Unlike bin_loc(), which does a binary search to find where a given value belongs if it is not present, bin_search() searches for the element itself and returns its location if the element is found and zero otherwise. Note that because contains() does not modify any of the representation variables, we only need to check the invariant on entry.


Next topic: Array_set removal
Previous topic: Array_set insertion

© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 27 April 2004