CODEWITHSUNDEEP
c++stl
CodingHero
CodingHero

Reputation: 3025

STL containers - How are unique key values determined?

In STL containers, like map and set - How the unique key is determined for user-defined types?

In C#, this is done by overriding GetHashCode and Equals methods.

Upvotes: 2

Views: 1168

Answers (4)

MSalters
MSalters

Reputation: 179799

Is the most simple case, it's determined by Key1 < Key2. That's to say, by an applicable operator<. There's no need for Equals. If (!(Key1 < Key2)) && (!(Key2 < Key1)) (neither key is smallest), then they're considered equal. For practical purposes, this is wrapped in the std::less<Key> template.

If you want another order, all ordered STL containers take a predicate. This is an object that defines an bool operator()(Key, Key) member to implement a strict weak ordering on keys. That means Pred(a,b) && Pred(b,c) implies Pred(a,c), Pred(a,a) must be false, and Pred(a,b) && Pred(b,a) must also be false. In other words, it must be a "normal" ordering.

Upvotes: 2

innochenti
innochenti

Reputation: 1103

First of all, it is unclear what containers do you need. If you talk about hashes, then use std::unordered_map and see Defining a hash function in TR1 unordered_map inside a struct If you need map or set, you can set order using operator< c++ less operator overload, which way to use?

Upvotes: 0

user1130005
user1130005

Reputation: 412

Edit: Seems like I'm talking about something slightly different here, but I guess I'll just leave it since it seems to be what you're talking about in C#.

You still need to implement your own hash-function and eq-function, you just do it differently. There's different ways of doing so, one for instance is to define a class with operator() to return a certain value etc, then when you define your map you say map<YourClass, YourHashClass, YourEqClass, ...>

Upvotes: 0

Rohan Prabhu
Rohan Prabhu

Reputation: 7302

A map, for example, takes 4 parameters as its template arguments. Most of the time, developers use just 2 of them i.e. the Key type and the Value type. But, one can also provide a functor that compares objects of the Key type (whatever type it would be).

From cplusplus.com:

Compare: Comparison class: A class that takes two arguments of the key type and returns a bool. The expression comp(a,b), where comp is an object of this comparison class and a and b are key values, shall return true if a is to be placed at an earlier position than b in a strict weak ordering operation. This can either be a class implementing a function call operator or a pointer to a function (see constructor for an example). This defaults to less, which returns the same as applying the less-than operator (a

http://www.cplusplus.com/reference/stl/map/

It is true for almost all cases (when using for sorting, or for any other container) and this principle holds across quite a few languages and platforms.

Upvotes: 2

Related Questions