2
\$\begingroup\$

The main problem that I tried to tackle here was trying not to have the erase method to be \$O(n)\$. I kept two data structures: a linked-list of pairs and a map of a key and a pair containing a value and a pointer that points to the node in the linked-list.

Am I on the right track? Right now the code is all rough, ugly and all over the place but I tested it and it works properly.

#include <iostream>
#include <list>
#include <map>
#include <string>

using std::cout;
using std::endl;

template <typename key, typename value>
class table {
    using node = std::pair<key, value>;
    using iterator = typename std::list<std::pair<key, value>>::iterator;
    using value_node = std::pair<value, iterator>;

    std::list<node> list;
    std::map<key, value_node> data;

public:
    table & push(key const & k, value const & v) {
        list.emplace_back(k, v);
        data.emplace(k, value_node {v, std::prev(std::end(list))});
        return *this;
    }

    iterator begin() {
        return std::begin(list);
    }

    iterator end() {
        return std::end(list);
    }

    table & erase(key const & k) {
        list.erase(data[k].second);
        data.erase(k);
        return *this;
    }

    // Just to check if the list items are actually being erased.
    size_t length() const {
        return list.size();
    }

    value & operator [](key const & k) {
        return data[k].first;
    }
};

int main() {

    table<std::string, std::string> t;

    t.push("hello", "world");
    t.push("blabla", "hello");

    cout << t["hello"] << endl;
    cout << t["blabla"] << endl;
    cout << t.length() << endl;

    for (auto const & e : t) {
        cout << e.first << " " << e.second << endl;
    }

    t.erase("hello");
    t.erase("blabla");
    cout << t.length() << endl;

    cout << "Size: " << sizeof(table<int, int>) << endl;

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Is there a reason an unordered_map wouldn't do the same job? \$\endgroup\$ – tinstaafl Jan 19 '17 at 2:28
  • \$\begingroup\$ The idea is to keep the order of insertion. So when you iterate, you iterate the elements by the order that you've inserted them. Also, one of the challenges was to make the erase method fast because of the linked list. The unordered_map uses a hash function that randomizes the order of the elements and the map sorts them using <; none of them keeps the order of insertion. \$\endgroup\$ – João Pires Jan 19 '17 at 2:33
  • \$\begingroup\$ If item is not inserted, then data[k] is erroneous call, therefore your erase function is wrong. You should to use std::map::at and get exception or std::map::find and compare its result against std::end(data), then in case of failure is is better to return bool(false) instead of *this. \$\endgroup\$ – Tomilov Anatoliy Jan 19 '17 at 18:17
  • \$\begingroup\$ You don't need to duplicate neither key nor value at all. 1st option is to use std::map< std::reference_wrapper< key const >, iterator const, std::less< key > > instead of your highly expensive way. Another approach is to use std::set< iterator > and use your custom comparator. It just adds one level of indirection in operator [] and others (it is cheap). Also it is better to use iterator const it = list.insert(std::cend(list), {k, v}); instead of ad-hoc std::prev(std::end(list)) in both cases. insert is more universal way of adding an elements to containers. \$\endgroup\$ – Tomilov Anatoliy Jan 19 '17 at 18:18
  • \$\begingroup\$ @Orient Thanks, I've changed the code and now it's much much better. (I still haven't updated it here) I am, however, interested in your approach std::reference_wrapper< key const >, iterator const, std::less< key > >, could you please explain it a bit better? Are you saying that I should make the map key and value a reference to the first and second element of the list pair? And I'm a still bit confused by your idea of using the set, since my map already has a "reference" to the iterator. iterator const it = list.insert(std::cend(list), {k, v}); was a nice one ;) \$\endgroup\$ – João Pires Jan 21 '17 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.