A custom associative container that is faster than std::map

[scarface382]

It uses stl heavily and is faster than maps by about 15%.
(I know that the number seems vague but showing my test results would be too long for this post.)

Some features:
operator[] creates a key if it doesn't already exist.
find(key_value) returns an iterator with which you can unbox the map-second value
ex:

map_vec<int, string> somemap;
string somestring = somemap.unbox(somemap.find(int));

#include <algorithm>
#include <vector>

//Esad Akar March 2016

using namespace std;

template <class first, class second>
class map_vec
{
public:
    typedef typename vector<first>::iterator iterator;

    second& operator[](const first& key)
    {
        iterator it;

        if (( it = lower_bound(keyList.begin(), keyList.end(), key)) != keyList.end() && *it == key)
            return data[keyPos[it-keyList.begin()]];

        else {
            data.push_back(second());

            int pos = it - keyList.begin();
            keyList.insert(it, key);
            keyPos.insert(keyPos.begin() + pos, data.size()-1);

            return data.back();
        }
    }

    second& unbox(const iterator& key_it) { return data[keyPos[key_it-keyList.begin()]]; }
    iterator find(const first& key) { return lower_bound(keyList.begin(), keyList.end(), key); }

    iterator begin() { return keyList.begin(); }
    iterator end() { return keyList.end(); }

    void clear() { keyList.clear(); data.clear(); keyPos.clear(); }

    void reserve(const int& size) { keyList.reserve(size); data.reserve(size); keyPos.reserve(size); }

private:
    vector<first>  keyList;
    vector<second> data;
    vector<int> keyPos;
};

ENJOY!
P.S I have used map_vec in some real scenarios and I quickly became impressed with its simplicity so I thought maybe I'd share it with people.

[Peter87]

Have you compared your map_vec to std::unordered_map? One thing I noticed is that your map_vec takes much longer time to insert the elements compared to std::map and std::unordered_map.

[scarface382]

Insertion and reading is faster than std::map. This container keeps keys vector sorted for use of lower_bound or else it would be uselessly slow. It, however, does not attempt to sort to second paring and I believe that is where it gets it speed from. This is written with the assumption that key or ->first is smaller in data size compared to ->second. Also this container shines where the container size becomes very large
ex:

void test_map(int sort)
{
    Stopwatch stopwatch;
    map<string, vector<string> > bank;
    bank.get_allocator().allocate(17576);

    vector<string> words;
    words.reserve(17576);

    string x;
    x.resize(3);

    if (sort == 1) {
        cout << "TEST MAP -SORTED" << endl;
        for(char a='a'; a < 'z'+1; ++a)
            for(char b='a'; b < 'z'+1; ++b)
                for(char c='a'; c < 'z'+1; ++c) {
                    x[0] = a; x[1]=b; x[2]=c;
                    words.push_back(x);
                }
    }
    else {
        cout << "TEST MAP -WORSE" << endl;
        for(char a='z'; a > 'a'-1; --a)
            for(char b='z'; b > 'a'-1; --b)
            for(char c='z'; c > 'a'-1; --c) {
                x[0] = a; x[1]=b; x[2]=c;
                words.push_back(x);
            }
    }

    stopwatch.on();
    for(int i=0; i < 17576; ++i)
        for(int j=0; j < 3000; ++j)
            bank[words[i]].push_back(words[j]);
    cout << stopwatch.now() << endl;

    stopwatch.on();
    for(int i=0; i < 17576; ++i)
        for(int j=0; j < 3000; ++j)
            x = bank.find(words[i])->second[j];
    cout << stopwatch.now() << endl;
}

