C++：无动态分配计算向量映射值的中位数实现方法

问题背景 #

定义了自定义结构体：

struct customStruct {
    float x;
    float y;
    float u;
    float v;
};

实例存储在myType::ptr_vector<customStruct>中，现有calcInitialVal函数通过生成临时向量tmp存储每个元素的两个映射值，再用nth_element取第N个值（N为points的元素数量），但tmp会触发动态内存分配，希望在不分配堆内存的前提下实现相同逻辑。

解决方案 #

核心思路是不存储所有映射值，而是在需要比较时实时计算，避免动态内存分配。 以下提供两种可行实现方式：

方法1：实现虚拟随机访问迭代器 #

通过自定义迭代器模拟访问2N个映射值的序列，迭代器解引用时实时计算对应值，直接适配std::nth_element：

// 封装映射逻辑的函数对象，可按需修改计算规则
struct ValueMapper {
    float s;
    float x0;
    float y0;

    float operator()(const customStruct& elem, bool is_x) const {
        return is_x ? elem.u - s * (elem.x - x0) : elem.v - s * (elem.y - y0);
    }
};

// 虚拟随机访问迭代器，模拟访问2N个映射值
class VirtualIter {
public:
    using value_type = float;
    using difference_type = ptrdiff_t;
    using pointer = const float*;
    using reference = float;
    using iterator_category = std::random_access_iterator_tag;

    VirtualIter(const myType::ptr_vector<customStruct>* points, const ValueMapper* mapper, ptrdiff_t idx)
        : points_(points), mapper_(mapper), idx_(idx) {}

    reference operator*() const {
        size_t elem_idx = idx_ / 2;
        bool is_x = (idx_ % 2 == 0);
        return (*mapper_)((*points_)[elem_idx], is_x);
    }

    bool operator==(const VirtualIter& other) const {
        return points_ == other.points_ && idx_ == other.idx_;
    }

    bool operator!=(const VirtualIter& other) const {
        return !(*this == other);
    }

    VirtualIter& operator++() {
        idx_++;
        return *this;
    }

    VirtualIter operator++(int) {
        VirtualIter tmp = *this;
        idx_++;
        return tmp;
    }

    VirtualIter& operator--() {
        idx_--;
        return *this;
    }

    VirtualIter operator--(int) {
        VirtualIter tmp = *this;
        idx_--;
        return tmp;
    }

    VirtualIter operator+(difference_type n) const {
        return VirtualIter(points_, mapper_, idx_ + n);
    }

    VirtualIter operator-(difference_type n) const {
        return VirtualIter(points_, mapper_, idx_ - n);
    }

    difference_type operator-(const VirtualIter& other) const {
        return idx_ - other.idx_;
    }

    bool operator<(const VirtualIter& other) const {
        return **this < *other;
    }

    bool operator>(const VirtualIter& other) const {
        return **this > *other;
    }

    bool operator<=(const VirtualIter& other) const {
        return !(*this > other);
    }

    bool operator>=(const VirtualIter& other) const {
        return !(*this < other);
    }

    VirtualIter& operator+=(difference_type n) {
        idx_ += n;
        return *this;
    }

    VirtualIter& operator-=(difference_type n) {
        idx_ -= n;
        return *this;
    }

private:
    const myType::ptr_vector<customStruct>* points_;
    const ValueMapper* mapper_;
    ptrdiff_t idx_;
};

// 改造后的calcInitialVal，无动态内存分配
float calcInitialVal(const myType::ptr_vector<customStruct>& points) {
    float s = 3;
    float x0 = 5;
    float y0 = 1.5;
    ValueMapper mapper{s, x0, y0};

    size_t numPoints = points.size();
    VirtualIter begin(&points, &mapper, 0);
    VirtualIter end(&points, &mapper, 2 * numPoints);
    VirtualIter nth = begin + numPoints;

    std::nth_element(begin, nth, end);
    return *nth;
}

方法2：手动实现快速选择算法 #

直接实现nth_element的底层快速选择逻辑，过程中实时计算映射值，完全避免内存分配：

// 实时计算单个映射值
float getMappedValue(const customStruct& elem, float s, float x0, float y0, size_t idx_in_pair) {
    return idx_in_pair == 0 ? elem.u - s * (elem.x - x0) : elem.v - s * (elem.y - y0);
}

// 快速选择核心：找到虚拟序列中第k小的元素
float quickSelect(const myType::ptr_vector<customStruct>& points, float s, float x0, float y0, size_t k) {
    const size_t total = 2 * points.size();
    size_t left = 0, right = total - 1;

    while (left <= right) {
        // 随机选基准值
        size_t pivot_idx = left + rand() % (right - left + 1);
        float pivot_val = getMappedValue(points[pivot_idx/2], s, x0, y0, pivot_idx%2);
        
        // 分区：把小于等于基准值的移到左边
        size_t store_idx = left;
        for (size_t i = left; i < right; ++i) {
            float val = getMappedValue(points[i/2], s, x0, y0, i%2);
            if (val <= pivot_val) {
                // 交换虚拟索引的位置（仅用临时变量记录，无内存分配）
                std::swap(left + (store_idx - left), left + (i - left));
                store_idx++;
            }
        }
        // 把基准值放到正确位置
        std::swap(left + (store_idx - left), left + (right - left));

        if (store_idx == k) {
            return pivot_val;
        } else if (store_idx < k) {
            left = store_idx + 1;
        } else {
            right = store_idx - 1;
        }
    }
    return 0.0f; // 理论不会执行到此处
}

float calcInitialVal(const myType::ptr_vector<customStruct>& points) {
    float s = 3;
    float x0 = 5;
    float y0 = 1.5;
    size_t numPoints = points.size();
    return quickSelect(points, s, x0, y0, numPoints);
}

注意事项 #

• 方法1的虚拟迭代器需严格遵循C++随机访问迭代器的规范，才能被std::nth_element正确调用。
• 方法2的实现完全无动态内存分配，但若points规模极大，需注意随机数生成的性能影响，可改用固定基准选择策略。

内容的提问来源于stack exchange，提问作者havakok