Quicker way to insert into list?

Question

I'm having a hard time writing an efficient way to insert a large volume of values into a list, without using maps. The code I have currently looks as follows:

list<pair<int, vector<int>>> myList;

void key_value_sequences::insert(int key, int value){
    for(it=myList.begin(); it!=myList.end(); ++it){
        if(it->first==key){
            it->second.push_back(value);
            return;
        }
    }
    vector<int> v;
    v.push_back(value);
    myList.push_back(make_pair(key, v));
    myList.sort();
    return;
};

Any help is greatly appreciated.

Looks like you really want a map of some sort. – GManNickG Oct 21 '16 at 03:49 — GManNickG, Oct 21 '16 at 03:49

score 0 · Answer 1 · answered Oct 21 '16 at 03:48

0

You're close; since you appear to have an in-order list, try this:

void key_value_sequences::insert(int key, int value){
    for(it=myList.begin(); it!=myList.end(); ++it){
        if(it->first==key){
            it->second.push_back(value);
            return;
        }
        else if (it->first > key) // Or <, depending on order
        {
            vector<int> v;
            v.push_back(value);
            myList.insert(it, make_pair(key, v));
            return;
        }
    }
    vector<int> v;
    v.push_back(value);
    myList.push_back(make_pair(key, v));
}

Basically, once you go one past the key, insert the new entry, or if you get to the end, you've got the largest key, so push it to the back. Thus you can keep the list sorted.

answered Oct 21 '16 at 03:48

Ken Y-N

14,644
21
71
114

looks like this still runs in linear time, but am shooting more for constant – Gman Oct 21 '16 at 03:59
As mentioned in another comment, for **O(1)** rather than **O(N)** you would need either an `std::map` (**O(logN)**?) or a hash table, **O(1)** without collisions. Your original version does **N + N log N** comparisons, I think, for a new element and this does an average of **N / 2**. – Ken Y-N Oct 21 '16 at 04:04
Is there a somewhat simple way to change this to a hash table without throwing it all away? – Gman Oct 21 '16 at 04:08
[`std::map`](http://en.cppreference.com/w/cpp/container/map) is sorted, so it might be a simple drop-in replacement. – Ken Y-N Oct 21 '16 at 04:11
Unfortunately I cannot use map, as the only headers I am working with are list, vector, and algorithm – Gman Oct 21 '16 at 04:24
@Gman A simple hash table can be made from a `vector>` Since `TYPE` is `int`, the hashing algorithm could be something simple like `value%myList.size()`. The list handles collisions. – user4581301 Oct 21 '16 at 05:36
@Gman My example is crack. I outlined a set, not a hash table in that comment. I'll post a better one in a few minutes. – user4581301 Oct 21 '16 at 20:56

score 0 · Answer 2 · edited May 23 '17 at 10:29

A simple hash table using a vector and a list.

The vector contains a list of collided keys. A smart hash table will adjust it's size and rehash to minimize collisions. This is not a smart hash table.

The vector is used as the outer container because it has much faster iteration. There is a string case for the inner container also being a vector because lists... they kinda suck unless you add and remove more than you iterate. I'll let the big man himself explain.

#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <stdexcept>

class poor_mans_hash
{
    std::vector<std::list<std::pair<int,int>>> hash_table;

    int hash(int val)
    {
        return abs(val%static_cast<int>(hash_table.size()));
        // abs because a negative number makes a very explosive vector index
    }
public:
    poor_mans_hash(int size): hash_table(size)
    {
        // all work done in member initialization list
    }

    void insert(int key,
                int val)
    {
        // get list for correct element
        std::list<std::pair<int,int>> &collisionlist = hash_table[hash(key)];

        // see if key is in list
        for (std::pair<int,int> &test: collisionlist)
        {
            if (key == test.first)
            {
                test.second = val; // update existing
                return;
            }
        }
        // key not found. Add it.
        collisionlist.push_back(std::pair<int,int>(key, val));
    }

    bool find(int key)
    {
        for (std::pair<int,int> &test: hash_table[hash(key)])
        {
            if (key == test.first)
            {
                return true;
            }
        }
        return false;
    }

    int & get(int key)
    {
        for (std::pair<int,int> &test: hash_table[hash(key)])
        {
            if (key == test.first)
            {
                // found key. Return value
                return test.second;
            }
        }

        // Not found. 
        throw std::out_of_range("No such key");
    }
};

int main()
{
    poor_mans_hash test(50);

    test.insert(1, 1);
    std::cout << "1: " << test.get(1) << std::endl;
    try
    {
        std::cout << test.get(51) << std::endl;
    }
    catch (std::out_of_range &e)
    {
        std::cout << "could not get 51: " << e.what() << std::endl;
    }
    test.insert(11, 11);
    test.insert(21, 21);
    test.insert(51, 51);
    std::cout << "1: " << test.get(1) << std::endl;
    std::cout << "51: " << test.get(51) << std::endl;
    test.insert(1, 2);
    std::cout << "1: " << test.get(1) << std::endl;

}

Possible improvements to this are many. Rehashing and smarter organizing, for one thing. For another, here's a write up on all the fun things you can do to make this a good, library-like container Writing your own STL Container

Quicker way to insert into list?

2 Answers2