void test_map_vec(int sort)
{

    Stopwatch stopwatch;
    map_vec<string, vector<string> > bank;
    bank.reserve(17576);

    vector<string> words;
    words.reserve(17576);

    string x;
    x.resize(3);

    if (sort == 1) {
        cout << "TEST VEC -SORTED" << endl;
        for(char a='a'; a < 'z'+1; ++a)
            for(char b='a'; b < 'z'+1; ++b)
                for(char c='a'; c < 'z'+1; ++c) {
                    x[0] = a; x[1]=b; x[2]=c;
                    words.push_back(x);
                }
    }
    else {
        cout << "TEST VEC -WORSE" << endl;
        for(char a='z'; a > 'a'-1; --a)
            for(char b='z'; b > 'a'-1; --b)
            for(char c='z'; c > 'a'-1; --c) {
                x[0] = a; x[1]=b; x[2]=c;
                words.push_back(x);
            }
    }

    stopwatch.on();
    for(int i=0; i < 17576; ++i)
        for(int j=0; j < 3000; ++j)
            bank[words[i]].push_back(words[j]);
    cout << stopwatch.now() << endl;

    stopwatch.on();
    for(int i=0; i < 17576; ++i)
        for(int j=0; j < 3000; ++j)
            x = bank.unbox(bank.find(words[i]))[j];
    cout << stopwatch.now() << endl;
}

int main()
{
    test_map(1);
    test_map_vec(1);
    test_map(2);
    test_map_vec(2);

    test_map_vec(2);
    test_map(2);
    test_map_vec(1);
    test_map(1);
}

here is the code for stopwatch:

class Stopwatch
{
public:
    typedef chrono::high_resolution_clock clock;

    void on() { start = clock::now(); }
    double now()
    {
        chrono::duration<double> elapsed = clock::now() - start;
        return elapsed.count();
    }
private:
    clock::time_point start;
};

* make sure you run this on release mode.

[TheIdeasMan]

Insertion and reading is faster than std::map.

Are you sure about that? Your latest code has O(N*M) complexity for the initialisation of the map. Even though you use the same algorithm to initialise both your container and the std::map, it looks like an unfair test: you are forcing std::map to be initialised with O(N*M) code. It might be different if all the pairs were created first, then pushed into the map.

Consider that the STL containers / algorithms are highly optimised, it's generally not worth it to try to do better. You are trying to optimise std::map, but std::unordered_map is better anyway.

chrono::high_resolution_clock is not the right clock for timing this: the high resolution part might be misleading in terms of you think you are getting something better, but it's a wall clock not a cpu clock. Use std::clock

This container keeps keys vector sorted for use of lower_bound or else it would be uselessly slow.

std::map is often implemented as a BST or a red/black tree, so it will always be sorted. So you have written code that does the same thing. Is your code better than what the std::map does? Is your code to keep it sorted better than putting it all in the vector, then sorting it with std::sort? And more importantly than anything else, as Peter87 says: Is it better than std::unordered_map ? I very much doubt it.

Also consider that there might be more work inserting into a red / black tree (self balancing BST), but that might be better in the long run for certain data sets. The self balancing is probably more efficient in the end than maintaining a sorted vector. Also, inserting into a vector (no matter how one does it) is not going to be good: all the remaining elements have to be moved along 1 position. So that is why insertion in the middle of a vector is O(n).

Edit:

It, however, does not attempt to sort to second paring and I believe that is where it gets it speed from.

std::map doesn't do that either. In (key, value) the value is a value. But your value is a vector, why should a container presume that the vector needs to be sorted?
end Edit

Also this container shines where the container size becomes very large

What size did you test it with? 17576 isn't large, 1 or 10 million might be a better test. And your strings only have 3 char.

Sorry to pour really cold water all over your idea, hopefully it is helpful in the end :+)

[TheIdeasMan]

Some more thoughts:

If one puts sorted data into a BST, it is a worst case scenario because each node only has a right child, so we have a big list going diagonally to the right. On an ordinary BST, a find operation now takes O(n) time, as opposed to O(log n) time. For a red black tree (a fair guess as to how std::map might be implemented) which does balancing, this would be quite a bit of work to reorganise. So that may be where your 15% difference comes from. Similar idea for reverse sorted data, so both scenario's are now worst case.

With std::map<A,B> the compiler doesn't care what B is, they are just values. It probably just stores a pointer to it. All it is really interested in is storing all the A's (the keys) in a sorted fashion. The fact that your B is a std::vector<std::string> is irrelevant.

[scarface382]

I appreciate the lengthy responses.

"Consider that the STL containers / algorithms are highly optimised, it's generally not worth it to try to do better. "
Sure, they are but this attitude is terrible I think.

