hvec_map::insert has a non-standard behavior

[asl]

hvec_map::insert looks like this:

    std::pair<iterator, bool> insert(const value_type &v) {
        bool new_key = false;
        size_t idx = hv_insert(&v.first);
        if (idx >= data.size()) {
            idx = data.size();
            data.push_back(v);
            new_key = true;
        } else {
            if ((new_key = erased[idx])) {
                erased[idx] = 0;
                const_cast<KEY &>(data[idx].first) = v.first;
                data[idx].second = v.second;
            } else {
                data[idx].second = v.second;
            }
        }
        return std::make_pair(iterator(*this, idx), new_key);
    }

Note that regardless whether element existed in the map or not, value is replaced. The bool result indicates whether the key was replaced and this is non-standard as well. Normally we expect from map inserts: a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool value set to true if and only if the insertion took place.

Such behavior could lead to very subtle bugs in common pattern insert-or-merge, e.g.:

hvec_map<key, value> m;
auto [it, inserted] = m.insert({something, something_else});
if (!inserted)
 merge(it->second, something_else);

hvec_map::emplace has the same problem.

[asl]

Tagging @ChrisDodd

I think the else in if ((new_key = erased[idx])) { should be removed to fix the issue. We cannot override value for non-erased entries.

[ChrisDodd]

Fixed by #4458