Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

bit_vector Class Reference

#include <stl_bvector.h>

Collaboration diagram for bit_vector:

Collaboration graph
[legend]
List of all members.

Public Types

typedef bool value_type
typedef size_t size_type
typedef ptrdiff_t difference_type
typedef __bit_reference reference
typedef bool const_reference
typedef __bit_reference * pointer
typedef const bool * const_pointer
typedef __bit_iterator iterator
typedef __bit_const_iterator const_iterator
typedef reverse_iterator<
const_iterator, value_type,
const_reference, difference_type > 		const_reverse_iterator
typedef reverse_iterator<
iterator, value_type, reference,
difference_type > 		reverse_iterator

Public Methods

iterator begin ()
const_iterator begin () const
iterator end ()
const_iterator end () const
reverse_iterator rbegin ()
const_reverse_iterator rbegin () const
reverse_iterator rend ()
const_reverse_iterator rend () const
size_type size () const
size_type max_size () const
size_type capacity () const
bool empty () const
reference operator[] (size_type n)
const_reference operator[] (size_type n) const
 __BVECTOR ()
 __BVECTOR (size_type n, bool value)
 __BVECTOR (int n, bool value)
 __BVECTOR (long n, bool value)
 __BVECTOR (size_type n)
 __BVECTOR (const __BVECTOR &x)
 __BVECTOR (const_iterator first, const_iterator last)
 __BVECTOR (const bool *first, const bool *last)
 ~__BVECTOR ()
__BVECTOR & operator= (const __BVECTOR &x)
void reserve (size_type n)
reference front ()
const_reference front () const
reference back ()
const_reference back () const
void push_back (bool x)
void swap (__BVECTOR &x)
iterator insert (iterator position, bool x=bool())
void insert (iterator position, const_iterator first, const_iterator last)
void insert (iterator position, const bool *first, const bool *last)
void insert (iterator position, size_type n, bool x)
void insert (iterator pos, int n, bool x)
void insert (iterator pos, long n, bool x)
void pop_back ()
iterator erase (iterator position)
iterator erase (iterator first, iterator last)
void resize (size_type new_size, bool x=bool())
void clear ()

Protected Methods

unsigned int * bit_alloc (size_type n)
void deallocate ()
void initialize (size_type n)
void insert_aux (iterator position, bool x)

Protected Attributes

iterator start
iterator finish
unsigned int * end_of_storage

Private Types

typedef simple_alloc< unsigned
int, alloc > 		data_allocator

Member Typedef Documentation

typedef __bit_const_iterator bit_vector::const_iterator
 

Definition at line 277 of file stl_bvector.h.

typedef const bool* bit_vector::const_pointer
 

Definition at line 274 of file stl_bvector.h.

typedef bool bit_vector::const_reference
 

Definition at line 272 of file stl_bvector.h.

typedef reverse_iterator<const_iterator, value_type, const_reference, difference_type> bit_vector::const_reverse_iterator
 

Definition at line 284 of file stl_bvector.h.

typedef simple_alloc<unsigned int, alloc> bit_vector::data_allocator [private]
 

Definition at line 265 of file stl_bvector.h.

typedef ptrdiff_t bit_vector::difference_type
 

Definition at line 270 of file stl_bvector.h.

typedef __bit_iterator bit_vector::iterator
 

Definition at line 276 of file stl_bvector.h.

typedef __bit_reference* bit_vector::pointer
 

Definition at line 273 of file stl_bvector.h.

typedef __bit_reference bit_vector::reference
 

Definition at line 271 of file stl_bvector.h.

typedef reverse_iterator<iterator, value_type, reference, difference_type> bit_vector::reverse_iterator
 

Definition at line 286 of file stl_bvector.h.

typedef size_t bit_vector::size_type
 

Definition at line 269 of file stl_bvector.h.

typedef bool bit_vector::value_type
 

Definition at line 268 of file stl_bvector.h.

Constructor & Destructor Documentation

bit_vector::~__BVECTOR (    )  [inline]
 

