stlab.adobe.com Adobe Systems Incorporated

#include <table_index.hpp>

Public Types

typedef boost::indirect_iterator< typename index_type::const_iterator > const_iterator
 
typedef const T * const_pointer
 
typedef const T & const_reference
 
typedef std::reverse_iterator< const_iteratorconst_reverse_iterator
 
typedef index_type::difference_type difference_type
 
typedef std::vector< T * > index_type
 
typedef boost::indirect_iterator< typename index_type::iterator > iterator
 
typedef Compare key_compare
 
typedef Key key_type
 
typedef T * pointer
 
typedef T & reference
 
typedef std::reverse_iterator< iteratorreverse_iterator
 
typedef index_type::size_type size_type
 
typedef Transform transform_type
 
typedef T value_type
 

Public Member Functions

const_reference at (size_type n) const
 
reference at (size_type n)
 
reference back ()
 
const_reference back () const
 
iterator begin ()
 
const_iterator begin () const
 
void clear ()
 
size_type count (const key_type &x) const
 
bool empty () const
 
iterator end ()
 
const_iterator end () const
 
std::pair< iterator, iteratorequal_range (const key_type &x)
 
std::pair< const_iterator, const_iteratorequal_range (const key_type &x) const
 
iterator erase (iterator location)
 
iterator erase (iterator first, iterator last)
 
iterator find (const key_type &x)
 
const_iterator find (const key_type &x) const
 
reference front ()
 
const_reference front () const
 
index_typeindex ()
 
const index_typeindex () const
 
iterator insert (iterator, value_type &)
 
template<class InputIterator >
void insert (iterator position, InputIterator first, InputIterator last)
 
iterator lower_bound (const key_type &x)
 
const_iterator lower_bound (const key_type &x) const
 
size_type max_size () const
 
reference operator[] (const key_type &)
 
const_reference operator[] (const key_type &) const
 
void pop_back ()
 
void push_back (value_type &)
 
reverse_iterator rbegin ()
 
const_reverse_iterator rbegin () const
 
reverse_iterator rend ()
 
const_reverse_iterator rend () const
 
size_type size () const
 
void sort ()
 
template<class TransformPrimitive >
 table_index (TransformPrimitive transform, const key_compare &compare=key_compare())
 
 table_index (const transform_type &, const key_compare &=key_compare())
 
template<typename InputIterator , typename TransformPrimitive >
 table_index (InputIterator first, InputIterator last, TransformPrimitive transform, const key_compare &compare=key_compare())
 
transform_type transform () const
 
void unique ()
 
iterator upper_bound (const key_type &x)
 
const_iterator upper_bound (const key_type &x) const
 

Friends

void swap (table_index &x, table_index &y)
 

Related Functions

(Note that these are not member functions.)

void swap (adobe::table_index &x, adobe::table_index &y)
 

Detailed Description

template<typename Key, typename T, typename Transform = mem_data_t<T, const Key>, typename Compare = std::less<Key>>
class adobe::table_index< Key, T, Transform, Compare >

Terminology:
  • Row : any class or struct type; an element
  • Column : a data or logical member of an element
  • Table : any random access container of elements
  • Transformation Function : given an element returns 1 or more columns. The result is by const reference so columns must be adjacent
  • Key : a value which can be compared against a single member of an element

The table_index does not own the elements it indexes. Therefore the client is required to maintain the elements in the table_index as long as the table_index refers to them.

If the index is not sorted then the result of a lookup by key is undefined.

Todo:
(sparent) note here on why not auto sort.

Definition at line 671 of file table_index.hpp.

Member Typedef Documentation

§ const_iterator

Const iterator used to iterate through a table_index.

Definition at line 690 of file table_index.hpp.

§ const_pointer

Const pointer to T.

Definition at line 687 of file table_index.hpp.

§ const_reference

Const reference to T.

Definition at line 683 of file table_index.hpp.

§ const_reverse_iterator

Const iterator used to iterate backwards through a table_index.

Definition at line 692 of file table_index.hpp.

§ difference_type

A signed integral type.

Definition at line 685 of file table_index.hpp.

§ index_type

Container to store the elements of the table.

Definition at line 675 of file table_index.hpp.

§ iterator

Iterator used to iterate through a table_index.

Definition at line 689 of file table_index.hpp.

§ key_compare

Functor that compares two keys for ordering.

Definition at line 680 of file table_index.hpp.

§ key_type

The table_index's key type, Key.

Definition at line 678 of file table_index.hpp.

§ pointer

Pointer to T.

Definition at line 686 of file table_index.hpp.

§ reference

Reference to T.

Definition at line 682 of file table_index.hpp.

§ reverse_iterator

Iterator used to iterate backwards through a table_index.

Definition at line 691 of file table_index.hpp.

§ size_type

An unsigned integral type.

Definition at line 684 of file table_index.hpp.

§ transform_type

ConvertibleToFunction used to transform an element into a specific key.

Definition at line 676 of file table_index.hpp.

§ value_type

The type of object referenced by the table_index.

Definition at line 679 of file table_index.hpp.

Constructor & Destructor Documentation

§ table_index() [1/3]

