c++ - 通过类存储和更新 vector 中的当前最小值

Question

我正在尝试实现一种数据结构，它通过存储当前最小值来更快地获取 vector 中的最小元素。 v 是一个 vector ，定义为 cont 类的私有(private)变量。

vector 中最小元素的索引存储在cont 的私有(private)变量mindex 中。 mindex 由此类的默认构造函数初始化为 0。

每当我插入一个新元素时，我都会更新最小值:

void cont<T>::insert(const T & newItem, int index){ 
    v.insert(v.begin() + index, newItem);
    if (newItem < v[mindex]) mindex = index;    
}

每当 mindex 处的元素弹出时，我也会运行 updatemin()(定义如下):

T cont<T>::pop_front(){
    T elem = v.front();
    v.erase(v.begin()); 
    if (mindex == 0) updatemin();       
    return elem;
}

T cont<T>::pop_back(){
    T elem = v.back();
    v.pop_back();
    if (mindex == v.size() - 1) updatemin();
    return elem;
}

T cont<T>::remove(int index){
    T elem = v[index];
    v.erase(v.begin() + index);
    if (index == mindex) updatemin();   
    return elem;
}

updatemin() 定义如下:

void cont<T>::updatemin() {
    for (unsigned long i = 0; i < v.size(); ++i) 
        if (v[i] < v[mindex]) mindex = i;
}

但是，mindex 在执行这些函数时不包含正确的值。在返回 mindex 之前运行 updatemin() 会返回正确的值。可能是什么问题？

Answer 1

您在跟踪最小值方面遇到了一些问题。所有这一切的原因是您没有考虑到当您插入、删除等操作时 min 的索引实际上发生了变化:

1-在insert函数中，你没有考虑到如果新数插入到mindex之前的索引处，那么mindex应该在比较之前递增:

void cont<T>::insert(const T & newItem, int index){ 
    v.insert(v.begin() + index, newItem);
    if (index < mindex) mindex++;
    if (newItem <= v[mindex]) mindex = index;    
}

2- pop_front:

T cont<T>::pop_front(){
    T elem = v.front();
    v.erase(v.begin()); 
    if (mindex == 0) updatemin();
    else mindex--;       
    return elem;
}

3-删除:

T cont<T>::remove(int index){
    T elem = v[index];
    v.erase(v.begin() + index);
    if (index == mindex) updatemin();
    else if (index < mindex) mindex--;   
    return elem;
}

祝你好运