Definition at line 450 of file stl_bvector.h.

References __BVECTOR, and vector::deallocate. 

00450 { deallocate(); }

Member Function Documentation

bit_vector::__BVECTOR (  const bool *    first,
const bool *    last
)  [inline]
 

Definition at line 442 of file stl_bvector.h.

References copy, distance, and vector::size_type. 

00442                                                  {
00443     size_type n = 0;
00444     distance(first, last, n);
00445     initialize(n);
00446     copy(first, last, start);
00447   }

bit_vector::__BVECTOR (  const_iterator    first,
const_iterator    last
)  [inline]
 

Definition at line 436 of file stl_bvector.h.

References copy, distance, and vector::size_type. 

00436                                                        {
00437     size_type n = 0;
00438     distance(first, last, n);
00439     initialize(n);
00440     copy(first, last, start);
00441   }

bit_vector::__BVECTOR (  const __BVECTOR &    x )  [inline]
 

Definition at line 425 of file stl_bvector.h.

References __BVECTOR, and copy. 

00425                                 {
00426     initialize(x.size());
00427     copy(x.begin(), x.end(), start);
00428   }

bit_vector::__BVECTOR (  size_type    n )  [inline, explicit]
 

Definition at line 421 of file stl_bvector.h.

References vector::end_of_storage, fill, __bit_iterator::p, and vector::size_type. 

00421                                   {
00422     initialize(n);
00423     fill(start.p, end_of_storage, 0);
00424   }

bit_vector::__BVECTOR (  long    n,
bool    value
)  [inline]
 

Definition at line 417 of file stl_bvector.h.

References vector::end_of_storage, fill, and __bit_iterator::p. 

00417                                 {
00418     initialize(n);
00419     fill(start.p, end_of_storage, value ? ~0 : 0);
00420   }

bit_vector::__BVECTOR (  int    n,
bool    value
)  [inline]
 

Definition at line 413 of file stl_bvector.h.

References vector::end_of_storage, fill, and __bit_iterator::p. 

00413                                {
00414     initialize(n);
00415     fill(start.p, end_of_storage, value ? ~0 : 0);
00416   }

bit_vector::__BVECTOR (  size_type    n,
bool    value
)  [inline]
 

Definition at line 409 of file stl_bvector.h.

References vector::end_of_storage, fill, __bit_iterator::p, and vector::size_type. 

00409                                      {
00410     initialize(n);
00411     fill(start.p, end_of_storage, value ? ~0 : 0);
00412   }

bit_vector::__BVECTOR (    )  [inline]
 

Definition at line 408 of file stl_bvector.h.

References vector::end_of_storage. 

00408 : start(iterator()), finish(iterator()), end_of_storage(0) {}

const_reference bit_vector::back (    )  const [inline]
 

Definition at line 473 of file stl_bvector.h.

References vector::end. 

00473 { return *(end() - 1); }

reference bit_vector::back (    )  [inline]
 

Definition at line 472 of file stl_bvector.h.

References vector::end. 

00472 { return *(end() - 1); }

const_iterator bit_vector::begin (    )  const [inline]
 

Definition at line 383 of file stl_bvector.h. 

00383 { return start; }

iterator bit_vector::begin (    )  [inline]
 

Definition at line 382 of file stl_bvector.h.

Referenced by operator<, and operator==. 

00382 { return start; }

unsigned int* bit_vector::bit_alloc (  size_type    n )  [inline, protected]
 

Definition at line 293 of file stl_bvector.h.

References __WORD_BIT, and vector::size_type. 

00293                                        {
00294     return data_allocator::allocate((n + __WORD_BIT - 1)/__WORD_BIT);
00295   }

size_type bit_vector::capacity (    )  const [inline]
 

Definition at line 398 of file stl_bvector.h.

References vector::begin, vector::const_iterator, vector::end_of_storage, and vector::size_type. 

00398                              {
00399     return size_type(const_iterator(end_of_storage, 0) - begin());
00400   }

void bit_vector::clear (    )  [inline]
 