table_index ( TransformPrimitive  transform,
const key_compare compare = key_compare() 
)
explicit
Parameters
transformConvertibleToFunction to be converted to the transformation function for this index
comparekey comparison function for this index

Definition at line 695 of file table_index.hpp.

§ table_index() [2/3]

table_index ( const transform_type transform,
const key_compare compare = key_compare() 
)
explicit
Parameters
transformtransformation function for this index
comparekey comparison function for this index

Definition at line 817 of file table_index.hpp.

§ table_index() [3/3]

table_index ( InputIterator  first,
InputIterator  last,
TransformPrimitive  transform,
const key_compare compare = key_compare() 
)

Definition at line 702 of file table_index.hpp.

Member Function Documentation

§ at() [1/2]

table_index< Key, T, Compare, Transform >::const_reference at ( size_type  n) const
Parameters
nindex into the table.
Returns
Element n in the table.

Definition at line 1022 of file table_index.hpp.

§ at() [2/2]

table_index< Key, T, Compare, Transform >::reference at ( size_type  n)
Parameters
nindex into the table.
Returns
Element n in the table.

Definition at line 1013 of file table_index.hpp.

§ back() [1/2]

Returns
The last element in the table.

§ back() [2/2]

Returns
The last element in the table.

§ begin() [1/2]

table_index< Key, T, Compare, Transform >::iterator begin ( )
Returns
An iterator pointing to the beginning of the table_index.

Definition at line 827 of file table_index.hpp.

§ begin() [2/2]

table_index< Key, T, Compare, Transform >::const_iterator begin ( ) const
Returns
A const_iterator pointing to the beginning of the table_index.

Definition at line 836 of file table_index.hpp.

§ clear()

void clear ( )

Erases the entire table_index.

Definition at line 987 of file table_index.hpp.

§ count()

table_index< Key, T, Compare, Transform >::size_type count ( const key_type x) const
Precondition
table must be sorted.
Parameters
xkey value to count within the index
Returns
Count of the elements with key value x.

Definition at line 1087 of file table_index.hpp.

§ empty()

bool empty ( ) const
Returns
true if the table_index's size is 0.

Definition at line 916 of file table_index.hpp.

§ end() [1/2]

table_index< Key, T, Compare, Transform >::iterator end ( )
Returns
An iterator pointing to the end of the table_index.

Definition at line 845 of file table_index.hpp.

§ end() [2/2]

table_index< Key, T, Compare, Transform >::const_iterator end ( ) const
Returns
A const_iterator pointing to the end of the table_index.

Definition at line 854 of file table_index.hpp.

§ equal_range() [1/2]

std::pair< typename table_index< Key, T, Compare, Transform >::iterator, typename table_index< Key, T, Compare, Transform >::iterator > equal_range ( const key_type x)
Precondition
table must be sorted.
Parameters
xkey value to find within the index
Returns
Essentially a combination of the values returned by lower_bound and upper_bound

Definition at line 1137 of file table_index.hpp.

§ equal_range() [2/2]

std::pair< typename table_index< Key, T, Compare, Transform >::const_iterator, typename table_index< Key, T, Compare, Transform >::const_iterator > equal_range ( const key_type x) const
Precondition
table must be sorted.
Parameters
xkey value to find within the index
Returns
Essentially a combination of the values returned by lower_bound and upper_bound

Definition at line 1148 of file table_index.hpp.

§ erase() [1/2]

table_index< Key, T, Compare, Transform >::iterator erase ( iterator  location)
Parameters
positioniterator to the element to be removed from the index
Returns
An iterator pointing to the next element after the one removed from the index

Definition at line 970 of file table_index.hpp.

§ erase() [2/2]

table_index< Key, T, Compare, Transform >::iterator erase ( iterator  first,
iterator  last 
)
Parameters
firstIterator to the first element to be erased from the index
lastIterator to one past the last element to be erased from the index
Returns
An iterator pointing to to the next element after the ones removed from the index

Definition at line 979 of file table_index.hpp.

§ find() [1/2]

table_index< Key, T, Compare, Transform >::iterator find ( const key_type x)
Precondition
table must be sorted.
Parameters
xkey value to find within the index
Returns
Iterator to the element with key value x, or end() if there is none.

Definition at line 1059 of file table_index.hpp.

§ find() [2/2]

table_index< Key, T, Compare, Transform >::const_iterator find ( const key_type x) const
Precondition
table must be sorted.
Parameters
xkey value to find within the index
Returns
Iterator to the element with key value x, or end() if there is none.

Definition at line 1073 of file table_index.hpp.

§ front() [1/2]

Returns
The first element in the table.

§ front() [2/2]

Returns
The first element in the table.

§ index() [1/2]

table_index< Key, T, Compare, Transform >::index_type & index ( )
Returns
All the elements in the index in a std::vector

Definition at line 1158 of file table_index.hpp.

§ index() [2/2]

const table_index< Key, T, Compare, Transform >::index_type & index ( ) const
Returns
All the elements in the index in a std::vector

Definition at line 1167 of file table_index.hpp.

§ insert() [1/2]

