容器模板类-减小容器大小

Question

我写了一些代码来减少模板化容器类的容量。从容器中删除元素后，擦除函数会检查是否有25%的总空间在使用，以及将容量减少一半是否会导致其小于我设置的默认大小。如果这两个返回true，则运行缩小大小函数。然而，如果这种情况发生在我处于const_idetator循环的中间时，我会得到一个segfault。

再次编辑：我认为这是因为const_iterator指针指向旧数组，需要指向由redize（）创建的新数组。。。现在该怎么做。。。

template <class T>
void sorted<T>::downsize(){
  // Run the same process as resize, except
  // in reverse (sort of). 
  int newCapacity = (m_capacity / 2);
  T *temp_array = new T[newCapacity];
  for (int i = 0; i < m_size; i++)
    temp_array[i] = m_data[i];
  // Frees memory, points m_data at the 
  // new, smaller array, sets the capacity
  // to the proper (lower) value.
  delete [] m_data;
  m_data = temp_array;
  setCap(newCapacity);
  cout << "Decreased array capacity to " << newCapacity << "." << endl;  
}

// Implementation of the const_iterator erase method.
template <class T>
typename sorted<T>::const_iterator sorted<T>::erase(const_iterator itr){  
  // This section is reused from game.cpp, a file provided in the
  // Cruno project. It handles erasing the element pointed to
  // by the constant iterator.
  T *end = &m_data[m_capacity];    // one past the end of data
  T *ptr = itr.m_current;        // element to erase
  // to erase element at ptr, shift elements from ptr+1 to 
  // the end of the array down one position
  while ( ptr+1 != end ) {
    *ptr = *(ptr+1);
    ptr++;
  }
  m_size--;
  // Once the element is removed, check to
  // see if a size reduction of the array is
  // necessary.
  // Initialized some new values here to make
  // sure downsize only runs when the correct
  // conditions are met.
  double capCheck = m_capacity;
  double sizeCheck = m_size;
  double usedCheck = (sizeCheck / capCheck);
  int boundCheck = (m_capacity / 2);
  if ((usedCheck <= ONE_FOURTH) && (boundCheck >= DEFAULT_SIZE))
    downsize();
  return itr;
}

// Chunk from main that erases.
int i = 0;
for (itr = x.begin(); itr != x.end(); itr++) {
  if (i < 7) x.erase(itr);
  i++;   
}

Answer 1

为了防止擦除循环中迭代器失效的问题，可以使用：

x.erase(itr++);

而不是单独的increment和increment调用（很明显，如果你没有擦除你循环的所有内容，你需要一个else case来增量超过未擦除的项。）注意，在这种情况下，你需要使用后增量而不是前增量。

不过整个事情看起来有点效率低下。转换为数组的方式表明，它只适用于某些容器类型。如果你期望从容器的中间进行大量擦除，那么你可以通过选择不同的容器来避免内存问题；也许可以列出。

如果您选择vector，您可能会发现调用shrink_to_fit正是您想要的。

还要注意，擦除有一个返回值，该值将指向元素在擦除后的（新）位置。

如果您将迭代器返回到新创建的容器的缩小版本，请注意，与原始容器end（）迭代器相比是不起作用的。

Answer 2

我解决了segfault问题！

当时的情况是，我的x.end（）使用的是数组的大小（而不是容量），其中大小是存储在数组中的数据元素的数量，而不是实际的数组大小。因此，当它寻找数组的末尾时，它将其视为实际末尾之前的许多元素。

现在来看更多有趣的问题！