Работа lower_bound в C++

Question

Помогите разобраться в работе lower_bound:

Есть struct:

struct MyStruct
{
  int firstNum;
  int secondNum;
}

и есть vector<MyStruct> myVector, который хранит структуры.

Информация в myVector:

[0] = {firstNum=1 secondNum=1 }
[1] = {firstNum=1 secondNum=2 }
[2] = {firstNum=2 secondNum=1 }
[3] = {firstNum=2 secondNum=2 }
[4] = {firstNum=3 secondNum=1 }
[5] = {firstNum=3 secondNum=2 }
[6] = {firstNum=4 secondNum=1 }
[7] = {firstNum=4 secondNum=2 }
[8] = {firstNum=4 secondNum=3 }
[9] = {firstNum=4 secondNum=4 }

Есть задача: при добавлении в myVector располагать объект в нужном месте, то есть: при добавлении MyStrcut ms {2,3} элементы myVector имели уже след. вид:

[2] = {firstNum=2 secondNum=1 }
[3] = {firstNum=2 secondNum=2 }
[4] = {firstNum=2 secondNum=3 }
[5] = {firstNum=3 secondNum=1 }

Пытался вот так сделать:

auto iter = lower_bound(myVector.begin(), myVector.end(), ms, 
                [](const myStruct& mv1, const myStruct& mv2) -> bool {return (mv1.firstNum == mv2.firstNum && mv1.secondNum
< mv2.secondNum); });

myVector.insert(iter, ms);

Но это работает неправильно: некоторые элементы добавляет в нужно место, а некоторые в самое начало почему-то.

Answer 1

У вас неправильный компаратор.

Должно быть:

auto iter = lower_bound(myVector.begin(), myVector.end(), ms,
        [](const MyStruct& mv1, const MyStruct& mv2) -> bool {
            return (mv1.firstNum < mv2.firstNum || (mv1.firstNum == mv2.firstNum && mv1.secondNum
            < mv2.secondNum)); 
        });

Вот так более читаемо:

auto iter = lower_bound(myVector.begin(), myVector.end(), ms,
        [](const MyStruct& mv1, const MyStruct& mv2) -> bool {
            if (mv1.firstNum != mv2.firstNum)
                return mv1.firstNum < mv2.firstNum;
            return mv1.secondNum < mv2.secondNum;
        });

Дело в том, что в вашем компараторе элементы структуры не сравниваются по первому значению, из-за чего возникают проблемы при сортировке в лексикографическом порядке.

В таком случае нужно при неравенстве firstNum сортировать по нему, в случае равенства сортировать по secondNum.

БЛОГ НА HUSL

Работа lower_bound в C++

Ответы (1 шт):