How does a vector as a key works internally in C++?

Question

This SO answers says that STL Map with a Vector for the Key the vector can be used as a key. So when we use a vector as a key. How does that actually work since the key needs to be unique so when we insert another vector with the same elements will the map check for duplicate element by element or the name of the vector does specify something? Like the name of the array represents the base address. So an array can be used as a key since the base address can be used as a key in this case but what is the key in case of a vector. How does it work internally.

Because when I print the name of the vector, I do get an error

vector<int> v;
cout<<v; //error

`has operators == and <` how does that help? my question was to check duplicate elements will map compare the vector key element by element — , Feb 17 '20 at 10:34
@Bart I just want to know how does map interprets avector as key — , Feb 17 '20 at 10:35
@PulkitBhatnagar Same as any other keys — it compares them by `operator<` (unless you provide your own comparator or a specialization of `std::less`). For vectors, this results in a [lexicographical comparison](https://en.cppreference.com/w/cpp/container/vector/operator_cmp). — Daniel Langr, Feb 17 '20 at 10:37
@PulkitBhatnagar Technically, if both vectors are not of the same size, no elements need to be compared. Otherwise, element-by-element w.r.t. increasing indexes. — Daniel Langr, Feb 17 '20 at 10:39
So why should we ever use vector as a key, cuz you see we use map for constant time storage and retrieval(average) and having a vector as key will again loop through entire element present in the vector. Isn't it absurd — , Feb 17 '20 at 10:39
@PulkitBhatnagar But... No one will ever force you to use `std::vector` as key for `std::map`. *You pay for what you use*. It can be done, and maybe there are some use-cases for that, but most certainly you can change your data structure of choice. STL containers are designed to be maximally versatile and usable in any way user could ever want to use them. — Yksisarvinen, Feb 17 '20 at 10:41
_we use map for constant time storage and retrieval(average)_ — `std::map` doesn't provide that. It's basically a binary tree and therefore has a logarithmic complexity. `std::unordered_map` (hash table) has a constant complexity (provided that the comparison operation has constant complexity as well). — Daniel Langr, Feb 17 '20 at 10:43
@DanielLangr binary tree to resolve collision or it stores the element directly in a binary tree? — , Feb 17 '20 at 10:44
@PulkitBhatnagar See, for example, [Why is std::map implemented as a red-black tree?](https://stackoverflow.com/q/5288320/580083). — Daniel Langr, Feb 17 '20 at 10:46
@PulkitBhatnagar Stores directly. `std::map` will copy both key and value into itself. `std::unordered_map` can store hash of the key. — Yksisarvinen, Feb 17 '20 at 10:46
Guys I have read that unordered_map uses chaning to handle collisions. Why is it so? It can use BST or AVL or RB trees tree too. Why didn't the developers think of that? — , Feb 17 '20 at 10:49
@PulkitBhatnagar You cannot use BST for value types that do not support ordering. For hash tables, you just need a hash function and equality-comparison (not less-than comparison). — Daniel Langr, Feb 17 '20 at 10:59
No no I was talking about collision in case of unordered_map — , Feb 17 '20 at 11:01
@PulkitBhatnagar Me as well. How would you use BST for handling collisions of hash tables, if you don't have a less-than comparion operation available? BTW, hash tables are designed such that the collisions are rare, and if they happen too often, rehashing is applied. Also note that this discussion is off-topic here. You may ask a separate question. — Daniel Langr, Feb 17 '20 at 11:04
Lets say we have an integer for which we want to create our custom unordered map. We hashed it and we got the location in the table where we want it to be stored. Now when next number comes and if it hashes to the same location as the first one why can't we have a AVL trees with the integer number as the key parameter for that location instead of chaining it — , Feb 17 '20 at 11:07
@PulkitBhatnagar Because unordered maps are generic and they don't work just with integers. How would you build such an AVL tree, if the key was not orderable? — Daniel Langr, Feb 17 '20 at 11:20

Vlad from Moscow · Accepted Answer · 2020-02-17T10:52:40.023

There is an overloaded operator < for the class template std::vector.

template <class T, 
class Allocator>
bool operator< (const vector<T, Allocator>& x, const vector<T, Allocator>& y);

that is based on the standard algorithm std::lexicographical_compare.

Here is a demonstrative program.

#include <iostream>
#include <iomanip>
#include <vector>
#include <iterator>
#include <algorithm>

int main() 
{
    std::vector<int> v1 = { 1, 2 };
    std::vector<int> v2 = { 1, 2, 3 };
    std::vector<int> v3 = { 2 };

    std::cout << std::boolalpha << ( v1 < v2 ) << '\n';
    std::cout << std::lexicographical_compare( std::begin( v1 ), std::end( v1 ),
                                               std::begin( v2 ), std::end( v2 ) )
             << '\n';                                              

    std::cout << std::boolalpha << ( v1 < v3 ) << '\n';
    std::cout << std::lexicographical_compare( std::begin( v1 ), std::end( v1 ),
                                               std::begin( v3 ), std::end( v3 ) )
             << '\n';                                              

    std::cout << std::boolalpha << ( v2 < v3 ) << '\n';
    std::cout << std::lexicographical_compare( std::begin( v2 ), std::end( v2 ),
                                               std::begin( v3 ), std::end( v3 ) )
             << '\n';                                              

    return 0;
}

Its output is

true
true
true
true
true
true

So the class can be used as a key in map.

By default the class template map uses the function object std::less that in turn uses the operator <

template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator<pair<const Key, T>>>
class map 
{
    //...
};

However there is no overloaded operator << for the class template std::vector.

I see your answers recently in almost all C++ question on SO, I don't know whether in my whole life I ll ever be able to achieve what you have but I ll try my best. Thanks for the answer — , Feb 17 '20 at 10:54

score 7 · Answer 2 · answered Feb 17 '20 at 10:39

Name of an object and content of that object are always unrelated things.

operator == for std::vector will first compare length of vectors and then each of it's elements using operator == as well.

operator < compares elements in vector lexicographically, i.e. it returns x[i] < y[i] for the first non-equal element in vectors x and y.

These are the requirements std::map has for a type used as Key. Since std::vector satisfies both, it can be used by as Key. Note that type managed by vector must also has these operators overloaded for this to work (because std::vector relies on those operators to implement it's own operators).

How does a vector as a key works internally in C++?

2 Answers2