Jean-Marc Lasgouttes a écrit :
"Abdelrazak" == Abdelrazak Younes <[EMAIL PROTECTED]> writes:
Abdelrazak> Did you try my suggested fix for output_latex? I cannot
Abdelrazak> verify it because I can't make mingw use safe_iterator. In
Abdelrazak> other word are you sure that it is not a problem of
Abdelrazak> output_latex instead?
I did not try it yet, but I do not see why it would assert with your
container and not with a vector (which has the same checks for end).
I do not remember whether I mentioned it already, but the
iterator::operator= entries seem strange to me. They seem to mix
freely iterator with const_iterator. Is that intentional?
Hum, brown paper bag for me. There is indeed a problem in my code:
const iterator & operator=(base_it const & it) {
Container::const_iterator::operator=(it);
return *this;
}
This should be of course (without the const):
const iterator & operator=(base_it const & it) {
Container::iterator::operator=(it);
return *this;
}
But I really don't think this is what created the safe_iterator crash.
Please find attached a corrected version of RandomAccessList.h.
Thanks for pointing this to me Jean-Marc,
Abdel.
// -*- C++ -*-
/**
* \file RandomAccessList.h
* This file is part of LyX, the document processor.
* Licence details can be found in the file COPYING.
*
* \author Abdelrazak Younes
*
* Full author contact details are available in file CREDITS.
*
*/
#ifndef _RANDOM_ACESS_LIST_H
#define _RANDOM_ACESS_LIST_H
#include "debug.h"
#include <boost/utility.hpp>
#include <vector>
#include <list>
#include <algorithm>
using std::endl;
/// Random Access List.
/**
This templatized class provide a std::vector like interface to a standard
std::list
underneath. An important property is that it keeps the std::list::iterator
interface.
A typical use would be:
typedef RandomAccessList<some_class> MyContainer;
Then you can use MyContainer as if it was a standard std::vector<some_class>
for operator[] access
and as if it was a standard std::list for iterator access.
The main difference with std::vector is that insertion of elements is much less
costly. Compared
to a standard list alone, there is of course a small overhead because the class
always keeps its
internal vector of iterator (ItVector_) up to date.
*/
template <class T>
class RandomAccessList
{
protected:
typedef std::list<T> Container;
typedef typename Container::const_iterator base_cit;
typedef typename Container::iterator base_it;
public:
typedef T value_type;
typedef typename Container::difference_type difference_type;
typedef size_t size_type;
///
class iterator: public Container::iterator
{
public:
iterator() {
}
iterator(base_it const & it) {
Container::iterator::operator=(it);
}
iterator & operator+=(difference_type pos) {
std::advance(*this, pos);
return *this;
}
iterator operator+(difference_type pos) const {
iterator it=*this;
std::advance(it, pos);
return it;
}
difference_type operator-(iterator it2) const {
return std::distance(*this, it2);
}
const iterator & operator=(base_it const & it) {
Container::iterator::operator=(it);
return *this;
}
};
///
class const_iterator: public Container::const_iterator
{
public:
const_iterator() {
}
const_iterator(base_cit const & it) {
Container::const_iterator::operator=(it);
}
const_iterator(iterator const & it) {
Container::const_iterator::operator=(static_cast<base_it>(it));
}
const_iterator & operator+=(difference_type pos) {
std::advance(*this, pos);
return *this;
}
const_iterator operator+(difference_type pos) const {
const_iterator it=*this;
std::advance(it, pos);
return it;
}
difference_type operator-(const_iterator it2) const {
return std::distance(*this, it2);
}
const const_iterator & operator=(base_cit const & it) {
Container::const_iterator::operator=(it);
return *this;
}
const const_iterator & operator=(base_it const & it) {
Container::const_iterator::operator=(it);
return *this;
}
const const_iterator & operator=(iterator const & it) {
Container::const_iterator::operator=(static_cast<base_it>(it));
return *this;
}
};
private:
/// Our container.
Container Container_;
/// Our vector of container iterator.
std::vector<iterator> ItVector_;
public:
///
RandomAccessList() {
}
/// Copy constructor.
RandomAccessList(RandomAccessList const & ext_list) {
const_iterator it_end = ext_list.end();
for (const_iterator it = ext_list.begin(); it != it_end; ++it)
push_back(*it);
}
/// Partial copy constructor.
/**
Copy "length" elements from ext_list beginning at pos.
*/
RandomAccessList(RandomAccessList const & ext_list, size_t pos, size_t
length) {
size_t end = pos+length;
for (size_t i = pos; i != end; ++i)
push_back(ext_list[i]);
}
/// Construct a new RandomAccessList by copying elements pointed from
it_start to it_end.
template<class It>
RandomAccessList(It it_start, It it_end) {
for (It it = it_start; it != it_end; ++it)
push_back(*it);
}
/// Copy ext_list.
void assign(RandomAccessList const & ext_list) {
assign(ext_list, 0, ext_list.size());
}
/// Copy ext_list from it_start to it_end.
template<class It>
void assign(It it_start, It it_end) {
clear();
for (It it = it_start; it != it_end; ++it)
push_back(*it);
}
/// Copy "length" elements from ext_list beginning at pos.
void assign(RandomAccessList const & ext_list, size_t pos, size_t
length) {
clear();
size_t end = pos+length;
for (size_t i = pos; i != end; ++i)
push_back(ext_list[i]);
}
value_type & at(size_t pos) {
// This test should be removed once output_*.C has been
verified.
if (pos >= ItVector_.size()) {
lyxerr[Debug::ACTION] << "trying to access element " <<
pos
<< " while size is "<< size() << endl;
return *ItVector_[size()-1];
}
// This test should be already done if compiled with
--enable-stdlib-debug
// but apparently not with mingw.
BOOST_ASSERT(pos < ItVector_.size());
// Make sure ItVector_ and Container_ are always in sync.
BOOST_ASSERT(ItVector_[pos]==boost::next(Container_.begin(),pos));
return *ItVector_[pos];
}
/// \todo remove first test (pos >= ItVector_.size()) when output_*.C
has been verified.
value_type const & at(size_t pos) const {
// This test should be removed once output_*.C has been
verified.
if (pos >= ItVector_.size()) {
lyxerr[Debug::ACTION] << "trying to access element " <<
pos
<< " while size is "<< size() << endl;
return *ItVector_[size()-1];
}
// This test should be already done if compiled with
--enable-stdlib-debug
// but apparently not with mingw.
BOOST_ASSERT(pos < ItVector_.size());
// Make sure ItVector_ and Container_ are always in sync.
BOOST_ASSERT(ItVector_[pos]==boost::next(Container_.begin(),pos));
return *ItVector_[pos];
}
size_t size() const {
return ItVector_.size();
}
const_iterator begin() const {
return Container_.begin();
}
iterator begin() {
return Container_.begin();
}
const_iterator end() const {
return Container_.end();
}
iterator end() {
return Container_.end();
}
value_type & back() {
return Container_.back();
}
value_type const & back() const {
return Container_.back();
}
value_type & front() {
return Container_.front();
}
value_type const & front() const {
return Container_.front();
}
bool empty() const {
return Container_.empty();
}
void clear() {
Container_.clear();
ItVector_.clear();
}
/// Erases 'length' elements starting from pos.
/**
\todo This could be optimized a bit by rebuilding ItVector instead of
multiple deletion.
Comments from Angus: use std::remove_if and vector<>::erase, passing the
same predicate to remove_if as is used by erase(size_t);
Refactor the other erase() member funtions to use this predicate
also?
std::remove_if doesn't actually remove anything from the vector. It
simply rearranges the
contents so that the stuff to be removed is all at the end, making it
trivial
(and cheap) to then used "itVector_.erase(it, itVector_.end());" to
resize the
vector. (it here is the iterator returned by std::remove_if). You just
need to
write the predicate that would actually flag up elements for removal.
*/
bool erase(size_t pos, size_t length) {
bool result=true;
size_t end = pos+length;
for (size_t i = pos; i != end; ++i)
result = result && erase(i);
return result;
}
/// Erases last element.
void pop_back() {
lyxerr[Debug::ACTION] << "pop_back from Container"<< endl;
Container_.pop_back();
ItVector_.pop_back();
lyxerr[Debug::ACTION] << "pop_back done"<< endl;
}
/// Erases the element at position pos.
bool erase(size_t pos) {
if (pos >= ItVector_.size()) {
lyxerr[Debug::ACTION] << "trying to erase element at "
<< pos << " while size is "<< size() << endl;
// What happened here?
return false;
}
if (pos == ItVector_.size()-1) {
pop_back();
return true;
}
lyxerr[Debug::ACTION] << "erasing element from Container at "
<< pos << endl;
Container_.erase(ItVector_[pos]);
ItVector_.erase(ItVector_.begin()+pos);
lyxerr[Debug::ACTION] << "erasing done"<< endl;
return true;
}
bool erase(iterator it) {
size_t pos = std::distance(Container_.begin(),
static_cast<base_it>(it));
return erase(pos);
}
bool erase(iterator start, iterator end) {
size_t startpos = std::distance(Container_.begin(),
static_cast<base_it>(start));
size_t endpos = std::distance(Container_.begin(),
static_cast<base_it>(end));
return erase(startpos, endpos-startpos);
}
void push_back(value_type const & new_element)
{
lyxerr[Debug::ACTION] << "push_back new_element in Container"<<
endl;
iterator it = Container_.insert(Container_.end(), new_element);
ItVector_.push_back(it);
lyxerr[Debug::ACTION] << "push_back done"<< endl;
}
/// Inserts the contents of an external container at position pos.
/**
The subsequent elements are shifted toward the end.
\todo This could be optimized a bit by rebuilding ItVector instead of
multiple insertion.
*/
template<class SomeContainer>
bool insert(size_t pos, SomeContainer const & some_container) {
bool result=true;
size_t i=pos;
typedef typename SomeContainer::const_iterator It;
It it_end = some_container.end();
for (It it = some_container.begin(); it != it_end; ++it) {
result = result && insert(i, *it);
++i;
}
return result;
}
/// Inserts an external RandomAccessList at position pos.
/**
The subsequent elements are shifted toward the end.
\todo This could be optimized a bit by rebuilding ItVector instead of
multiple insertion
and maybe using list::splice.
*/
bool insert(size_t pos, RandomAccessList const & ext_list, size_t
ext_pos, size_t length) {
bool result=true;
size_t i=pos;
size_t ext_end = ext_pos+length;
for (size_t j = ext_pos; j != ext_end; ++j) {
result = result && insert(i, ext_list[j]);
++i;
}
return result;
}
/// Inserts external elements pointed by iterator it_start and it_end
at position pos.
/**
The subsequent elements are shifted toward the end.
\return the position after the last inserted element.
\todo This could be optimized a bit by rebuilding ItVector instead of
multiple insertion
and maybe using list::splice.
*/
template<class It>
size_t insert(size_t pos, It it_start, It it_end) {
bool result=true;
size_t i=pos;
for (It it = it_start; it != it_end; ++it) {
result = result && insert(i, *it);
++i;
}
if (result)
return i;
return size();
}
/// Inserts external elements pointed by iterator it_start and it_end
before element pointed by it.
/**
The subsequent elements are shifted toward the end.
\return the iterator after the last inserted element.
\todo This could be optimized a bit by rebuilding ItVector instead of
multiple insertion
and maybe using list::splice.
*/
template<class It>
iterator insert(iterator it, It it_start, It it_end) {
size_t pos = std::distance(Container_.begin(),
static_cast<base_it>(it));
pos = insert(pos, it_start, it_end);
if (pos < size())
return ItVector_[pos];
return Container_.end();
}
/// Inserts new_element at position pos.
/// The subsequent value_types are shifted toward the end.
bool insert(size_t pos, value_type const & new_element) {
if (pos > ItVector_.size()) {
lyxerr[Debug::ACTION] << "trying to insert element at "
<< pos << " while size is "<< size() << endl;
// What happened here?
return false;
}
if (pos == ItVector_.size()) {
push_back(new_element);
return true;
}
lyxerr[Debug::ACTION] << "inserting new_element in Container at
"<< pos << endl;
iterator it = Container_.insert(ItVector_[pos], new_element);
ItVector_.insert(ItVector_.begin()+pos, it);
lyxerr[Debug::ACTION] << "insertion done"<< endl;
return true;
}
/// Inserts new_element before element pointed by iterator it.
/**
\return The iterator pointing to the newly inserted element
or Container_.end() if the insertion did not succeed.
*/
iterator insert(iterator it, value_type const & new_element) {
size_t pos = std::distance(Container_.begin(),
static_cast<base_it>(it));
if (insert(pos, new_element))
return ItVector_[pos];
return Container_.end();
}
value_type & operator[](size_t pos) {
return at(pos);
}
value_type const & operator[](size_t pos) const {
return at(pos);
}
iterator operator()(size_t pos) {
return ItVector_[pos];
}
const_iterator operator()(size_t pos) const {
return ItVector_[pos];
}
RandomAccessList & operator=(RandomAccessList const & ext_list) {
assign(ext_list);
return *this;
}
}; // RandomAccessList
#endif
