使键等于（如果键存在于映射中）或严格小于映射中的给定输入

Question

我将 numberOfItems 个键作为输入并将它们放在这样的地图中：

int numberOfItems;
int query;
scanf("%d",&numberOfItems);
int temp;
map<int,int> iimap;
for(int i=0;i<numberOfItems;i++)
{
    scanf("%d",&temp);
    iimap.insert(make_pair(temp,1));
}
printf("Enter query: ");
scanf("%d",&query);
int VstrictlyLessOrEqual = FstrictlyLessOrEqual(query);

我设置了每次输入的默认键=1；因此，不存在的键的值为 =0 .

6 100 5 4 3 2 1 50

对于这个输入（第一个输入6是numberOfItems，最后一个输入50是query）FstrictlyLessOrEqual()应该return值5

Answer 1

您想使用 std::map 的 upper_bound() or lower_bound() 方法：

upper_bound()

upper_bound() returns 指向比搜索的键更高的第一个键的迭代器。所以：

致电upper_bound().
If upper_bound() returned begin() 这意味着搜索的是低于地图中最低的键。
否则递减迭代器。它现在将指向一个等于搜索的键或下一个更小的键的键。

lower_bound()

lower_bound() returns 指向映射中第一个等于或大于搜索键的键的迭代器，因此要实现您的目标，您需要：

呼叫lower_bound()
检查lower_bound()是否没有returnend()，迭代器的key是否与你搜索的key相同。密钥存在于地图中。
否则，检查是否 lower_bound() returned 映射的 begin() 迭代器值。如果是，这意味着你搜索的键低于映射中的第一个键，因此存在这样的值。
否则，递减 returned 迭代器。您搜索的键在映射中不存在，递减后的迭代器指向映射中下一个最小的键。

Answer 2

如果键的默认顺序 (std::less) 不是必需的，那么使用 std::greater 作为 key_compare 和单个 lower_bound() 调用就可以了.

// std::greater instead of default std::less
std::map<int, int, std::greater<int>> m = {{3, 0}, {5, 0}, {7, 0}, {9, 0}};

auto it = m.lower_bound(1);
printf("%d\n", it != m.end() ? it->first : -1); // prints -1
it = m.lower_bound(3);
printf("%d\n", it != m.end() ? it->first : -1); // prints 3
it = m.lower_bound(4);
printf("%d\n", it != m.end() ? it->first : -1); // also prints 3

Answer 3

Return 指向最后一个键为 < key 的元素的迭代器。如果没有找到这样的元素，则返回尾后迭代器。

template <typename C>
typename C::const_iterator
find_key_less(const C& c, const typename C::key_type& key)
{
    auto iter = c.lower_bound(key);
    if (iter == c.cbegin())
        return c.cend();
    return --iter;
}

Return 指向最后一个键为 <= key 的元素的迭代器。如果没有找到这样的元素，则返回尾后迭代器。

template <typename C>
typename C::const_iterator
find_key_less_equal(const C& c, const typename C::key_type& key)
{
    auto iter = c.upper_bound(key);
    if (iter == c.cbegin())
        return c.cend();
    return --iter;
}

find_key_greater_equal == lower_bound

find_key_greater == upper_bound

使键等于（如果键存在于映射中）或严格小于映射中的给定输入

Get the key equal (if key exists in the map) or strictly less than given input in a map

c++

stl

stdmap

upper_bound()

lower_bound()