C++ Container Adapter Mimics and Priority_queue Use

Container Adapter

Adapters are a design pattern (the design pattern is a set of reused, known to most people, classified cataloging, and code design experience). This pattern is to convert an interface of a class into another interface that customers want. Their underlying containers are all other containers. For example, the underlying containers of stack and queues are deque by default, while the underlying container of priority_queue is vector. They are packaged to provide the interface the user wants.

Simulation functions

Definition: A functor is not a function, but a class that behaves like a function. It overloads opprator()

Advantages of functors:

• Status maintenance: A functor can hold states, and each call can change behavior according to state.
• Inline calls: Since functors are called through objects, the compiler can easily inline them, reducing the calling overhead.
• Highly customized: The behavior can be adjusted through the properties of the object.

Example:

#include <iostream>
#include <algorithm>
#include <vector>
 
class Compare {
public:
    bool operator()(int a, int b) {
        return a < b;
    }
};
 
int main() {
    std::vector<int> numbers = {10, 65, 30, 99, 23};
 
    //Sorting with functors    std::sort((), (), Compare());
 
    std::cout << "Sorted numbers: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
 
    return 0;
}

In this example,CompareIt's a functor, it overloadsoperator()To perform integer comparison. We use this functor asstd::sortThe comparison function is used to sort an integer vector.

priority_queue

Brief introduction to priority_queue

priority_queue is a container adapter (such as stack, queue) whose underlying container is vector. It behaves like heap (heap) by default, which is built with a large heap. Its underlying container must be able to support accessing elements at any time (this is also to meet the requirements of heap building)

Simulation implementation

template<class T>
	struct less
	{
		bool operator()(const T& left, const T& right)
		{
			return left < right;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& left, const T& right)
		{
			return left > right;
		}
	};

First implement two functors that can be used to build a large (small) heap

Then implement the downward and upward adjustment algorithm

void AdjustUP(int child)
		{
			int parent = ((child - 1) >> 1);
			while (child)
			{
				if (Compare()(c[parent], c[child]))
				{
					swap(c[child], c[parent]);
					child = parent;
					parent = ((child - 1) >> 1);
				}
				else
				{
					return;
				}
			}
		}

		// Adjust downward		void AdjustDown(int parent)
		{
			size_t child = parent * 2 + 1;
			while (child < ())
			{
				// Find older children with parent as root				if (child + 1 < () && Compare()(c[child], c[child + 1]))
					child += 1;

				// Check whether the parents are satisfied				if (Compare()(c[parent], c[child]))
				{
					swap(c[child], c[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					return;
			}
		}

Up (down) adjustment algorithm

Upward adjustment algorithm: Starting from the last node, compare with your father, if it is older (small), exchange positions with your father until it is adjusted to the root node

Down adjustment algorithm: Starting from the root node, compared with those with larger (smaller) of the left and right child nodes, if the root node is larger (smaller), the position will be exchanged and all the way down to the last node.

Next is a relatively simple implementation using the interface

template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		// Create an empty priority queue		priority_queue() : c() {}

		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: c(first, last)
		{
			// Adjust the elements in c into heap structure			int count = ();
			int root = ((count - 2) >> 1);
			for (; root >= 0; root--)
				AdjustDown(root);
		}

		void push(const T& data)
		{
			c.push_back(data);
			AdjustUP(() - 1);
		}

		void pop()
		{
			if (empty())
				return;

			swap((), ());
			c.pop_back();
			AdjustDown(0);
		}

		size_t size()const
		{
			return ();
		}

		bool empty()const
		{
			return ();
		}

		// Modification of the heap top element is not allowed, because: modification of the heap top element can destroy the heap's characteristics		const T& top()const
		{
			return ();
		}
        private:
		Container c;
	};

This is the end of this article about C++ container adapter functors and priority_queue. For more related C++ container adapter and priority_queue content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!