At 02:09 AM 3/11/2005, Eric Niebler wrote:

It's impossible to say, since I don't know how hashed_array_tree is defined and I don't have a way to find out. If you could post a minimal, complete example that reproduces the problem, I could probably tell you what's wrong.

The trouble is that I wasn't sure how to make things any more minimal, since I don't know what aspects of the container's definition are relevant; I'll attach the headers for the hashed_array_tree, though. // -*- c++ -*- #pragma once namespace cphstl { template <class T, class A = allocator<T> > class hashed_array_tree { template <class T, class A = allocator<T> > friend class hat_iterator; template <class T, class A = allocator<T> > friend class hat_const_iterator; private: inline void find_index (unsigned int n, int& leaf, int& index) { leaf = n >> _power; index = n & _mask; } inline int find_leafsize (unsigned int n) { int leafsize = 1, capacity = 1; while (capacity < (int) n) { leafsize <<= 1; capacity <<= 2; } return leafsize; } public: typedef T value_type; typedef A allocator_type; typedef typename A::size_type size_type; typedef typename A::difference_type difference_type; typedef hat_iterator<T, A> iterator; typedef hat_const_iterator<T, A> const_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; typedef typename A::pointer pointer; typedef typename A::const_pointer const_pointer; typedef typename A::reference reference; typedef typename A::const_reference const_reference; hashed_array_tree (const size_type c = 1, const value_type& val = value_type(), const A& a = A()) : _alloc(a), _size(0) { // Find the initial capacity as the square of a power of two // that corresponds best to the initial_capacity. _leafsize = find_leafsize((unsigned int)c); _top_array = _palloc.allocate(_leafsize); int leafs = (int)(c / _leafsize + (c % _leafsize ? 1 : 0)); for (int i = 0; i < leafs; i++) { _top_array[i] = _alloc.allocate(_leafsize); for (int j = 0; j < _leafsize; j++) _alloc.construct(&_top_array[i][j], val); } _capacity = _leafsize * leafs; _power = log_2_ceil(_leafsize); _mask = (1 << _power) - 1; } hashed_array_tree(const hashed_array_tree& v, const A& a = A()) : _leafsize(v._leafsize), _mask(v._mask), _power(v._power), _alloc(a), _capacity(v._capacity), _size(v._size) { // Allocate the top array and the leafs. _top_array = _palloc.allocate(_leafsize); // Copy the elements. int leafs = (int)(_capacity / _leafsize); for (int i = 0; i < leafs; i++) { _top_array[i] = _alloc.allocate(_leafsize); for (int j = 0; j < _leafsize; j++) { _alloc.construct(&_top_array[i][j], v._top_array[i][j]); } } } ~hashed_array_tree () { int leafs = (int)(_capacity / _leafsize); for (int i = 0; i < leafs; i++) { for (int j = 0; j < _leafsize; j++) _alloc.destroy(&_top_array[i][j]); _alloc.deallocate(_top_array[i], _leafsize); } _palloc.deallocate(_top_array, _leafsize); } iterator begin() {return iterator(0, this);} iterator end() {return iterator(_size, this);} const_iterator begin() const {return const_iterator(0, this);} const_iterator end() const {return const_iterator(_size, this);} reverse_iterator rbegin() { return reverse_iterator(iterator(_size, this)); } reverse_iterator rend() { return reverse_iterator(iterator(0, this)); } const_reverse_iterator rbegin() const { return const_reverse_iterator(const_iterator(_size, this)); } const_reverse_iterator rend() const { return const_reverse_iterator(const_iterator(0, this)); } reference operator[] (size_type n) { return _top_array[n >> _power][n & _mask]; } const_reference operator[] (size_type n) const { return _top_array[n >> _power][n & _mask]; } reference front() { return _size == 0 ? 0 : _top_array[0][0]; } const_reference front() const { return _size == 0 ? 0 : _top_array[0][0]; } reference back() { if (_size == 0) return 0; return _top_array[_size >> _power][_size & _mask]; } const_reference back() const { if (_size == 0) return 0; return _top_array[_size >> _power][_size & _mask]; } hashed_array_tree& operator=(const hashed_array_tree& v) { // If the leafsize of the two trees are different we just // deallocate everything and allocate new leafs. if (_leafsize != v._leafsize) { // Destroy and deallocate everything. int leafs = _capacity / _leafsize; for (int i = 0; i < leafs; i++) { for (int j = 0; j < _leafsize; j++) _alloc.destroy(&_top_array[i][j]); _alloc.deallocate(_top_array[i], _leafsize); } _palloc.deallocate(_top_array, _leafsize); // Allocate a new top_array and allocate the new // elements. While doing this we copy the values from v into // the new leafs. _top_array = _palloc.allocate(v._leafsize); int need = v._capacity / v._leafsize; for (int i = 0; i < need; i++) { _top_array[i] = _alloc.allocate(v._leafsize); for (int j = 0; j < v._leafsize; j++) _alloc.construct(&_top_array[i][j], v._top_array[i][j]); } _leafsize = v._leafsize; _mask = v._mask; _power = v._power; } else { // The leafsizes are the same. Now we free the space that is // no longer needed or allocate extra leafs if they are // needed. int leafs = _capacity / _leafsize; int need = v._capacity / _leafsize; if (leafs < need) { // We have to allocate extra leafs. for (int i = leafs; i < need; i++) _top_array[i] = _alloc.allocate(_leafsize); } else { // We might have to deallocate some leafs. for (int i = need; i < leafs; i++) { for (int j = 0; j < _leafsize; j++) _alloc.destroy(&_top_array[i][j]); _alloc.deallocate(_top_array[i], _leafsize); } // We set leafs to need to make sure that element copying // works. leafs = need; } // Copy the data from v into the new storage. First we copy // into the old leafs where destruction of old elements are // needed. for (int i = 0; i < leafs; i++) { for (int j = 0; j < _leafsize; j++) { _alloc.destroy(&_top_array[i][j]); _alloc.construct(&_top_array[i][j], v._top_array[i][j]); } } // Then we copy into the new leafs that doesn't need // destruction of elements. for (int i = leafs; i < need; i++) { for (int j = 0; j < _leafsize; j++) _alloc.construct(&_top_array[i][j], v._top_array[i][j]); } } _size = v._size; _capacity = v._capacity; return *this; } void reserve(size_type n) { if (n <= _capacity) return; // There are two cases here, one where we have to change the // leafsize and one where we can reserve the space without // changing the leafsize. int new_leafsize = find_leafsize(n); int needed_leafs = n / new_leafsize + (n % new_leafsize ? 1 : 0); value_type val = value_type(); if (_leafsize == new_leafsize) { for (int i = _capacity / _leafsize; i < needed_leafs; i++) { _top_array[i] = _alloc.allocate(_leafsize); for (int j = 0; j < _leafsize; j++) _alloc.construct(&_top_array[i][j], val); _capacity += _leafsize; } } else { pointer* new_top_array = _palloc.allocate(new_leafsize); // For each new leaf that is needed we allocate it and either // copy the old value into the position or construct it with // the default value val. First we allocate the new leafs. for (int i = 0; i < needed_leafs; i++) new_top_array[i] = _alloc.allocate(new_leafsize); // Then we copy the elements from the old top_array. // x is the number of old leafs that fit into one new leaf. int x = new_leafsize / _leafsize; int leafs = _capacity / _leafsize; for (int i = 0; i < leafs; i++) { for (int j = 0; j < _leafsize; j++) { _alloc.construct(&new_top_array[i/x][(i%x) * _leafsize + j], _top_array[i][j]); _alloc.destroy(&_top_array[i][j]); } _alloc.deallocate(_top_array[i], _leafsize); } // Now we have to check wether one of the leafs have not been // fully constructed. int idx = (_capacity / new_leafsize + (_capacity % new_leafsize ? 1 : 0)) - 1; int start; if ((start = _capacity % new_leafsize) != 0) { for (int i = start; i < new_leafsize; i++) _alloc.construct(&new_top_array[idx][i], val); idx++; } // The rest of the needed leafs only needs to be constructed // with the standard value val. for (int i = idx; i < needed_leafs; i++) { for (int j = 0; j < new_leafsize; j++) _alloc.construct(&new_top_array[i][j], val); } _top_array = new_top_array; _leafsize = new_leafsize; _capacity = _leafsize * needed_leafs; _power = log_2_ceil(_leafsize); _mask = (1 << _power) - 1; } } void swap (hashed_array_tree& v) { int tmp_leafsize = _leafsize; unsigned int tmp_power = _power; unsigned int tmp_mask = _mask; unsigned int tmp_capacity = _capacity; unsigned int tmp_size = _size; value_type **tmp_top_array = _top_array; _leafsize = v._leafsize; _power = v._power; _mask = v._mask; _capacity = v._capacity; _size = v._size; _top_array = v._top_array; v._leafsize = tmp_leafsize; v._power = tmp_power; v._mask = tmp_mask; v._capacity = tmp_capacity; v._size = tmp_size; v._top_array = tmp_top_array; } void push_back (const_reference x) { // Check to see is extra storage must be allocated. if (_size == _capacity) { // Check to see if we need to change leafsize. if (_size == (unsigned int)_leafsize * _leafsize) { int new_leafsize = _leafsize << 1; pointer* new_top_array = _palloc.allocate(new_leafsize); // The is one special case here and that's when the old // leafsize is 1. This is handled separately here. This is a // special case because the moving of old elements does not // completely fill the new leafs of the new top_array. if (_leafsize == 1) { new_top_array[0] = _alloc.allocate(2); _alloc.construct(&new_top_array[0][0], _top_array[0][0]); _alloc.construct(&new_top_array[0][1], x); _alloc.destroy(&_top_array[0][0]); _alloc.deallocate(_top_array[0], _leafsize); _palloc.deallocate(_top_array, _leafsize); _top_array = new_top_array; _leafsize = 2; _capacity = 2; _power = 1; _mask = 1; } else { // This loops over the new leafs needed by the objects in // the old leafs. _power += 1; size_type last_leaf = _size >> _power; for (size_type i = 0; i < last_leaf; i++) { new_top_array[i] = _alloc.allocate(new_leafsize); size_type pos = 0; // The starting position in this new leaf. // This loops over the next two old leafs that need to // be copied into new leafs. size_type stop_index = (i + 1) * 2; for (size_type j = i * 2; j < stop_index; j++) { // Copy the actual elements. for (int k = 0; k < _leafsize; k++) { _alloc.construct(&new_top_array[i][pos++], _top_array[j][k]); _alloc.destroy(&_top_array[j][k]); } _alloc.deallocate(_top_array[j], _leafsize); } } _palloc.deallocate(_top_array, _leafsize); _top_array = new_top_array; // Allocate the extra leaf that we wanted to begin with. _top_array[last_leaf] = _alloc.allocate(new_leafsize); value_type val = value_type(); for (int i = 1; i < new_leafsize; i++) _alloc.construct(&_top_array[last_leaf][i], val); _leafsize = new_leafsize; _capacity += _leafsize; _mask = (_mask<<1)|1; // Insert the element. _alloc.construct(&_top_array[last_leaf][0], x); } } else { // If no change in leafsize is needed we just allocate an // extra leaf. size_type new_leaf = _capacity >> _power; value_type val = value_type(); _top_array[new_leaf] = _alloc.allocate(_leafsize); for (int i = 1; i < _leafsize; i++) _alloc.construct(&_top_array[new_leaf][i], val); _capacity += _leafsize; // Insert the element. _alloc.construct(&_top_array[new_leaf][0], x); } } else { // Insert the new element. int leaf = (int)(_size >> _power); int leaf_idx = (int)(_size & _mask); _alloc.destroy(&_top_array[leaf][leaf_idx]); _alloc.construct(&_top_array[leaf][leaf_idx], x); } _size += 1; } void pop_back () { value_type val = value_type(); size_type max_capacity = _leafsize * _leafsize; _size -= 1; // Check if resizing is needed. if (_capacity != 1 && _size <= max_capacity / 8) { int new_leafsize = _leafsize >> 1; pointer* new_top_array = _palloc.allocate(new_leafsize); size_type last_leaf = _size >> _power; size_type last_idx = _size & _mask; size_type cur_new_leaf = 0; // Start by allocating the leafs that are needed in the new // top_array. size_type new_leafs = _size / new_leafsize + (_size % new_leafsize ? 1 : 0); if (new_leafs == 0) new_leafs = 1; // If _size is 0. for (size_type i = 0; i < new_leafs; i++) new_top_array[i] = _alloc.allocate(new_leafsize); // For every leaf containing data in the old top_array but // the last one. for (size_type i = 0; i < last_leaf; i++) { for (int j = 0; j < new_leafsize; j++) _alloc.construct(&new_top_array[cur_new_leaf][j], _top_array[i][j]); cur_new_leaf++; for (int j = new_leafsize; j < _leafsize; j++) _alloc.construct(&new_top_array[cur_new_leaf][j%new_leafsize], _top_array[i][j]); cur_new_leaf++; } // Now take care of the last leaf. First check to see if // index == 0 in which case no more elements must be moved. if (last_idx != 0) { // See if two new leafs are needed. if ((int)last_idx > new_leafsize) { // Fill the first leaf. for (int j = 0; j < new_leafsize; j++) _alloc.construct(&new_top_array[cur_new_leaf][j], _top_array[last_leaf][j]); cur_new_leaf++; // And copy the elements until n into the last leaf. for (size_type j = new_leafsize; j < last_idx; j++) _alloc.construct(&new_top_array[cur_new_leaf][j%new_leafsize], _top_array[last_leaf][j]); // Construct the empty spaces. for (int j = last_idx%new_leafsize; j < new_leafsize; j++) _alloc.construct(&new_top_array[cur_new_leaf][j], val); } else { for (size_type j = 0; j < last_idx; j++) _alloc.construct(&new_top_array[cur_new_leaf][j], _top_array[last_leaf][j]); // Construct the empty spaces. for (int j = last_idx; j < new_leafsize; j++) _alloc.construct(&new_top_array[cur_new_leaf][j], val); } } // Destroy the elements in the old top_array. last_leaf = _capacity / _leafsize; for (size_type i = 0; i < last_leaf; i++) { for (int j = 0; j < _leafsize; j++) _alloc.destroy(&_top_array[i][j]); _alloc.deallocate(_top_array[i], _leafsize); } _palloc.deallocate(_top_array, _leafsize); _top_array = new_top_array; _leafsize = new_leafsize; _capacity = new_leafs * _leafsize; _power -= 1; _mask = _mask >> 1; } else { // No resizing is needed. size_type last_leaf = _size >> _power; size_type last_idx = _size & _mask; _alloc.destroy(&_top_array[last_leaf][last_idx]); _alloc.construct(&_top_array[last_leaf][last_idx], val); // Check to see if there are two empty leafs. If so we // deallocate the last one. last_leaf = (_capacity - 1) >> _power; if (last_leaf >= ((_size - 1) >> _power) + 2) { for (int i = 0; i < _leafsize; i++) _alloc.destroy(&_top_array[last_leaf][i]); _alloc.deallocate(_top_array[last_leaf], _leafsize); _capacity -= _leafsize; } } } // This function could be optimized when a resize is done by // moving elements while copying them from the old top_array. It // has not been done because of 1) time, 2) it's not necessary for // what I'm meassuring in my report. iterator insert(iterator pos, const value_type& x) { // Allocate an extra leaf if this is needed. if (_size == _capacity) { value_type val = value_type(); // Check to see if we need to change leafsize. if (_size == (unsigned int)_leafsize * _leafsize) { int new_leafsize = _leafsize << 1; pointer* new_top_array = _palloc.allocate(new_leafsize); // The is one special case here and that's when the old // leafsize is 1. This is handled separately here. This is a // special case because the moving of old elements does not // completely fill the new leafs of the new top_array. if (_leafsize == 1) { new_top_array[0] = _alloc.allocate(2); _alloc.construct(&new_top_array[0][0], _top_array[0][0]); _alloc.construct(&new_top_array[0][1], val); _alloc.destroy(&_top_array[0][0]); _alloc.deallocate(_top_array[0], _leafsize); _palloc.deallocate(_top_array, _leafsize); _top_array = new_top_array; _leafsize = 2; _capacity = 2; _power = 1; _mask = 1; } else { // This loops over the new leafs needed by the objects in // the old leafs. int last_leaf = _size / new_leafsize; for (int i = 0; i < last_leaf; i++) { new_top_array[i] = _alloc.allocate(new_leafsize); int pos = 0; // The starting position in this new leaf. // This loops over the next two old leafs that need to // be copied into new leafs. for (int j = i * 2; j < (i + 1) * 2; j++) { // Copy the actual elements. for (int k = 0; k < _leafsize; k++) { _alloc.construct(&new_top_array[i][pos++], _top_array[j][k]); _alloc.destroy(&_top_array[j][k]); } _alloc.deallocate(_top_array[j], _leafsize); } } _palloc.deallocate(_top_array, _leafsize); _top_array = new_top_array; // Allocate the extra leaf that we wanted to begin with. _top_array[last_leaf] = _alloc.allocate(new_leafsize); for (int i = 0; i < new_leafsize; i++) _alloc.construct(&_top_array[last_leaf][i], val); _leafsize = new_leafsize; _capacity += _leafsize; _power = log_2_ceil(_leafsize); _mask = (1 << _power) - 1; } } else { // If no change in leafsize is needed we just allocate an // extra leaf. int new_leaf = _capacity / _leafsize; _top_array[new_leaf] = _alloc.allocate(_leafsize); for (int i = 0; i < _leafsize; i++) _alloc.construct(&_top_array[new_leaf][i], val); _capacity += _leafsize; } } // Insert the element into position n. int index = pos - this->begin(); int leaf = index / _leafsize; int n = index % _leafsize; // The index in the leaf. // Now move all the elements in front of position n one space up // in the tree. int last_leaf, move_from; find_index(_size - 1, last_leaf, move_from); // This loops over the leaf from the last one to the one that // contains n. for (int i = last_leaf; i >= leaf; i--) { // First we check to see if we need to move the last element // in the leaf into the leaf in front of this one. if (move_from == _leafsize - 1) { _alloc.destroy(&_top_array[i+1][0]); _alloc.construct(&_top_array[i+1][0], _top_array[i][move_from--]); } // The we move the rest of the elements inside of the leaf. If // this is the leaf that contains n we only move the elements // until the n'th position. if (i == leaf) { for (int j = move_from; j >= n; j--) { _alloc.destroy(&_top_array[i][j+1]); _alloc.construct(&_top_array[i][j+1], _top_array[i][j]); } } else { for (int j = move_from; j >= 0; j--) { _alloc.destroy(&_top_array[i][j+1]); _alloc.construct(&_top_array[i][j+1], _top_array[i][j]); } } move_from = _leafsize - 1; } // Insert x into the hole that has appeared. _alloc.destroy(&_top_array[leaf][n]); _alloc.construct(&_top_array[leaf][n], x); _size += 1; return iterator(n, this); } iterator erase(iterator pos) { int n = pos - this->begin(); value_type val = value_type(); // Check if we need to change to another leafsize after this // erase. We change leafsize if the size is 1/8 of the max // capacity with the current leafsize. unsigned int max_cap = _leafsize * _leafsize; if (_capacity != 1 && _size - 1 <= max_cap / 8) { int new_leafsize = _leafsize >> 1; pointer *new_top_array = _palloc.allocate(new_leafsize); int last_leaf = (_size - 1) / _leafsize; int last_idx = (_size - 1) % _leafsize; int n_leaf = n / _leafsize; int n_idx = n % _leafsize; int cur_new_leaf = 0; // Start by allocating the leafs that are needed in the new // top_array. int new_leafs = new_leafsize == 1 ? 1 : (_size - 1) / new_leafsize + ((_size - 1) % new_leafsize ? 1 : 0); for (int i = 0; i < new_leafs; i++) new_top_array[i] = _alloc.allocate(new_leafsize); // For every leaf containing data in the old top_array. for (int i = 0; i <= last_leaf; i++) { // If this is before the leaf that contain n we just copy // the elements. if (i < n_leaf) { int split; for (int j = 0; j < _leafsize; j++) { split = j >= new_leafsize ? 1 : 0; _alloc.construct(&new_top_array[cur_new_leaf+split] [j-new_leafsize*split], _top_array[i][j]); } } else if (i == n_leaf) { // If this is exactly the leaf that contain n. int split; for (int j = 0; j < n_idx; j++) { split = j >= new_leafsize ? 1 : 0; _alloc.construct(&new_top_array[cur_new_leaf+split] [j-new_leafsize*split], _top_array[i][j]); } // Now we have to check if this is the last leaf in which // case we only have to copy the elements until last_idx. if (i == last_leaf) { for (int j = n_idx; j < last_idx; j++) { split = j >= new_leafsize ? 1 : 0; _alloc.construct(&new_top_array[cur_new_leaf+split] [j-new_leafsize*split], _top_array[i][j+1]); } // Now we need to construct the last elements in // new_top_array. int leaf, idx; if (last_idx >= new_leafsize) { leaf = cur_new_leaf + 1; idx = last_idx - new_leafsize; if (idx != 0) { for (int j = idx + 1; j < new_leafsize; j++) _alloc.construct(&new_top_array[leaf][j], val); } } else { if (n_idx != 0) { for (int j = last_idx + 1; j < new_leafsize; j++) _alloc.construct(&new_top_array[cur_new_leaf][j], val); } } } else { // If this is not the last leaf we copy all the elements // from this leaf (after the n'th position) into the new // leafs. When that is done we copy the first element // from the next leaf into the last position of the new // leaf. for (int j = n_idx; j < _leafsize - 1; j++) { split = j >= new_leafsize ? 1 : 0; _alloc.construct(&new_top_array[cur_new_leaf+split] [j-new_leafsize*split], _top_array[i][j+1]); } _alloc.construct(&new_top_array[cur_new_leaf+1] [new_leafsize-1], _top_array[i+1][0]); } } else { // If this is a leaf that comes after the leaf that contain n. int split; // If this is the last leaf we just copy over the elements // from this leaf. if (i == last_leaf) { for (int j = 0; j < last_idx; j++) { split = j >= new_leafsize ? 1 : 0; _alloc.construct(&new_top_array[cur_new_leaf+split] [j-new_leafsize*split], _top_array[i][j+1]); } // Now we construct the last elements of the new leaf. int leaf, idx; if (last_idx >= new_leafsize) { leaf = cur_new_leaf + 1; idx = last_idx - new_leafsize; if (idx != 0) { for (int j = idx + 1; j < new_leafsize; j++) _alloc.construct(&new_top_array[leaf][j], val); } } else { if (last_idx != 0) { for (int j = last_idx + 1; j < new_leafsize; j++) _alloc.construct(&new_top_array[cur_new_leaf][j], val); } } } else { for (int j = 0; j < _leafsize - 1; j++) { split = j >= new_leafsize ? 1 : 0; _alloc.construct(&new_top_array[cur_new_leaf+split] [j-new_leafsize*split], _top_array[i][j+1]); } _alloc.construct(&new_top_array[cur_new_leaf+1] [new_leafsize-1], _top_array[i+1][0]); } } cur_new_leaf += 2; } // Destroy the elements in the old top_array. last_leaf = _capacity / _leafsize; for (int i = 0; i < last_leaf; i++) { for (int j = 0; j < _leafsize; j++) _alloc.destroy(&_top_array[i][j]); _alloc.deallocate(_top_array[i], _leafsize); } _palloc.deallocate(_top_array, _leafsize); _top_array = new_top_array; _leafsize = new_leafsize; _capacity = new_leafs * _leafsize; _power -= 1; _mask = _mask >> 1; } else { // If no resizing of leafs is necessary we just rearrange the // elements in the existing structure. We just start from the // n'th position and run forward through the leafs. int last_leaf = (_size - 1) / _leafsize; int last_idx = (_size - 1) % _leafsize; int n_leaf = n / _leafsize; int start_idx = n % _leafsize; for (int i = n_leaf; i <= last_leaf; i++) { // If this is the last leaf with data in it we only move // elements until last_idx. if (i == last_leaf) { for (int j = start_idx; j < last_idx; j++) { _alloc.destroy(&_top_array[i][j]); _alloc.construct(&_top_array[i][j], _top_array[i][j+1]); } _alloc.destroy(&_top_array[i][last_idx]); _alloc.construct(&_top_array[i][last_idx], val); } else { for (int j = start_idx; j < _leafsize - 1; j++) { _alloc.destroy(&_top_array[i][j]); _alloc.construct(&_top_array[i][j], _top_array[i][j+1]); } // Move the first element from the next leaf into the last // position in this leaf. This makes the hole that is // needed to start rearranging the next leaf. _alloc.destroy(&_top_array[i][_leafsize-1]); _alloc.construct(&_top_array[i][_leafsize-1], _top_array[i+1][0]); } start_idx = 0; } // Check to see if there are two empty leafs. If so we // deallocate the last one. last_leaf = _capacity / _leafsize - 1; if (last_leaf >= (int)((_size - 2) / _leafsize + 2)) { for (int i = 0; i < _leafsize; i++) _alloc.destroy(&_top_array[last_leaf][i]); _alloc.deallocate(_top_array[last_leaf], _leafsize); _capacity -= _leafsize; } } _size -= 1; return iterator(n, this); } void clear() { int last = (int)(_capacity / _leafsize); for (int i = 0; i < last; i++) { for (int j = 0; j < _leafsize; j++) _alloc.destroy(&_top_array[i][j]); _alloc.deallocate(_top_array[i], _leafsize); } _palloc.deallocate(_top_array, _leafsize); _size = 0; _capacity = 1; _leafsize = 1; _power = 0; _mask = 0; _top_array = _palloc.allocate(1); _top_array[0] = _alloc.allocate(1); _alloc.construct(&_top_array[0][0], value_type()); } template <class T, class A> friend bool operator==(const hashed_array_tree<T, A>& v1, const hashed_array_tree<T, A>& v2); template <class T, class A> friend bool operator<(const hashed_array_tree<T, A>& v1, const hashed_array_tree<T, A>& v2); const size_type size() const { return _size; } private: int _leafsize; unsigned int _mask; unsigned int _power; typedef typename A::rebind<typename A::pointer>::other palloc; palloc _palloc; allocator_type _alloc; protected: size_type _capacity; size_type _size; pointer *_top_array; }; template <class T, class A> bool operator==(const hashed_array_tree<T, A>& v1, const hashed_array_tree<T, A>& v2) { if (v1._size != v2._size) return false; else { for (unsigned int i = 0; i < v1._size; i++) { if (v1[i] != v2[i]) return false; } return true; } } template <class T, class A> bool operator<(const hashed_array_tree<T, A>& v1, const hashed_array_tree<T, A>& v2) { unsigned int size = v1._size < v2._size ? v1._size : v2._size; for (unsigned int i = 0; i < size; i++) { if (v1[i] < v2[i]) return true; else if (v1[i] > v2[i]) return false; } return (v1._size < v2._size); } }; #ifndef MATH_UTILS_H #define MATH_UTILS_H /** A logarithm function that computes \lfloor \log_2(x) \rfloor in LaTeX codes :-) This function computes the 2-logarithm of the parameter rounded down to the nearest integer. \param x The integer to calculate the 2-logarithm for. \return The rounded down result of the 2-logarithm function. */ inline unsigned int log_2 (unsigned int x) { unsigned int r = 0; x >>= 1; while (x) { r++; x >>= 1; } return r; } /** A logarithm function that computes \lceil \log_2(x) \rceil. This function computes the 2-logarithm of the parameter rounded up to the nearest integer. \param x The integer to calculate the 2-logarithm for. \return The rounded down result of the 2-logarithm function. */ inline unsigned int log_2_ceil (unsigned int x) { if (x == 0) return 0; unsigned int x_copy = x; unsigned int r = 0; x >>= 1; while (x) { r++; x >>= 1; } if (x_copy - (1<<r) != 0) r++; return r; } /** A power-of-2 shorthand. This define calculates the value of the power of two that is given in the parameter. This is just to make the code easier to read. \param x The power of 2 to calculate. \return The computed power of 2. */ #define pow_2(x) (1 << x) #endif

On Fri, Mar 11, 2005 at 10:32:18AM -0800, Eric Niebler wrote:

I don't see where hat_iterator and hat_const_iterator are defined. Please send a *complete* example.

They should have been in the third attached file ("hat_iterator.hpp"). Mike Daniels

At 03:46 PM 3/11/2005, Eric Niebler wrote:

For hat_const_iterator, the nested "reference" typedef is non-const, and operator* is returning a const reference. The nested reference type should be:

typedef typename A::const_reference reference;

Yep. Everything works just fine now; thanks!