C++ Performing mapping between vectors and unique numbers and vice versa

Question

I need to create a dictionary data structure which maps vector to unique numbers and vice versa:

For example for mapping vectors to unique numbers, I can do the following:

   vector   ---------> unique number
   (0,7,8)                   0
   (0,8,10)                  1
   (1,2,9)                   2
   (1,2,10)                  3
   (1,3,1)                   4

Then I need to map back unique numbers to vectors, e.g. given below:

   unique numbers --------> vector   
   0                        (0,7,8)    
   1                        (0,8,10)   
   2                        (1,2,9)    
   3                        (1,2,10)   
   4                        (1,3,1)

I tried to do this mapping by creating a structure of integers and vectors -- however, this turned to be very inefficient. Is there some c++ data structure which can perform the forward and reverse mapping efficiently.

Are the vectors sorted (in their unique-number ordering), or is it just a coincidence they're sorted in your example? If they are, the unique numbers are continuous, and you're not dynamically changing the data as you're indexing it, then you can store a `vectors>` and use the outer-vector's index as your unique number, and use the binary search algorithm to lookup an inner-vector's unique number == outer-index. — Tony Delroy, Jul 01 '15 at 04:15
@TonyD Yes the vectors are sorted. I think what you are suggesting can work great. Can you please explain it with the help of an example — Steg Verner, Jul 01 '15 at 04:23

score 2 · Answer 1 · answered Jul 01 '15 at 04:08

2

boost::bimap has the same functionality as what you're describing.

It is similar to std::map, but allows either element of the pair to be a key to the other element.

answered Jul 01 '15 at 04:08

Drew Dormann

59,987
13
123
180

score 1 · Answer 2 · edited May 23 '17 at 11:58

1

There is Boost.Bimap. This is a related question to Bimap Is there a Boost.Bimap alternative in c++11? .

In short, you can have two maps, one for each relationship (id -> vec, vec -> id).

edited May 23 '17 at 11:58

Community

1
1

answered Jul 01 '15 at 04:15

user2922709

67
4

score 0 · Answer 3 · answered Jul 01 '15 at 05:25

[example as requested in a comment under the question]

Summarily, this makes the array index in the sorted ordering the "unique number" identifying a specific vector<int>, and seeks a specific vector<int> using std::lower_bound. Effectively, get_vec_id is just a convenience function if you find dealing in vector indices (with (size_t)-1 being a "not-found" sentinel value) more intuitive than repeatedly using lower_bound directly and dealing with iterators.

This is not very convenient when you have insert and/or erase of vector<int>s interspersed with lookups, because 1) earlier-retrieved indices are all invalidated, and 2) inserting and erasing in vectors is O(n). But, it's pretty good when the data's prepared first then a multitude of lookups are done.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

template <typename Data>
size_t get_vec_id(const Data& data, const typename Data::value_type& value)
{
    auto it = std::lower_bound(data.begin(), data.end(), value);
    if (it != data.end() && *it == value)
        return it - data.begin();
    else
        return (size_t)-1;
}

int main()
{
    std::vector<std::vector<int>> data =
        { { 0,7,8 },
          { 0,8,10 },
          { 1,2,9 },
          { 1,2,10 },
          { 1,3,1 } };

    std::cout << get_vec_id(data, {0, 7}) << '\n';
    std::cout << get_vec_id(data, {0, 7, 8}) << '\n';
    std::cout << get_vec_id(data, {0, 7, 9}) << '\n';
    std::cout << get_vec_id(data, {1, 2, 9}) << '\n';
    std::cout << get_vec_id(data, {1, 2, 11}) << '\n';
    std::cout << get_vec_id(data, {1, 3, 1}) << '\n';
    std::cout << get_vec_id(data, {1, 4, 1}) << '\n';

    // to map from a "vec_id" to a vector, use data[vec_id]...
}

C++ Performing mapping between vectors and unique numbers and vice versa

3 Answers3