Insert invalidate iterators

[boukhelef]

According to the C++ standard, all Associative Containers: The insert and emplace members shall not affect the validity of iterators and references to the container [26.2.6/9]. However I found that after insertion of of a list of element, some iterator values are invalidated.

Please find bellow code snippet to test this feature:

namespace xxx { typedef std::string key_t; typedef std::string value_t;

typedef ska::flat_hash_map<key_t, value_t> map_t;
//typedef std::map<key_t, value_t> map_t;
typedef std::list<map_t::iterator> list_t;

} ... std::vector keys(MAX_SIZE__); generatKeys(keys); ... for (auto& key : keys) { std::pair < xxx::map_t::iterator, bool> ret = dict.insert(xxx::map_t::value_type(key, keys[rand() % MAX_SIZE__]));

        if (ret.second) {
            list_items.push_back(ret.first);
        }
    }

    for (xxx::map_t::iterator iter = dict.begin(); iter != dict.end(); ++iter) {

        xxx::list_t::iterator findIter = std::find(list_items.begin(), list_items.end(), iter);

        if(findIter == list_items.end()) {
            cerr << "Item does not exist\n";
        } else {
            cerr << "Item exists\n";
        }
    }

[boukhelef]

When using it against std::map, everything is fine!

[max0x7ba]

While this container has an interface similar to C++ standard associative container, this container is not a part of the C++ standard library, hence those requirements do not apply.

It is unfortunate for the C++ standard that those requirements do not allow for fast associative containers with open addressing.

[pps83]

@boukhelef flat (hash) maps may invalidate iterators: that's the point of flat part: once you need to resize, you'll have to move your data.