CGAL::In_place_list<T,bool>
Definition
An object of the class In_place_list<T,bool>
represents a sequence of items of type T that supports
bidirectional iterators and allows constant time insert and erase
operations anywhere within the sequence. The functionality is
similar to the list<T> in the STL.
The In_place_list<T,bool> manages the items in place, i.e., inserted
items are not copied. Two pointers of type T* are expected
to be reserved in T for the list management. The base class
In_place_list_base<T> can be used to obtain such pointers.
The In_place_list<T,bool> does not copy element items during
insertion (unless otherwise stated for a function). On removal of an
item or destruction of the list the items are not deleted by
default. The second template parameter bool is set to
false in this case. If the In_place_list<T,bool> should
take the responsibility for the stored objects the bool
parameter could be set to true, in which case the list
will delete removed items and will delete all remaining items on
destruction. In any case, the destroy() member function
deletes all items. Note that these two possible versions of
In_place_list<T,bool> are not assignable to each other to avoid
confusions between the different storage responsibilities.
#include <CGAL/In_place_list.h>
Parameters
The full class name is In_place_list<T, bool managed = false, class Alloc = CGAL_ALLOCATOR(T)>.
The parameter T is supposed to have a default constructor,
a copy constructor and an assignment operator. The copy constructor
and the assignment may copy the pointers in T for the list
management, but they do not have to. The equality test and the
relational order require the operators == and <
for T respectively. These operators must not compare the pointers
in T.
Types
|
In_place_list<T,bool>::iterator
|
|
In_place_list<T,bool>::const_iterator
|
|
|
In_place_list<T,bool>::value_type
|
|
In_place_list<T,bool>::reference
|
|
In_place_list<T,bool>::const_reference
|
|
In_place_list<T,bool>::size_type
|
|
In_place_list<T,bool>::difference_type
|
|
|
In_place_list<T,bool>::reverse_iterator
|
|
In_place_list<T,bool>::const_reverse_iterator
|
|
|
In_place_list<T,bool>::allocator_type
|
Creation
|
In_place_list<T,bool> l;
|
|
introduces an empty list.
|
|
|
In_place_list<T,bool> l ( list<T> l1);
|
|
copy constructor.
Each item in l1 is copied.
|
|
|
In_place_list<T,bool> l ( size_type n, T t = T());
|
|
introduces a list with n items, all initialized with copies
of t.
|
|
|
template <class InputIterator>
|
|
In_place_list<T,bool> l ( InputIterator first, InputIterator last);
|
|
a list with copies from
the range [first,last).
|
|
|
In_place_list<T,bool> l ( const T* first, const T* last);
|
|
non-member-template version.
|
|
In_place_list<T,bool> &
|
l =
l1
|
assignment. Each item in l1
is copied. Each item in l is deleted if the bool
parameter is true.
|
|
|
void
|
l.swap ( l1)
|
swaps the
contents of l with l1.
|
|
|
void
|
l.destroy ()
|
all items in l are deleted
regardless of the bool parameter.
|
Comparison Operations
|
bool
|
l ==
l1
|
test for equality: Two lists are equal, iff they have the
same size and if their corresponding elements are equal.
|
|
|
bool
|
l <
l1
|
compares in lexicographical order.
|
Access Member Functions
|
iterator
|
l.begin ()
|
returns a mutable iterator referring to the first
element in l.
|
|
const_iterator
|
l.begin () const
|
returns a constant
iterator referring to the first element in l.
|
|
iterator
|
l.end ()
|
returns a mutable iterator which
is the past-end-value of l.
|
|
const_iterator
|
l.end () const
|
returns a constant
iterator which is the past-end-value of l.
|
|
|
bool
|
l.empty ()
|
returns true if l is
empty.
|
|
size_type
|
l.size ()
|
returns the number of
items in list l.
|
|
size_type
|
l.max_size ()
|
returns the maximum
possible size of the list l.
|
|
|
T&
|
l.front ()
|
returns the first item in list l.
|
|
T&
|
l.back ()
|
returns the last item in list l.
|
|
|
allocator_type
|
l.get_allocator ()
|
returns the allocator.
|
Insertion
|
void
|
l.push_front ( T&)
|
inserts an item in front of
list l.
|
|
void
|
l.push_back ( T&)
|
inserts an item at the back
of list l.
|
|
|
iterator
|
l.insert ( iterator pos, T& t)
|
|
iterator
|
l.insert ( T* pos, T& t)
|
inserts t
in front of pos. The return value points to the
inserted item.
|
|
|
void
|
l.insert ( iterator pos, size_type n, T t = T())
|
|
void
|
l.insert ( T* pos, size_type n, T t = T())
|
| |
inserts n copies of t in front of
pos.
|
|
|
template <class InputIterator>
|
|
void
|
l.insert ( iterator pos, InputIterator first, InputIterator last)
|
|
|
template <class InputIterator>
|
|
void
|
l.insert ( T* pos, InputIterator first, InputIterator last)
|
| |
inserts the range
[first, last) in front of iterator pos.
|
As long as member templates are not supported, member functions
using T* instead of the general InputIterator
are provided.
Removal
|
void
|
l.pop_front ()
|
removes the first item from
list l.
|
|
void
|
l.pop_back ()
|
removes the last item from
list l.
|
|
void
|
l.erase ( iterator pos)
|
removes the item from
list l, where pos refers to.
|
|
void
|
l.erase ( T* pos)
|
removes the item from
list l, where pos refers to.
|
|
|
void
|
l.erase ( iterator first, iterator last)
|
|
void
|
l.erase ( T* first, T* last)
|
removes the items
in the range [first, last) from l.
|
Special List Operations
|
void
|
l.splice ( iterator pos, & x)
|
|
void
|
l.splice ( T* pos, & x)
|
inserts the list x before position pos and x
becomes empty. It takes constant time.
|
|
|
void
|
l.splice ( iterator pos, & x, iterator i)
|
|
void
|
l.splice ( T* pos, & x, T* i)
|
inserts an element pointed to by i from list x before
position pos and removes the element from x. It takes
constant time. i is a valid dereferenceable iterator of x.
The result is unchanged if pos == i or pos == ++i.
|
|
|
void
|
l.splice ( iterator pos, & x, iterator first, iterator last)
|
|
void
|
l.splice ( T* pos, & x, T* first, T* last)
|
| |
inserts elements in the range [first, last) before position pos and removes the elements
from x. It takes constant time if &x == &l;
otherwise, it takes linear time. [first, last) is a
valid range in x. | Precondition: | pos is not in the range
[first, last). |
|
|
|
void
|
l.remove ( T value)
|
erases all elements e in
the list l for which e == value. It is stable.
| Precondition: | a suitable operator== for the type T. |
|
|
|
void
|
l.unique ()
|
erases all but the first element from
every consecutive group of equal elements in the list l.
| Precondition: | a suitable operator== for the type T. |
|
|
|
void
|
l.merge ( & x)
|
merges the list x
into the list l and x becomes empty. It is stable.
| Precondition: | Both lists are increasingly sorted. A suitable
operator< for the type T. |
|
|
|
void
|
l.reverse ()
|
reverses the order of the elements in
l in linear time.
|
|
|
void
|
l.sort ()
|
sorts the list l according to the
operator< in time O(n log n) where n = size(). It is stable. | Precondition: | a suitable operator<
for the type T. |
|
Example
File: examples/STL_Extension/in_place_list_prog.cpp
#include <CGAL/basic.h>
#include <cassert>
#include <algorithm>
#include <CGAL/In_place_list.h>
using CGAL::In_place_list_base;
struct item : public In_place_list_base<item> {
int key;
item() {}
item( const item& i) : In_place_list_base<item>(i), key(i.key) {}
item( int i) : key(i) {}
bool operator== (const item& i) const { return key == i.key;}
bool operator!= (const item& i) const { return ! (*this == i);}
bool operator== (int i) const { return key == i;}
bool operator!= (int i) const { return ! (*this == i);}
bool operator< (const item& i) const { return key < i.key;}
};
int main() {
typedef CGAL::In_place_list<item,true> List;
List l;
item* p = new item(1);
l.push_back(*p);
l.push_back(*new item(2));
l.push_front(*new item(3));
l.push_front(*new item(4));
l.push_front(*new item(2));
List::iterator i = l.begin();
++i;
l.insert(i, *new item(5));
l.insert(p, *new item(5));
int a[7] = {2,5,4,3,5,1,2};
bool ok = std::equal(l.begin(), l.end(), a);
assert(ok);
l.sort();
l.unique();
assert(l.size() == 5);
int b[5] = {1,2,3,4,5};
ok = std::equal(l.begin(), l.end(), b);
assert(ok);
return 0;
}
