C++ list with fast find

Question

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.

Pretty hard to do a O(log n) search on a sequence that doesn't have random access. — Fred Larson, Oct 26 '20 at 14:06
@IllidanS4supportsMonica because i need the order in which elements were inserted to be preserved. — mrchance, Oct 26 '20 at 14:06
Not sure of best-practices, but rather than try to add lookup to a list, I'd try to add next/previous functionality to an unordered hash set. — aschepler, Oct 26 '20 at 14:07
Yes, use boost multi-index if you don't want to reinvent the wheel. — Eugene, Oct 26 '20 at 14:09
Searching a `std::vector` should offer significant performance benefits over a `std::list` because of better cache locality. Since you are only adding at the end, there's no significant cost to this, unless you do [a lot of] deletes in the middle of the vector. — Paul Sanders, Oct 26 '20 at 14:29
"_all the properties of a list_" - Are you sure that you need all the properties of a `std::list`? If not, @PaulSanders has a good point. — Ted Lyngmo, Oct 26 '20 at 14:33
@PaulSanders yeah I need to remove elements from anywhere in the list:-| Basically Im implementing a queue where elements may drop out from anywhere... — mrchance, Oct 26 '20 at 14:44
Chances are vector will still be way faster, if your list doesnt have a bigillion elements — Yamahari, Oct 26 '20 at 20:10
@FredLarson, that's exactly what binary, AVL and RB trees do. It's not so hard. — Elliott, Oct 27 '20 at 07:16

Paul Sanders · Accepted Answer · 2020-10-27T09:19:45.273

5

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.

edited Oct 27 '20 at 09:19

answered Oct 26 '20 at 15:03

Paul Sanders

24,133
4
26
48

thx, this was what I was thinking to do, but it occurred to me that this kind of need would be sufficiently common for there to exists a ready-made standard container. I will accept your answer, since i gather that it answers my question: what is the/a "standard" way of doing this. I will then implement this simultaneous bookkeeping in a class offering encapsulation and single-point-of-access. Thanks! – mrchance Oct 26 '20 at 15:07

mrchance · Answer 2 · 2020-10-28T11:57:39.193

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;-)

There are some things that must be changed. Your `find()` will create a map entry if the element isn't present and return a default constructed `list::iterator`.The `list` supports inserting duplicates but the map doesn't. Insert two and remove one and then you'll have a list with one entry while the map is empty. If you `find` and element and change the value, the corresponding change won't be made in the map. I made a few adjustments [here](https://godbolt.org/z/6xfbq7) but if you change the value of an entry in the list, it'll be broken. — Ted Lyngmo, Oct 27 '20 at 10:31
@TedLyngmo Thanks! I will let the "example" stand like it is, but anyone wanting to modify it are of course more than wellcome. I also think I will not embark on making a complete container myself since I dont feel confident that I will be able to make it totally robust + complete + generic + fast. I will be looking out for somebody else's solution and/or some proprietary/professional grade (but free) container. Thx! — mrchance, Oct 27 '20 at 10:50
@TedLyngmo btw, your https://godbolt.org/z/6xfbq7 is quite neat!! maybe you are not far away from becoming that implementer of a professional-release-grade "index_list" container? nudge nudge, i encourage you;-) thx! — mrchance, Oct 27 '20 at 11:12
:-) Thanks but I think I'll lean on boost if I ever need a container with these capabilities. — Ted Lyngmo, Oct 27 '20 at 11:15
@TedLyngmo yeah, certainly, Ive added this stackoverflow answer above https://stackoverflow.com/a/39510606/11608725 to give a practical example of how to use Boost MultiIndex — mrchance, Oct 27 '20 at 11:39

score 0 · Answer 3 · answered Oct 27 '20 at 11:37

Very short and understandable guide (based on a single example) on how to implement a container with the desired capabilities using Boost MultiIndex https://stackoverflow.com/a/39510606/11608725

It is more hands-on, to me, easier to understand, than the more formal-styled https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookup that covers every possible use (albeit it also uses examples).

C++ list with fast find

3 Answers3