3

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.

11
  • 3
    Why not std::map?
    – IS4
    Oct 26, 2020 at 14:05
  • 3
    Pretty hard to do a O(log n) search on a sequence that doesn't have random access. Oct 26, 2020 at 14:06
  • @IllidanS4supportsMonica because i need the order in which elements were inserted to be preserved.
    – mrchance
    Oct 26, 2020 at 14:06
  • 1
    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. Oct 26, 2020 at 14:29
  • 2
    "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, 2020 at 14:33

3 Answers 3

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.

1
  • 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, 2020 at 15:07
0

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

0

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

5
  • 2
    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<T>::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 but if you change the value of an entry in the list, it'll be broken.
    – Ted Lyngmo
    Oct 27, 2020 at 10:31
  • 1
    @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, 2020 at 10:50
  • @TedLyngmo btw, your 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, 2020 at 11:12
  • 1
    :-) Thanks but I think I'll lean on boost if I ever need a container with these capabilities.
    – Ted Lyngmo
    Oct 27, 2020 at 11:15
  • 1
    @TedLyngmo yeah, certainly, Ive added this stackoverflow answer above stackoverflow.com/a/39510606/11608725 to give a practical example of how to use Boost MultiIndex
    – mrchance
    Oct 27, 2020 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.