C++ STL–make_heap with pair as data type

cheap

I know how does heap work and how it arranges min and max elements. It is easy, if vector contains only int, to apply make_heap in STL. But how to apply make_heap() if vector contains structure of string and int. Iwant to make heap based on int value in structure.
Please tell me how to do that.

Best Answer

You have to provide comparison function for your structure:

struct A
{
 int x, y;
};

struct Comp
{
   bool operator()(const A& s1, const A& s2)
   {
       return s1.x < s2.x && s1.y == s2.y;
   }
};

std::vector<A> vec;
std::make_heap(vec.begin(), vec.end(), Comp());

Related Solutions

C++ – How to concatenate a std::string and an int

In alphabetical order:

std::string name = "John";
int age = 21;
std::string result;

// 1. with Boost
result = name + boost::lexical_cast<std::string>(age);

// 2. with C++11
result = name + std::to_string(age);

// 3. with FastFormat.Format
fastformat::fmt(result, "{0}{1}", name, age);

// 4. with FastFormat.Write
fastformat::write(result, name, age);

// 5. with the {fmt} library
result = fmt::format("{}{}", name, age);

// 6. with IOStreams
std::stringstream sstm;
sstm << name << age;
result = sstm.str();

// 7. with itoa
char numstr[21]; // enough to hold all numbers up to 64-bits
result = name + itoa(age, numstr, 10);

// 8. with sprintf
char numstr[21]; // enough to hold all numbers up to 64-bits
sprintf(numstr, "%d", age);
result = name + numstr;

// 9. with STLSoft's integer_to_string
char numstr[21]; // enough to hold all numbers up to 64-bits
result = name + stlsoft::integer_to_string(numstr, 21, age);

// 10. with STLSoft's winstl::int_to_string()
result = name + winstl::int_to_string(age);

// 11. With Poco NumberFormatter
result = name + Poco::NumberFormatter().format(age);

is safe, but slow; requires Boost (header-only); most/all platforms
is safe, requires C++11 (to_string() is already included in #include <string>)
is safe, and fast; requires FastFormat, which must be compiled; most/all platforms
(ditto)
is safe, and fast; requires the {fmt} library, which can either be compiled or used in a header-only mode; most/all platforms
safe, slow, and verbose; requires #include <sstream> (from standard C++)
is brittle (you must supply a large enough buffer), fast, and verbose; itoa() is a non-standard extension, and not guaranteed to be available for all platforms
is brittle (you must supply a large enough buffer), fast, and verbose; requires nothing (is standard C++); all platforms
is brittle (you must supply a large enough buffer), probably the fastest-possible conversion, verbose; requires STLSoft (header-only); most/all platforms
safe-ish (you don't use more than one int_to_string() call in a single statement), fast; requires STLSoft (header-only); Windows-only
is safe, but slow; requires Poco C++ ; most/all platforms

C++ – What does the C++ standard state the size of int, long type to be

The C++ standard does not specify the size of integral types in bytes, but it specifies minimum ranges they must be able to hold. You can infer minimum size in bits from the required range. You can infer minimum size in bytes from that and the value of the CHAR_BIT macro that defines the number of bits in a byte. In all but the most obscure platforms it's 8, and it can't be less than 8.

One additional constraint for char is that its size is always 1 byte, or CHAR_BIT bits (hence the name). This is stated explicitly in the standard.

The C standard is a normative reference for the C++ standard, so even though it doesn't state these requirements explicitly, C++ requires the minimum ranges required by the C standard (page 22), which are the same as those from Data Type Ranges on MSDN:

signed char: -127 to 127 (note, not -128 to 127; this accommodates 1's-complement and sign-and-magnitude platforms)
unsigned char: 0 to 255
"plain" char: same range as signed char or unsigned char, implementation-defined
signed short: -32767 to 32767
unsigned short: 0 to 65535
signed int: -32767 to 32767
unsigned int: 0 to 65535
signed long: -2147483647 to 2147483647
unsigned long: 0 to 4294967295
signed long long: -9223372036854775807 to 9223372036854775807
unsigned long long: 0 to 18446744073709551615

A C++ (or C) implementation can define the size of a type in bytes sizeof(type) to any value, as long as

the expression sizeof(type) * CHAR_BIT evaluates to a number of bits high enough to contain required ranges, and
the ordering of type is still valid (e.g. sizeof(int) <= sizeof(long)).

Putting this all together, we are guaranteed that:

char, signed char, and unsigned char are at least 8 bits
signed short, unsigned short, signed int, and unsigned int are at least 16 bits
signed long and unsigned long are at least 32 bits
signed long long and unsigned long long are at least 64 bits

No guarantee is made about the size of float or double except that double provides at least as much precision as float.

The actual implementation-specific ranges can be found in <limits.h> header in C, or <climits> in C++ (or even better, templated std::numeric_limits in <limits> header).

For example, this is how you will find maximum range for int:

#include <limits.h>
const int min_int = INT_MIN;
const int max_int = INT_MAX;

C++:

#include <limits>
const int min_int = std::numeric_limits<int>::min();
const int max_int = std::numeric_limits<int>::max();

Best Answer

Related Solutions

C++ – How to concatenate a std::string and an int

C++ – What does the C++ standard state the size of int, long type to be

Related Topic