C++ list with fast find

user_11608725 0
Viewed 986

Im working with a std::list.

Elements appear in "order of insertion" into the list, not according to the value of an element.

When std::find()-ing an element, the whole list must be searched.

In order to speed up "finding" from O(n) to O(log(n)) I could myself implement a hash-map to store the std::list elements positions, or I could use boost Multi Indexes, https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookup.

Question: Today, with C++17, is there a standard/common or a best-practices way of implementing a container that have all the properties of a list PLUS fast find (and, eg. remove)? Or, does such a container type already exist? C++20 perhaps?

Edit/Nb: The order of the elements in the list is relevant and thus a std::map can not directly be used.

c++17 std containers list c++
3 Answers

Since iterators for a std::list remain valid across inserts and deletes (except for the element you deleted, of course), you could maintain a secondaray data structure of type std::map <my_key, my_list_iterator> (or a std::unordered_map if that is more suitable).

Then, whenever you add or delete a list entry, do the same thing to your std::map / unordered_map and you're done. You can, of course, search that with O(log(n)) (or O(1)) complexity.

user_57432880

A partial and VERY primitive (prototype) implementation of the present answer https://stackoverflow.com/a/64539693/11608725 (by Paul Sanders):

 #include <unordered_map>
 #include <list>
 #include <iterator>
 #include <iostream>

 using std::unordered_map;
 using std::list;
 using std::make_pair;
 using std::begin;
 using std::end;
 using std::prev;
 using std::cout;

 template <typename T>
 struct fastlist {
    list<T> l;
    unordered_map<T, typename list<T>::iterator> m;
     
    void push_front(T e) {
        l.push_front(e);
        m.insert(make_pair(e, begin(l)));
    }

    void push_back(T e) {
        l.push_back(e);
        m.insert(make_pair(e, prev(end(l))));
    }

    auto find(T e) {
        return m[e];
    }

    void remove(T e) {
        auto it = m[e];
        m.erase(*it);
        l.erase(it);
    }
};

int main() {          // Giving it a spin
    fastlist<int> f;

    f.push_back(3);
    f.push_back(4);
    f.push_back(5);
    f.push_front(2);
    f.push_front(1);
    f.remove(3);
    f.remove(5);
    f.remove(1); 
    f.push_back(200); 
    f.push_front(-100);
    cout << *f.find(4);
}

demo: https://godbolt.org/z/jdnvdM

Among many other things, this prototype is missing iterator methods to implement a custom container, info on this here: How to implement an STL-style iterator and avoid common pitfalls?.

(Edit: Ted Lyngmo in his comment below provides a better version here: https://godbolt.org/z/6xfbq7).

It really would be neat if this kind of container would be provided out-of-the box. As well as other containers that are modelled on/derived from more fundamental ones, but add specific performance advantages reflecting specific usage situations. If anybody knows of any library that provides that kind of specialized containers, please tell;-)

user_116087250
user_116087250
Related