C++中基于vector第三个元素的最小STL优先队列实现及官方源码查询

Hey there! Let's walk through exactly how to build this custom min-priority queue using C++ STL's priority_queue, where each element is a 4-element vector, and we sort based on the 3rd element (remember, C++ uses 0-indexing, so that's index 2).

Step 1: Understand the Custom Comparator #

The default std::priority_queue is a max-heap, meaning the largest element sits at the top. To make it a min-heap based on the 3rd vector element, we need to define a custom comparator that tells the queue how to order elements.

Our comparator will return true when the first vector's 3rd element is greater than the second's—this reverses the default behavior, pushing smaller 3rd elements to the top.

Step 2: Full Implementation Code #

Here's a complete, working example with explanations in comments:

#include <iostream>
#include <vector>
#include <queue>
#include <cassert> // Optional: For enforcing 4-element vectors

// Custom comparator struct to order vectors by their 3rd element (index 2)
struct VectorThirdElementComparator {
    bool operator()(const std::vector<int>& vec_a, const std::vector<int>& vec_b) {
        // Ensure both vectors have exactly 4 elements (optional but recommended)
        assert(vec_a.size() == 4 && vec_b.size() == 4);
        
        // Return true if vec_a's 3rd element is larger than vec_b's
        // This makes the priority_queue a min-heap for the 3rd element
        return vec_a[2] > vec_b[2];
    }
};

int main() {
    // Declare our priority queue:
    // - Element type: std::vector<int>
    // - Underlying container: std::vector<std::vector<int>> (default for priority_queue)
    // - Comparator: Our custom struct
    std::priority_queue<
        std::vector<int>,
        std::vector<std::vector<int>>,
        VectorThirdElementComparator
    > min_pq;

    // Insert test vectors (all have 4 elements)
    min_pq.push({10, 20, 5, 30});   // 3rd element: 5
    min_pq.push({5, 15, 2, 25});    // 3rd element: 2 (smallest)
    min_pq.push({1, 3, 8, 4});      // 3rd element: 8 (largest)

    // Print and pop elements to verify the min-heap behavior
    std::cout << "Priority queue output (ordered by smallest 3rd element first):\n";
    while (!min_pq.empty()) {
        const auto& top_vec = min_pq.top();
        std::cout << "Vector: [" << top_vec[0] << ", " << top_vec[1] << ", " 
                  << top_vec[2] << ", " << top_vec[3] << "] (3rd element: " << top_vec[2] << ")\n";
        min_pq.pop();
    }

    return 0;
}

Step 3: Key Notes #

• Enforcing 4-element vectors: The assert statements are optional but help catch bugs if you accidentally push a vector with the wrong size. For production code, you might want to add runtime checks instead of assertions.
• Lambda Alternative: If you prefer a more concise approach, you can use a lambda as the comparator (C++11 and later). Just note that you need to wrap it in std::function or use decltype:

  auto comparator = [](const std::vector<int>& a, const std::vector<int>& b) {
      return a[2] > b[2];
  };
  std::priority_queue<std::vector<int>, std::vector<std::vector<int>>, decltype(comparator)> min_pq(comparator);
  

About the STL priority_queue Official Implementation #

The STL std::priority_queue is a container adapter, meaning it uses an underlying container (by default std::vector) to store elements. It leverages heap algorithms from the <algorithm> header—specifically std::make_heap, std::push_heap, and std::pop_heap—to maintain the heap property. By default, it uses std::less<T> to create a max-heap; changing the comparator lets you customize the ordering (like our min-heap here).

内容的提问来源于stack exchange，提问作者aagrawal207