Maps are known to be notoriously slow because they are based on linked lists so my first instinct was to translate it to a vectors version.

"Sorry to pour really cold water all over your idea, hopefully it is helpful in the end."
This is also not a idea, I have used it in a project where I could not get good performance from maps so I set out to create my own and I succeeded. Sample size is insignificant in my case because the project I used it in did not pass 2000 objects.

But I do agree with you that if the objects being inserted into the container are in descending order, then you're gonna have a terrible time :).

[TheIdeasMan]

Hi,

Sure, they are but this attitude is terrible I think.

Consider who are the people that design and write these containers, do you really think you can do better than them ? I am not saying you shouldn't pursue new ideas. If no one tried anything new the world would go nowhere. But I am almost certain you won't come up with something better than what is in the STL already.

Maps are known to be notoriously slow because they are based on linked lists so my first instinct was to translate it to a vectors version.

Disagree, maps are usually Binary Sort Tree, or a variation of BST, the Red / Black tree.

http://en.cppreference.com/w/cpp/container/map

cppreference wrote:

std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.

Consider that maintaining a vector in a sorted state is an expensive thing to do, given that new objects are always being added. Sorting is expensive, even once - never mind multiple times. Insertion that isn't at either end is expensive: it's linear in distance to the end.

Again, consider std::unordered_map, it is a very efficient container. It uses buckets with hash functions to determine which bucket something is in.

This is also not a idea, I have used it in a project where I could not get good performance from maps so I set out to create my own and I succeeded.

With the way you timed your code, I have doubts about whether the map was slower, and whether your vector was faster. Therefore I have doubts about whether it was a success. I hope you understand why a wall clock is no good for timing code. And how you time the algorithm is important too.

Sample size is insignificant in my case because the project I used it in did not pass 2000 objects.

With such a small amount of objects, it is very difficult to compare anything. With your other code, you had 17,000 odd objects - this is also small. See what happens when you have 1, 10 or 100 million objects.

But I do agree with you that if the objects being inserted into the container are in descending order, then you're gonna have a terrible time :).

With a std::map, it will be a terrible time when it is sorted in ascending order too.

[coder777]

Whether a container has a speed issue depends on what it is designed for and how it is used.

std::map is slow in regard of inserting/removing, but pretty fast when accessing.

With unordered_map I honestly don't like the hash mechanism.

So a associative container with improved modifying speed and good enough access speed is ok.

@scarface382

line 25/26: you insert a value twice in a vector which seems not that effective perfomance wise.

[dhayden]

I'm sorry to say this, but in my experience, sorted vectors are a really bad idea. It takes forever to insert into them and it takes forever to delete from them. For example, this test takes 39.45 seconds of CPU time on my computer and and 500000 items:

int main(int argc, char **argv)
{
    unsigned N = atoi(argv[1]);
    map_vec<int, int> theMap;

    for (unsigned i = 0; i < N; ++i) {
        int key = rand();
        int val = rand();
        theMap[key] = val;
    }
    return 0;
}

Changing it to use map instead of map_vec, it takes 0.717 seconds.

consider std::unordered_map, it is a very efficient container.

Hash tables are wonderful but they too have their quirks:

It's critical to keep the load_factor (items per bucket) reasonably low. In my experience, you can often know ahead of time about how many items will go in the collection so you can create it with the right number of buckets. If you fill the container before doing accesses, you can just fill the container using the default buckets, and then change the load factor to what you want. This causes a rehash, but it only happens once.

Hash tables are NOT a good choice when the hash data is relatively large. Consider, for example, a table of strings that average 1k in size. To hash a string, you must read the entire string. In contrast, to compare two strings, you only have to read the initial unique characters.

And of course the hash function is very important.

Really all of this boils down to a simple concept: when selecting a container class, you have to analyze how the container will be used and then select an appropriate container for the usage. Scarface382 has used map_vec<> successfully and there are certainly use cases where it will perform wonderfully.

In fact, I'll go out on a limb and say that about 80% of what's useful in computer science education is the performance of various data structures (aka containers). You could summarize it on a single sheet of paper.