table_index< Key, T, Compare, Transform >::iterator insert ( iterator  position,
value_type x 
)
Parameters
positionposition at which the new element is to be inserted
xThe element to insert as the position specified
Returns
An iterator pointing to the new element.
Postcondition
x must exist as long as this table's reference to it exists.

Definition at line 941 of file table_index.hpp.

§ insert() [2/2]

void insert ( iterator  position,
InputIterator  first,
InputIterator  last 
)
Parameters
positionposition at which the new elements are to be inserted
firstIterator to the first new element to be inserted
lastIterator to one past the last new element to be inserted
Postcondition
The elements found in (first, last] must exist as long as this table's references to them exist.

Definition at line 955 of file table_index.hpp.

§ lower_bound() [1/2]

table_index< Key, T, Compare, Transform >::iterator lower_bound ( const key_type x)
Precondition
table must be sorted.
Parameters
xkey value to find within the index
Returns
The first position where the element transformed to x could be inserted without violating the ordering of the table.

Definition at line 1096 of file table_index.hpp.

§ lower_bound() [2/2]

table_index< Key, T, Compare, Transform >::const_iterator lower_bound ( const key_type x) const
Precondition
table must be sorted.
Parameters
xkey value to find within the index
Returns
The first position where the element transformed to x could be inserted without violating the ordering of the table.

Definition at line 1106 of file table_index.hpp.

§ max_size()

table_index< Key, T, Compare, Transform >::size_type max_size ( ) const
Returns
The largest possible size of the table_index.

Definition at line 899 of file table_index.hpp.

§ operator[]() [1/2]

table_index< Key, T, Compare, Transform >::reference operator[] ( const key_type key)
Precondition
table must be sorted.
Parameters
keykey value to find in the table index.
Returns
One or more adjacent values whose keys match key.

Definition at line 1031 of file table_index.hpp.

§ operator[]() [2/2]

table_index< Key, T, Compare, Transform >::const_reference operator[] ( const key_type key) const
Precondition
table must be sorted.
Parameters
keykey value to find in the table index.
Returns
One or more adjacent values whose keys match key.

Definition at line 1045 of file table_index.hpp.

§ pop_back()

void pop_back ( )

Eliminates the last element from the table.

Definition at line 932 of file table_index.hpp.

§ push_back()

void push_back ( value_type x)
Parameters
xThe element to insert at the end of the table
Postcondition
x must exist as long as this table's reference to it exists.

Definition at line 924 of file table_index.hpp.

§ rbegin() [1/2]

table_index< Key, T, Compare, Transform >::reverse_iterator rbegin ( )
Returns
A reverse_iterator pointing to the beginning of the reversed table_index.

Definition at line 863 of file table_index.hpp.

§ rbegin() [2/2]

table_index< Key, T, Compare, Transform >::const_reverse_iterator rbegin ( ) const
Returns
A const_reverse_iterator pointing to the beginning of the reversed table_index.

Definition at line 872 of file table_index.hpp.

§ rend() [1/2]

table_index< Key, T, Compare, Transform >::reverse_iterator rend ( )
Returns
A reverse_iterator pointing to the end of the reversed table_index.

Definition at line 881 of file table_index.hpp.

§ rend() [2/2]

table_index< Key, T, Compare, Transform >::const_reverse_iterator rend ( ) const
Returns
A const_reverse_iterator pointing to the end of the reversed table_index.

Definition at line 890 of file table_index.hpp.

§ size()

table_index< Key, T, Compare, Transform >::size_type size ( ) const
Returns
Returns the size of the table_index.

Definition at line 908 of file table_index.hpp.

§ sort()

void sort ( )

Sorts all the elements in the table based on their transformed values as compared with the key_compare function object.

Definition at line 995 of file table_index.hpp.

§ transform()

transform_type transform ( ) const

Definition at line 777 of file table_index.hpp.

§ unique()

void unique ( )

Reduces the index to a single value per key.

Definition at line 1003 of file table_index.hpp.

§ upper_bound() [1/2]

table_index< Key, T, Compare, Transform >::iterator upper_bound ( const key_type x)
Precondition
table must be sorted.
Parameters
xkey value to find within the index
Returns
The last position where the element transformed to x could be inserted without violating the ordering of the table.

Definition at line 1116 of file table_index.hpp.

§ upper_bound() [2/2]

table_index< Key, T, Compare, Transform >::const_iterator upper_bound ( const key_type x) const
Precondition
table must be sorted.
Parameters
xkey value to find within the index
Returns
The last position where the element transformed to x could be inserted without violating the ordering of the table.

Definition at line 1126 of file table_index.hpp.

Friends And Related Function Documentation

§ swap() [1/2]

void swap ( adobe::table_index< Key, T, Transform, Compare > &  x,
adobe::table_index< Key, T, Transform, Compare > &  y 
)
related

Swaps the contents of two table_indexes.

Parameters
xthe first table_index to swap.
ythe second table_index to swap.

§ swap [2/2]

void swap ( table_index< Key, T, Transform, Compare > &  x,
table_index< Key, T, Transform, Compare > &  y 
)
friend

Definition at line 779 of file table_index.hpp.

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google