(C++) An Overview of Associative Containers: std::set and std::map

C++ offers a set of associative containers, including std::set, std::map, std::multiset, and std::multimap.

In order to write correct and effective code, we need to be aware of their core characteristics.

Key characteristics of associative containers

1. They automatically maintain their elements in a sorted order based on a specified comparison criterion.

2. They handle elements based on equivalence, not equality.

This second point is a frequent source of confusion and bugs. Let's clarify the difference.

Equality vs. Equivalence

• Equality

  • Determined by operator==.

  • It checks if two objects have the same value.

  • STL algorithms like std::find rely on equality.

• Equivalence

  • Determined by the container's internal comparison logic.

  • Two elements, x and y, are considered equivalent if neither comes before the other in the container's established sorting order.

  • If we denote the container's comparison function as comp, x and y are equivalent if both comp(x, y) and comp(y, x) return false. (In other words, they are equivalent if !comp(x, y) && !comp(y, x) is true.)

This is why you should always prefer member functions like c.find() over non-member algorithms like std::find() when working with associative containers. The member functions use the container's equivalence-based comparison, ensuring correct and efficient lookups. (Note : The member find() guarantee O(log n) time complexity, as it leverages the container's internal structure (typically a balanced binary search tree.))

Comparison Function

The behavior of an associative container is defined by its comparison function.

By default, the comparator is std::less<T>, which internally calls operator< on the elements.

With operator<, equivalence is defined as !(x < y) && !(y < x).

Three critical rules for comparison functions:

1. Comparator must be a type

   This means you should use a function object (a class or struct with an overloaded operator()) or use decltype on a function pointer.

    // A custom data type
    struct MyData {
        int value;
        // ... other members
    };
   
    // A comparison function for pointers to MyData
    bool cmpMyData(const MyData* lhs, const MyData* rhs) {
        return lhs->value < rhs->value;
    }
   
    // A comparison function object (functor)
    struct MyDataComparator {
        bool operator()(const MyData* lhs, const MyData* rhs) const {
            return lhs->value < rhs->value;
        }
    };
   
    // This will NOT compile. The comparator must be a type.
    // std::set<MyData*, cmpMyData> invalid_set;
   
    // Correct Way 1: Use decltype to get the function pointer's type
    std::set<MyData*, decltype(&cmpMyData)> my_set_1(&cmpMyData);
   
    // Correct Way 2 (Preferred): Use a function object type
    std::set<MyData*, MyDataComparator> my_set_2;
   

2. Comparator must Implement a ‘Strict Weak Ordering’
   Comparison function must return false for equivalent values. A function that returns true for comp(x, x) violates this rule.

    // INCORRECT comparison function
    struct IncorrectComparator {
        bool operator()(const std::string* lhs, const std::string* rhs) const {
            // If lhs and rhs point to equivalent strings, this returns true,
            // violating the strict weak ordering requirement.
            // This can lead to undefined behavior.
            return !(*lhs < *rhs);
        }
    };
   

3. Provide a custom comparator for pointers

   Provide a comparator that dereferences the pointers, when you store raw pointers in an associative container. If not, the elements will be sorted by their memory addresses. This leads to non-deterministic behavior, as the order will change between program executions.

---

References

• C++ reference for std::set

  • https://en.cppreference.com/w/cpp/container/set

• C++ reference for std::map

  • https://en.cppreference.com/w/cpp/container/map

• Effective STL by Scott Meyers (Addison-Wesley Professional, 2001)