C++ Utilities

Various utilities that extend the C++ Standard Library.

• Contents
  • Constant Expression Square Root
  • Updatable Priority Queue
• Configuration
• Testing
• License

Contents

• Constant Expression Square Root
• Updatable Priority Queue

(Back to Top)

Constant Expression Square Root

Constant expression (constexpr) square root function. Note that the C++ Standard Library's square root function (std::sqrt) is not a constant expression. Returns the same result as the C++ Standard Library's implementation to within one unit in the last place (1 ULP).

constexpr double square_root_of_two = utility::constexpr_sqrt(2.0);

If you wish to use this implementation in your project, copy the constexpr_sqrt.hpp header file to your source code repository and include it in your C++ source code files with #include "constexpr_sqrt.hpp".

(Back to Contents)

Updatable Priority Queue

Simple C++ priority queue where the priorities of elements can be updated. Each element consist of a value and a priority; multiple values can have the same priority, but values must be unique.

utility::updatable_priority_queue<std::string, double> name_and_score;

name_and_score.insert("Alice", 10.0);
name_and_score.insert("Bob", 15.0);
name_and_score.insert("Claire", 5.0);
std::cout << name_and_score.front_value() << std::endl;  // Claire

name_and_score.update("Claire", 20.0);
std::cout << name_and_score.front_value() << std::endl;  // Alice

name_and_score.erase_front();
std::cout << name_and_score.front_value() << std::endl;  // Bob

The C++ Standard Library's priority queue (std::priority_queue) does not support updating the priority of its elements; certain use cases such as Dijkstra's algorithm require this operation. This project implements a priority queue that supports updating the priority of its elements and achieves the same asymptotic time complexity and asymptotic space complexity as the C++ Standard Library's implementation to within a constant factor.

If you wish to use this implementation in your project, copy the updatable_priority_queue.hpp header file to your source code repository and include it in your C++ source code files with #include "updatable_priority_queue.hpp".

(Back to Contents)

Configuration

This project requires the following packages:

• C++11 Compiler: Any C++11 compiler will do, such as GCC or Clang. On Ubuntu, install GCC with sudo apt install g++ or Clang with sudo apt install clang.
• CMake: On Ubuntu, install CMake with sudo apt install cmake.

Clone this project's repository and configure it with:

git clone [email protected]:acodcha/cpp-utilities.git
cd cpp-utilities
mkdir build
cd build
cmake ..

This is a header-only library, so no compilation is needed.

(Back to Top)

Testing

Testing is optional, disabled by default, and requires the following additional package:

• GoogleTest: The GoogleTest library (https://github.com/google/googletest) is used for testing. On Ubuntu, install it with sudo apt install libgtest-dev. When testing is enabled, if the GoogleTest library is not found on your system, it is automatically downloaded, built, and linked with this project.

You can manually test this project from the build directory with:

cmake .. -DTEST_CPP_UTILITIES=ON
make --jobs=16
make test

(Back to Top)

License

This project is maintained by Alexandre Coderre-Chabot (https://github.com/acodcha) and licensed under the MIT license. For more details, see the LICENSE file or visit https://mit-license.org.

(Back to Top)