C++: Create integer vector of infinities

Question

I'm working on an algorithm and I need to initialize the vector of ints:

std::vector<int> subs(10)

of fixed length with values:

{-inf, +inf, +inf …. }

This is where I read that it is possible to use MAX_INT, but it's not quiete correct because the elements of my vector are supposed to be greater than any possible int value.

I liked overrloading comparison operator method from this answer, but how do you initialize the vector with infinitytype class objects if there are supposed to be an int?

Or maybe you know any better solution?

Thank you.

`int` is a type typically of size 32 bits. To the object of type `int`, you can therefore store any 0/1 combination of 32 bits. Each such combination is interpreted as a finite number. There is no option to store `inf` into integer. — Daniel Langr, Feb 28 '18 at 10:52
If your vector elements may be greater than any possible `int` value, the they cannot be `int` values. It looks like you have an XY problem. Why do you need infinity vaues? — n. m. could be an AI, Feb 28 '18 at 10:54
@GusevSlava If you need `<=` then `std::numeric_limits::max()`? If you need `<` then you can't do that with `int`. I'm not sure what you are trying to achieve. — freakish, Feb 28 '18 at 10:57
`<=` means "less than or equal to". Every int value is less than or equal to `INT_MAX`. — n. m. could be an AI, Feb 28 '18 at 10:59
Sorry, I mean that every input integer value has to be `<` than all elements of vector, except the first element. — Gusev Slava, Feb 28 '18 at 11:03
An integer value you are looking for does not exist. Why do you think you need it? — n. m. could be an AI, Feb 28 '18 at 11:13
Will you be doing anything more then comparing `>` and `<` against `int`? You could extend @lisyarus idea by adding `operator=` and `operator int()` ect. and then you can use it as if it was an int. — super, Feb 28 '18 at 12:13
Your vector contains int values. By definition, an int value cannot be greater than the greatest possible int value. Same for floats: even `+inf` is not larger than `+inf`. — MSalters, Feb 28 '18 at 13:02
"I mean that every input integer value has to be < than all elements of vector, except the first element" Would a `std::set>` be the collection you are after? I.e. a collection of `int` values in descending order — Caleth, Feb 28 '18 at 13:39

einpoklum · Accepted Answer · 2018-02-28T17:58:13.787

The solution depends on the assumptions your algorithm (or the implementation of your algorithm) has:

You could increase the element size beyond int (e.g. if your sizeof(int) is 4, use int64_t), and initialize to (int64_t) 1 + std::numeric_limits<int>:max() (and similarly for the negative values). But perhaps your algorithm assumes that you can't "exceed infinity" by adding on multiplying by positive numbers?
You could use an std::variant like other answers suggest, selecting between an int and infinity; but perhaps your algorithm assumes your elements behave like numbers?
You could use a ratio-based "number" class, ensuring it will not get non-integral values except infinity.
You could have your algorithm special-case the maximum and minimum integers
You could use floats or doubles which support -/+ infinity, and restrict them to integrality.
etc.

So, again, it really just depends and there's no one-size-fits-all solution.

score 1 · Answer 2 · answered Feb 28 '18 at 10:56

1

AS already said in the comments, you can't have an infinity value stored in int: all values of this type are well-defined and finite.

If you are ok with a vector of something working as an infinite for ints, then consider using a type like this:

struct infinite
{ };

bool operator < (int, infinite)
{
    return true;
}

answered Feb 28 '18 at 10:56

lisyarus

15,025
3
43
68

1

Doesn't work for the question - there's no `-inf`. Your `infinite` class will need at least a `bool negative`, and it needs to be taken into account when comparing them. – MSalters Feb 28 '18 at 13:04

score 0 · Answer 3 · answered Feb 28 '18 at 10:58

0

You can use a variant (for example, boost::variant) which supports double dispatching, which stores either an int or an infinitytype (which should store the sign of the infinity, for example in a bool), then implement the comparison operators through a visitor.

But I think it would be simpler if you simply used a double instead of int, and whenever you take out a value that is not infinity, convert it to int. If performance is not that great of an issue, then it will work fine (probably still faster than a variant). If you need great performance, then just use MAX_INT and be done with it.

answered Feb 28 '18 at 10:58

petersohn

11,292
13
61
98

1

Variants are now standard C++ - as of C++17: [`std::variant`](en.cppreference.com/w/cpp/utility/variant/). – einpoklum Feb 28 '18 at 11:03
@einpoklum Do standard variants support double dispatching? – petersohn Feb 28 '18 at 13:12

score 0 · Answer 4 · edited Feb 28 '18 at 13:26

You are already aware of the idea of an "infinite" type, but that implementation could only contain infinite values. There's another related idea:

struct extended_int {
  enum {NEGINF, FINITE, POSINF} type;
  int finiteValue; // Only meaningful when type==FINITE

  bool operator<(extended_int rhs) {
    if (this->type==POSINF) return false;
    if (rhs.type==NEGINF) return false;
    if (this->type==FINITE && rhs.type==POSINF) return false;
    if (this->type==NEGINF && rhs.type==FINITE) return false;
    assert(this->type==FINITE && rhs.type==FINITE);
    return this->finiteValue < rhs.finiteValue)
  }

  // Implicitly converting ctor
  constexpr extended_int(int value) : type(FINITE), finiteValue(value) { }
  // And the two infinities
  static constexpr extended_int posinf;
  static constexpr extended_int neginf;
}

You now have extended_int(5) < extended_int(6) but also extended_int(5) < extended_int::posinf

C++: Create integer vector of infinities

4 Answers4