Definition at line 584 of file stl_bvector.h.

References vector::begin, vector::end, and vector::erase. 

00584 { erase(begin(), end()); }

void bit_vector::deallocate (    )  [inline, protected]
 

Definition at line 296 of file stl_bvector.h.

References vector::end_of_storage, and __bit_iterator::p. 

00296                     {
00297     if (start.p)
00298       data_allocator::deallocate(start.p, end_of_storage - start.p);
00299   }

bool bit_vector::empty (    )  const [inline]
 

Definition at line 401 of file stl_bvector.h.

References vector::begin, and vector::end. 

00401 { return begin() == end(); }

const_iterator bit_vector::end (    )  const [inline]
 

Definition at line 385 of file stl_bvector.h. 

00385 { return finish; }

iterator bit_vector::end (    )  [inline]
 

Definition at line 384 of file stl_bvector.h.

Referenced by operator<, and operator==. 

00384 { return finish; }

iterator bit_vector::erase (  iterator    first,
iterator    last
)  [inline]
 

Definition at line 574 of file stl_bvector.h.

References copy, and vector::end. 

00574                                                 {
00575     finish = copy(last, end(), first);
00576     return first;
00577   }

iterator bit_vector::erase (  iterator    position )  [inline]
 

Definition at line 568 of file stl_bvector.h.

References copy, and vector::end. 

00568                                     {
00569     if (position + 1 != end())
00570       copy(position + 1, end(), position);
00571     --finish;
00572     return position;
00573   }

const_reference bit_vector::front (    )  const [inline]
 

Definition at line 471 of file stl_bvector.h.

References vector::begin. 

00471 { return *begin(); }

reference bit_vector::front (    )  [inline]
 

Definition at line 470 of file stl_bvector.h.

References vector::begin. 

00470 { return *begin(); }

void bit_vector::initialize (  size_type    n )  [inline, protected]
 

Definition at line 300 of file stl_bvector.h.

References __WORD_BIT, vector::difference_type, vector::end_of_storage, vector::iterator, and vector::size_type. 

00300                                {
00301     unsigned int* q = bit_alloc(n);
00302     end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
00303     start = iterator(q, 0);
00304     finish = start + difference_type(n);
00305   }

void bit_vector::insert (  iterator    pos,
long    n,
bool    x
)  [inline]
 

Definition at line 565 of file stl_bvector.h.

References vector::insert, and vector::size_type. 

00565 { insert(pos, (size_type)n, x); }

void bit_vector::insert (  iterator    pos,
int    n,
bool    x
)  [inline]
 

Definition at line 564 of file stl_bvector.h.

References vector::insert, and vector::size_type. 

00564 { insert(pos, (size_type)n, x); }

void bit_vector::insert (  iterator    position,
size_type    n,
bool    x
)  [inline]
 

Definition at line 545 of file stl_bvector.h.

References __WORD_BIT, vector::begin, vector::capacity, copy, copy_backward, vector::deallocate, vector::difference_type, vector::end, vector::end_of_storage, fill, fill_n, vector::iterator, max, vector::size, and vector::size_type. 

00545                                                       {
00546     if (n == 0) return;
00547     if (capacity() - size() >= n) {
00548       copy_backward(position, end(), finish + difference_type(n));
00549       fill(position, position + difference_type(n), x);
00550       finish += difference_type(n);
00551     }
00552     else {
00553       size_type len = size() + max(size(), n);
00554       unsigned int* q = bit_alloc(len);
00555       iterator i = copy(begin(), position, iterator(q, 0));
00556       fill_n(i, n, x);
00557       finish = copy(position, end(), i + difference_type(n));
00558       deallocate();
00559       end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
00560       start = iterator(q, 0);
00561     }
00562   }

void bit_vector::insert (  iterator    position,
const bool *    first,
const bool *    last
)  [inline]
 

Definition at line 523 of file stl_bvector.h.

References __WORD_BIT, vector::begin, vector::capacity, copy, copy_backward, vector::deallocate, distance, vector::end, vector::end_of_storage, vector::iterator, max, vector::size, and vector::size_type. 

