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
22 #define USE_OLD_ITERATOR 1
24 /// Random Access List.
26 This templatized class provide a std::vector like interface to a
27 standard std::list underneath. An important property is that it
28 keeps the std::list::iterator interface. A typical use would be:
30 typedef RandomAccessList<some_class> MyContainer;
32 Then you can use MyContainer as if it was a standard
33 std::vector<some_class> for operator[] access and as if it was a
34 standard std::list for iterator access. The main difference with
35 std::vector is that insertion of elements is much less costly. Compared
36 to a standard list alone, there is of course a small overhead because
37 the class always keeps its internal vector of iterator (it_vector_) up
41 class RandomAccessList {
44 typedef std::list<T> Container;
45 typedef typename Container::reference reference;
46 typedef typename Container::const_reference const_reference;
49 typedef typename Container::iterator iterator;
50 // const_iterator (below)
51 typedef typename Container::const_iterator const_iterator;
55 typedef typename Container::size_type size_type;
56 typedef typename Container::difference_type difference_type;
57 typedef typename Container::value_type value_type;
58 typedef typename Container::allocator_type allocator_type;
59 typedef typename Container::pointer pointer;
60 typedef typename Container::const_pointer const_pointer;
62 // const_reverse_iterator
64 typedef std::vector<typename Container::iterator> IterCont;
66 // construct/copy/destroy
71 // RandomAccessList(size_type n T const & value = T())
73 template<class InputIterator>
74 RandomAccessList(InputIterator first, InputIterator last)
81 RandomAccessList(RandomAccessList const & x)
83 assign(x.begin(), x.end());
86 // ~RandomAccessList()
89 RandomAccessList & operator=(RandomAccessList const & x)
91 assign(x.begin(), x.end());
95 template<class InputIterator>
96 void assign(InputIterator first, InputIterator last)
98 container_.assign(first, last);
103 // void assign(size_type n, T const & u);
109 return container_.begin();
112 const_iterator begin() const
114 return container_.begin();
119 return container_.end();
122 const_iterator end() const
124 return container_.end();
127 // reverse_iterator rbegin();
128 // const_reverse_iterator rbegin() const;
129 // reverse_iterator rend();
130 // const_reverse_iterator rend() const;
133 size_type size() const
135 return iterCont_.size();
138 size_type max_size() const
140 return iterCont_.max_size();
143 // void resize(size_type sz, T c = T());
145 size_type capacity() const
147 return iterCont_.capacity();
152 return container_.empty();
155 // void reserve(size_type n);
159 reference operator[](size_type pos)
161 return *iterCont_[pos];
165 const_reference operator[](size_type pos) const
167 return *iterCont_[pos];
170 reference at(size_type pos)
172 return *iterCont_.at(pos);
175 const_reference at(size_type pos) const
177 return *iterCont_.at(pos);
182 return container_.front();
185 const_reference front() const
187 return container_.front();
192 return container_.back();
195 const_reference back() const
197 return container_.back();
202 void push_back(T const & x)
204 typename Container::iterator it =
205 container_.insert(container_.end(), x);
206 iterCont_.push_back(it);
211 container_.pop_back();
212 iterCont_.pop_back();
215 iterator insert(iterator position, T const & x)
217 typename Container::iterator it =
218 container_.insert(position, x);
223 // void insert(iterator position, size_type n, T const & x);
225 template<class InputIterator>
226 void insert(iterator position,
227 InputIterator first, InputIterator last)
229 container_.insert(position, first, last);
233 iterator erase(iterator position)
235 typename Container::iterator it =
236 container_.erase(position);
241 iterator erase(iterator first, iterator last)
243 typename Container::iterator it =
244 container_.erase(first, last);
249 void swap(size_t i, size_t j)
251 size_t const p = std::max(i, j);
252 size_t const q = std::min(i, j);
253 container_.splice(iterCont_[p], container_, iterCont_[q]);
254 container_.splice(iterCont_[q], container_, iterCont_[p]);
258 void splice(iterator where, iterator first, iterator last)
260 container_.splice(where, container_, first, last);
264 void swap(RandomAccessList & x)
266 std::swap(container_, x.container_);
267 std::swap(iterCont_, x.iterCont_);
276 size_t position(iterator it) const
278 size_t const s = iterCont_.size();
279 for (size_t i = 0; it != s; ++i) {
280 if (iterCont_[i] == it)
286 size_t position(const_iterator it) const
288 size_t const s = iterCont_.size();
289 for (size_t i = 0; i != s; ++i) {
290 if (iterCont_[i] == it)
297 const_iterator iterator_at(size_t i) const
299 return (i == size()) ? end() : const_iterator(iterCont_[i]);
302 iterator iterator_at(size_t i)
304 return (i == size()) ? end() : iterCont_[i];
308 void recreateVector()
311 typename Container::iterator beg = container_.begin();
312 typename Container::iterator end = container_.end();
313 for (; beg != end; ++beg)
314 iterCont_.push_back(beg);
318 Container container_;
319 /// Our container of iterators.