我有vector
的double
s。我希望找到两个:
x
。x
。例如。如果我有一个矢量:
std::vector<double> vec = {0, 1.0, 3.0, 4.0, 5.0};
和一个价值
x = 2.6;
我希望找到1.0
和3.0
。
这样做最有效的方法是什么?
我有类似的东西:
double x1, x2; // But these need to be initialised!!!
double x = 2.6;
for (i = 0; i < vec.size(); ++i)
{
if (vec[i] >= x && vec[i] < x2)
x2 = vec[i];
if (vec[i] <= x && vec[i] > x1)
x1 = vec[i];
}
但是我如何初始化x1和x2?我可以使x2成为矢量的最大值而x1是最小值,但这需要初始通过数据。有没有办法更有效地做到这一点?
编辑:
我认为我可以/不能对数据做出一些假设:
0
)你可以使用std::lower_bound
:
#include <iterator>
#include <algorithm>
template<class ForwardIt, class T>
std::pair<ForwardIt, ForwardIt> hilo(ForwardIt first, ForwardIt last, T const &value)
{
if (first != last)
{
auto lb = std::lower_bound(first, last, value);
auto prelbd = std::distance(first, lb) - 1;
if (lb == last) return{ std::next(first, prelbd), last };
if (!(value < *lb)) return{ lb, lb };
if (lb == first) return{ last, first };
return{ std::next(first, prelbd), lb };
}
return{ last, last };
}
哪个可以用作:
std::vector<double> vec = { -1.0, -1.0, 0.0, 1.0, 3.0, 3.0, 3.0, 3.0, 4.0, 5.0, 5.0 };
// if not ordered
//std::sort(vec.begin(), vec.end());
double x = 5.0;
auto b = hilo(vec.begin(), vec.end(), x);
if (b.first != vec.end())
{
std::cout << "First index: " << std::distance(vec.begin(), b.first)
<< "(value " << *b.first << ")\n";
}
if (b.second != vec.end())
{
std::cout << "Second index: " << std::distance(vec.begin(), b.second)
<< "(value " << *b.second << ")\n";
}
如果你想避免在整个向量中额外传递,你总是可以为你正在使用的类型获取最大可能值(在这种情况下,为double)。 STL为您提供了一种方法,请参阅例如这里:
http://www.cplusplus.com/reference/limits/numeric_limits/
对于您的情况,请尝试以下方法:
#include <limits> // std::numeric_limits
.
.
.
double x1 = std::numeric_limits<double>::max();
double x2 = std::numeric_limits<double>::min();
.
.
.
// rest of your code
使用迭代器:
auto maxBelowX = vec.end();
for (auto i = vec.begin(); i != vec.end(); ++i)
{
if (*i <= x && (i == vec.end() || *i > maxBelowX)) {
maxBelowX = i;
}
}
if (maxBelowX == vec.end()) {
std::cout << "There was no element <= x";
}
要将x1
和x2
初始化为向量的最小值和最大值,我会想象你别无选择,只能通过它,除非你先在向量上调用std::sort
,然后按升序或降序排序,然后选择头/尾列表的位置,取决于您的顺序,初始化两个值。
您还可以使用qazxsw poi从容器中获取最小值,或使用qazxsw poi查找容器中的最大元素。
没有必要通过向量来获得向量中的最小值和最大值,因为它们仍然不能保证分别小于或大于std::min_element
(考虑std::max_element
的向量x
- 你可以初始化[1 2 3 4]
但是之后循环你会错误地认为它是最小的值x = 5
)。
看来你需要的是将x1 = 4
和>= 5
初始化为明确标记你是否找到最小值或最大值的值,其中明确表示你不能将它们误认为向量中的实际值。
Yannis Douros给出的一个建议是使用x1
和x2
。或者你可以去
std::numeric_limits<double>::min()
在循环期间,std::numeric_limits<double>::max()
将被第一个大于x1 = x - 1;
x2 = x + 1;
的值覆盖,因此在循环之后,您需要做的就是检查x1
是否知道您是否找到了最小值。如果你有,它的价值将是x
。
同样,如果x1 >= x
应该是x1
,那么小于x2
的最大值是<= x
,如果另一方面x
(即x2
仍然是x2 > x
)并且你没有找到最大值。
您可以使用以下方法
x2
程序输出是
x + 1
如果矢量已排序,那么您可以使用标准算法#include <iostream>
#include <vector>
#include <utility>
int main()
{
std::vector<double> v = { 0, 1.0, 3.0, 4.0, 5.0 };
double x = 2.6;
auto minmax = std::make_pair( v.size(), v.size() );
for ( std::vector<double>::size_type i = 0; i != v.size(); ++i )
{
if ( v[i] <= x && ( minmax.first == v.size() || v[minmax.first] < v[i] ) )
{
minmax.first = i;
}
else if ( x <= v[i] && ( minmax.second == v.size() || v[i] < v[minmax.second] ) )
{
minmax.second = i;
}
}
if ( minmax.first != v.size() )
{
std::cout << "The maximum value less than or equal to " << x
<< " is " << v[minmax.first] << std::endl;
}
if ( minmax.second != v.size() )
{
std::cout << "The minimum value greater than or equal to " << x
<< " is " << v[minmax.second] << std::endl;
}
return 0;
}
。例如
The maximum value less than or equal to 2.6 is 1
The minimum value greater than or equal to 2.6 is 3
程序输出与上面显示的相同。
这可以使用std::equal_range
完成
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
int main()
{
std::vector<double> v = { 0, 1.0, 3.0, 4.0, 5.0 };
double x = 2.6;
auto minmax = std::equal_range( v.begin(), v.end(), x );
if ( minmax.first == minmax.second )
{
if ( minmax.first != v.begin() ) std::advance( minmax.first, -1 );
else minmax.first = v.end();
}
else
{
std::advance( minmax.second, - 1 );
}
if ( minmax.first != v.end() )
{
std::cout << "The maximum value less than or equal to " << x
<< " is " << *minmax.first << std::endl;
}
if ( minmax.second != v.end() )
{
std::cout << "The minimum value greater than or equal to " << x
<< " is " << *minmax.second << std::endl;
}
return 0;
}