00523                                                                       {
00524     if (first == last) return;
00525     size_type n = 0;
00526     distance(first, last, n);
00527     if (capacity() - size() >= n) {
00528       copy_backward(position, end(), finish + n);
00529       copy(first, last, position);
00530       finish += n;
00531     }
00532     else {
00533       size_type len = size() + max(size(), n);
00534       unsigned int* q = bit_alloc(len);
00535       iterator i = copy(begin(), position, iterator(q, 0));
00536       i = copy(first, last, i);
00537       finish = copy(position, end(), i);
00538       deallocate();
00539       end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
00540       start = iterator(q, 0);
00541     }
00542   }

void bit_vector::insert (  iterator    position,
const_iterator    first,
const_iterator    last
)  [inline]
 

Definition at line 501 of file stl_bvector.h.

References __WORD_BIT, vector::begin, vector::capacity, copy, copy_backward, vector::deallocate, distance, vector::end, vector::end_of_storage, vector::iterator, max, vector::size, and vector::size_type. 

00502                                    {
00503     if (first == last) return;
00504     size_type n = 0;
00505     distance(first, last, n);
00506     if (capacity() - size() >= n) {
00507       copy_backward(position, end(), finish + n);
00508       copy(first, last, position);
00509       finish += n;
00510     }
00511     else {
00512       size_type len = size() + max(size(), n);
00513       unsigned int* q = bit_alloc(len);
00514       iterator i = copy(begin(), position, iterator(q, 0));
00515       i = copy(first, last, i);
00516       finish = copy(position, end(), i);
00517       deallocate();
00518       end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
00519       start = iterator(q, 0);
00520     }
00521   }

iterator bit_vector::insert (  iterator    position,
bool    x = bool()
)  [inline]
 

Definition at line 485 of file stl_bvector.h.

References vector::begin, vector::difference_type, vector::end, vector::end_of_storage, vector::insert_aux, and __bit_iterator::p. 

00485                                                       {
00486     difference_type n = position - begin();
00487     if (finish.p != end_of_storage && position == end())
00488       *finish++ = x;
00489     else
00490       insert_aux(position, x);
00491     return begin() + n;
00492   }

void bit_vector::insert_aux (  iterator    position,
bool    x
)  [inline, protected]
 

Definition at line 306 of file stl_bvector.h.

References __WORD_BIT, vector::begin, copy, copy_backward, vector::deallocate, vector::end, vector::end_of_storage, vector::iterator, __bit_iterator::p, vector::size, and vector::size_type. 

00306                                              {
00307     if (finish.p != end_of_storage) {
00308       copy_backward(position, finish, finish + 1);
00309       *position = x;
00310       ++finish;
00311     }
00312     else {
00313       size_type len = size() ? 2 * size() : __WORD_BIT;
00314       unsigned int* q = bit_alloc(len);
00315       iterator i = copy(begin(), position, iterator(q, 0));
00316       *i++ = x;
00317       finish = copy(position, end(), i);
00318       deallocate();
00319       end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
00320       start = iterator(q, 0);
00321     }
00322   }

size_type bit_vector::max_size (    )  const [inline]
 

Definition at line 397 of file stl_bvector.h.

References vector::size_type. 

00397 { return size_type(-1); }

__BVECTOR& bit_vector::operator= (  const __BVECTOR &    x )  [inline]
 

Definition at line 451 of file stl_bvector.h.

References __BVECTOR, vector::begin, vector::capacity, copy, vector::deallocate, and vector::difference_type. 

00451                                            {
00452     if (&x == this) return *this;
00453     if (x.size() > capacity()) {
00454       deallocate();
00455       initialize(x.size());
00456     }
00457     copy(x.begin(), x.end(), begin());
00458     finish = begin() + difference_type(x.size());
00459     return *this;
00460   }

const_reference bit_vector::operator[] (  size_type    n )  const [inline]
 

Definition at line 405 of file stl_bvector.h.

