which datastructure or stl to be used to save a pair with a value?

Question

I have a data like

**"London","Paris" -> 10
"New York","Japan" -> 100
"London","Japan" -> 200**
..

How to save pair with value using STL? As Map only allow key and value, not extra key.

I can save key with extra object which will hold the 2 values.

 map < string, Object>

But then i have to go through an extra step of parsing the object and it will be an overhead.

Even i can do my work using linked list. But is there any other efficient way to save it and access it? Or i am thinking in correct direction? I am new to STL.

@M.M trivial as it may seem to experienced users of the STL, it's not obvious to beginners that std::pair<> is comparable. This should be an answer — Richard Hodges, Apr 18 '16 at 06:37
@RichardHodges I couldn't remember either TBH, but if someone responded saying it wasn't, I was going to suggest how to make a custom comparator — M.M, Apr 18 '16 at 06:45
Since you are new to STL, it would be worth learning how to have custom Keys in associative containers. http://stackoverflow.com/questions/906244/custom-types-as-key-for-a-map-c — sameerkn, Apr 18 '16 at 06:48

score 4 · Accepted Answer · edited May 23 '17 at 12:07

4

You can use either an std::map (as noted by M. M.) or an std::unordered_map of std::pair<std::string, std::string>s to ints.

The std::map is easy - simply use std::map<std::pair<std::string, std::string>, int>. The standard library already knows how to compare pairs.

If you don't need ordering, though, you might be better off with a hash-based dictionary. Borrowing from this question, first define this:

struct pairhash {
public:
    template <typename T, typename U>
    std::size_t operator()(const std::pair<T, U> &x) const
    {
        return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
    }
};

(see comment below by Tony D for an even better version.)

Now you can use std::unordered_map<std::pair<std::string, std::string>, int, pairhash>.

Be sure to include the appropriate headers, also (e.g., <map> and <unordered_map>, respectively). For the unordered version, you should also make sure you're building in c++11 settings.

edited May 23 '17 at 12:07

Community

1
1

answered Apr 18 '16 at 06:45

Ami Tavory

74,578
11
141
185

Thanks. I think as answered by M.M and you, will work for me. i need to scratch more my head towards STL. But, i got my directions where to move ahead. – Vishwadeep Singh Apr 18 '16 at 07:11
2

`std::hash()(x.first) ^ std::hash()(x.second);` is awfully collision prone - every `pair` where `first == second` will hash to 0, and every pair `(a, b)` will collide with `(b, a)`. Those circumstances may not apply to the OP's data, but in general - if stopping short of `boost::hash_combine` - even `std::hash()(x.first) ^ (std::hash()(x.second) << 3) ^ (std::hash()(x.second) >> 2);` is *much* better. – Tony Delroy Apr 18 '16 at 07:26
@TonyD Many thanks - updated to reference your comment. – Ami Tavory Apr 18 '16 at 07:31

which datastructure or stl to be used to save a pair with a value?

1 Answers1