3 * \file RandomAccessList.h
4 * This file is part of LyX, the document processor.
5 * Licence details can be found in the file COPYING.
7 * \author Abdelrazak Younes
9 * Full author contact details are available in file CREDITS.
13 #ifndef RANDOM_ACESS_LIST_H
14 #define RANDOM_ACESS_LIST_H
18 #include <boost/utility.hpp>
27 #define USE_OLD_ITERATOR 1
29 /// Random Access List.
31 This templatized class provide a std::vector like interface to a
32 standard std::list underneath. An important property is that it
33 keeps the std::list::iterator interface. A typical use would be:
35 typedef RandomAccessList<some_class> MyContainer;
37 Then you can use MyContainer as if it was a standard
38 std::vector<some_class> for operator[] access and as if it was a
39 standard std::list for iterator access. The main difference with
40 std::vector is that insertion of elements is much less costly. Compared
41 to a standard list alone, there is of course a small overhead because
42 the class always keeps its internal vector of iterator (it_vector_) up
46 class RandomAccessList {
49 typedef std::list<T> Container;
50 typedef typename Container::reference reference;
51 typedef typename Container::const_reference const_reference;
54 typedef typename Container::iterator iterator;
55 // const_iterator (below)
56 typedef typename Container::const_iterator const_iterator;
60 typedef typename Container::size_type size_type;
61 typedef typename Container::difference_type difference_type;
62 typedef typename Container::value_type value_type;
63 typedef typename Container::allocator_type allocator_type;
64 typedef typename Container::pointer pointer;
65 typedef typename Container::const_pointer const_pointer;
67 // const_reverse_iterator
69 typedef std::vector<typename Container::iterator> IterCont;
71 // construct/copy/destroy
76 // RandomAccessList(size_type n T const & value = T())
78 template<class InputIterator>
79 RandomAccessList(InputIterator first, InputIterator last)
86 RandomAccessList(RandomAccessList const & x)
88 assign(x.begin(), x.end());
91 // ~RandomAccessList()
94 RandomAccessList & operator=(RandomAccessList const & x)
96 assign(x.begin(), x.end());
100 template<class InputIterator>
101 void assign(InputIterator first, InputIterator last)
103 container_.assign(first, last);
108 // void assign(size_type n, T const & u);
114 return container_.begin();
117 const_iterator begin() const
119 return container_.begin();
124 return container_.end();
127 const_iterator end() const
129 return container_.end();
132 // reverse_iterator rbegin();
133 // const_reverse_iterator rbegin() const;
134 // reverse_iterator rend();
135 // const_reverse_iterator rend() const;
138 size_type size() const
140 return iterCont_.size();
143 size_type max_size() const
145 return iterCont_.max_size();
148 // void resize(size_type sz, T c = T());
150 size_type capacity() const
152 return iterCont_.capacity();
157 return container_.empty();
160 // void reserve(size_type n);
164 reference operator[](size_type pos)
166 return *iterCont_[pos];
170 const_reference operator[](size_type pos) const
172 return *iterCont_[pos];
175 reference at(size_type pos)
177 return *iterCont_.at(pos);
180 const_reference at(size_type pos) const
182 return *iterCont_.at(pos);
187 return container_.front();
190 const_reference front() const
192 return container_.front();
197 return container_.back();
200 const_reference back() const
202 return container_.back();
207 void push_back(T const & x)
209 typename Container::iterator it =
210 container_.insert(container_.end(), x);
211 iterCont_.push_back(it);
216 container_.pop_back();
217 iterCont_.pop_back();
220 iterator insert(iterator position, T const & x)
222 typename Container::iterator it =
223 container_.insert(position, x);
228 // void insert(iterator position, size_type n, T const & x);
230 template<class InputIterator>
231 void insert(iterator position,
232 InputIterator first, InputIterator last)
234 container_.insert(position, first, last);
238 iterator erase(iterator position)
240 typename Container::iterator it =
241 container_.erase(position);
246 iterator erase(iterator first, iterator last)
248 typename Container::iterator it =
249 container_.erase(first, last);
254 void swap(RandomAccessList & x)
256 std::swap(container_, x.container_);
257 std::swap(iterCont_, x.iterCont_);
267 void recreateVector()
270 typename Container::iterator beg = container_.begin();
271 typename Container::iterator end = container_.end();
272 for (; beg != end; ++beg)
273 iterCont_.push_back(beg);
277 Container container_;
278 /// Our container of iterators.