Create an indexed ordered map

I looked here and similar sites for the past few days and spent many hours trying to come up with a solution and would like to ask for advice.

I came to the disappointing conclusion that without going into boost libraries for C ++, there is no way to create an associative container that preserves indexed order.

More clearly and specifically, what I need is a map that can search using the [key] operator, but is also indexed in order items added for iteration purposes.

I decided that this morning I would need to write one myself, and I tried several approaches using map cards and pair vectors, etc. But nothing really worked and getting all the functionality I am looking for is surprisingly not easily achievable in this language. Must be wrong? Has anyone else had experience with this functionality or is familiar with this concept that could point me in the right direction of what I'm looking for?

Thank you very much in advance! Happy new year everyone.

+4
source share
1 answer

Warning: this is a crude manner of very desired behavior. This is not anywhere near good code, but it is quick and should demonstrate a technique for this.

, Boost multi_index, . , , .

template<typename Key, typename Val>
class OrderedMap
{
private:
    std::vector<std::pair<Key, Val>> ordered;
    std::map<Key, std::size_t> lookup;

public:
    void insert(Key k, Val v)
    {
        ordered.push_back(std::pair<Key, Val>(k, v));
        lookup.emplace(k, ordered.size() - 1);
    }

    Val find(Key k)
    {
        std::size_t index = lookup[k];
        return ordered[index].second;
    }
    // "typename" needed as the "iterator" is a dependent type
    typename std::vector<std::pair<Key, Val>>::iterator begin()
    {
        return ordered.begin();
    }
    typename std::vector<std::pair<Key, Val>>::iterator end()
    {
        return ordered.end();
    }
};

, , std::vector<std::pair<Key, Val>>, std::map<Key, std::size_t>, . , , /.

, , , - , .


. .

OrderedMap<std::string, int> m;
m.insert("1", 1);
m.insert("2", 2);
m.insert("3", 3);

std::cout << m.find("2") << std::endl << std::endl;

for (auto i = m.begin(); i != m.end(); i++)
    std::cout << i->first << " " << i->second << std::endl;
std::cout << std::endl;

:

2

1 1
2 2
3 3
0

Source: https://habr.com/ru/post/1691556/


All Articles