References vector::begin, vector::difference_type, and vector::size_type. 

00405                                                 {
00406     return *(begin() + difference_type(n));
00407   }

reference bit_vector::operator[] (  size_type    n )  [inline]
 

Definition at line 402 of file stl_bvector.h.

References vector::begin, vector::difference_type, and vector::size_type. 

00402                                     {
00403     return *(begin() + difference_type(n));
00404   }

void bit_vector::pop_back (    )  [inline]
 

Definition at line 567 of file stl_bvector.h. 

00567 { --finish; }

void bit_vector::push_back (  bool    x )  [inline]
 

Definition at line 474 of file stl_bvector.h.

References vector::end, vector::end_of_storage, vector::insert_aux, and __bit_iterator::p. 

00474                          {
00475     if (finish.p != end_of_storage)
00476       *finish++ = x;
00477     else
00478       insert_aux(end(), x);
00479   }

const_reverse_iterator bit_vector::rbegin (    )  const [inline]
 

Definition at line 388 of file stl_bvector.h.

References vector::const_reverse_iterator, and vector::end. 

00388                                         { 
00389     return const_reverse_iterator(end()); 
00390   }

reverse_iterator bit_vector::rbegin (    )  [inline]
 

Definition at line 387 of file stl_bvector.h.

References vector::end, and vector::reverse_iterator. 

00387 { return reverse_iterator(end()); }

const_reverse_iterator bit_vector::rend (    )  const [inline]
 

Definition at line 392 of file stl_bvector.h.

References vector::begin, and vector::const_reverse_iterator. 

00392                                       { 
00393     return const_reverse_iterator(begin()); 
00394   }

reverse_iterator bit_vector::rend (    )  [inline]
 

Definition at line 391 of file stl_bvector.h.

References vector::begin, and vector::reverse_iterator. 

00391 { return reverse_iterator(begin()); }

void bit_vector::reserve (  size_type    n )  [inline]
 

Definition at line 461 of file stl_bvector.h.

References __WORD_BIT, vector::begin, vector::capacity, copy, vector::deallocate, vector::end, vector::end_of_storage, vector::iterator, and vector::size_type. 

00461                             {
00462     if (capacity() < n) {
00463       unsigned int* q = bit_alloc(n);
00464       finish = copy(begin(), end(), iterator(q, 0));
00465       deallocate();
00466       start = iterator(q, 0);
00467       end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
00468     }
00469   }

void bit_vector::resize (  size_type    new_size,
bool    x = bool()
)  [inline]
 

Definition at line 578 of file stl_bvector.h.

References vector::begin, vector::difference_type, vector::end, vector::erase, vector::insert, vector::size, and vector::size_type. 

00578                                                    {
00579     if (new_size < size()) 
00580       erase(begin() + difference_type(new_size), end());
00581     else
00582       insert(end(), new_size - size(), x);
00583   }

size_type bit_vector::size (    )  const [inline]
 

Definition at line 396 of file stl_bvector.h.

References vector::begin, vector::end, and vector::size_type.

Referenced by operator==. 

00396 { return size_type(end() - begin()); }

void bit_vector::swap (  __BVECTOR &    x )  [inline]
 

Definition at line 480 of file stl_bvector.h.

References __BVECTOR, vector::end_of_storage, and swap. 

00480                           {
00481     __STD::swap(start, x.start);
00482     __STD::swap(finish, x.finish);
00483     __STD::swap(end_of_storage, x.end_of_storage);
00484   }

Member Data Documentation

unsigned int* bit_vector::end_of_storage [protected]
 

Definition at line 292 of file stl_bvector.h.

iterator bit_vector::finish [protected]
 

Definition at line 291 of file stl_bvector.h.

iterator bit_vector::start [protected]
 

Definition at line 290 of file stl_bvector.h.

The documentation for this class was generated from the following file:
logo OpenMask

Documentation generated on Thu May 2 15:03:24 2002

Generated with doxygen 1.2.12 by Dimitri van Heesch ,   1997-2001