-
July 28th, 2022, 08:09 AM
#1
stl find
Hello,
I have a table like:
index value
-------------
64 and more x1
32 to 63 x2
16 to 31 x3
8 to 15 x4
1 to 7 x5
Now we store , the index, values, 1, 8, 16, 32, 64 in a vector A.
and x1, to x5 in another vector B.
I need to write a function (efficint, may be use cache)
to get value, for the particular index.
thankyou very much for the inputs
pdk
-
July 28th, 2022, 09:52 AM
#2
Re: stl find
Sorry, but I'm not understanding. Perhaps you could provide an example of A and B and what is expected from the function.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
July 28th, 2022, 10:47 AM
#3
Re: stl find
Thankyou very much kaud.
Sorry for delay
vector A = {1,8,16,32,64}
vector B={ x5, x4, x3,x2,x1}
The function needs to check,
- if the passed index , falls to 64 and above , Return value "x1"
- if the passed index is from 32 to 63 , Return " x2"
-
July 28th, 2022, 11:23 AM
#4
Re: stl find
Is something like this what you are after? I'm not sure what type x1 - x5 are so I've just made them literals.
Code:
#include <iostream>
#include <vector>
#include <iterator>
int main() {
const std::vector A { 1, 8, 16, 32, 64 };
const std::vector B { "x5", "x4", "x3", "x2", "x1" };
for (int i {1}; i > 0; ) {
std::cin >> i;
for (auto it { A.rbegin() }; it != A.rend(); ++it)
if (i - *it >= 0) {
std::cout << B[std::distance(A.begin(), it.base()) - 1] << '\n';
break;
}
}
}
Code:
66
x1
32
x2
63
x2
1
x5
7
x5
8
x4
17
x3
16
x3
100
x1
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
July 28th, 2022, 11:59 AM
#5
Re: stl find
Thankyou very much kaud.
Yes, I needed exactly same logic.
x1, x2, etc are "double" type.
if we put them in a function to pass the index and the double type as output
double GetValue(int index)
{
}
If we keep calling the same function, several times (with consecutive calls having same index).. is there anyway to cache the old value, so to avoid the search again ?
I never written cache, but there is suggestion that cache is helpful...
-
July 28th, 2022, 06:02 PM
#6
Re: stl find
This does not use cache, but one way is to use local static variables
in the function. They are initialized once and remembered between
function calls.
Code:
double GetValue(int index)
{
static int index_last = -1; // must be an index that is not possible
static double value = 0.0f;
if (index == index_last)
{
//cout << "using last call\n";
return value;
}
//cout << "calculating\n";
static const std::vector<int> A{ 1, 8, 16, 32, 64 };
static const std::vector<double> B{ 5.0, 15.0, 6.0, 19.0, 33.0 };
// code to find the value in "B" based on "index"
// this does not verify if "index" is in the A array
for (int i = 0; i < (int)A.size(); ++i)
{
if (index == A[i])
{
index_last = index;
value = B[i];
break;
}
}
return value;
}
-
July 29th, 2022, 02:53 AM
#7
Re: stl find
Thankyou very much for the idea Philip.
@kaud : thankyou very much. Is there any other ways to do this, using predicate may be. Also was wondering, if binary search can be used ?
-
July 29th, 2022, 03:41 AM
#8
Re: stl find
What are the sizes of A and B?
If they are just values from 1 to 64 even in production, then a simple table lookup using an array of size 64 with each element the required x value. If the given value is > 64 then return the last value.
Last edited by 2kaud; July 29th, 2022 at 03:52 AM.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
July 29th, 2022, 05:02 AM
#9
Re: stl find
Thankyou very much kaud.
As of now, the A and B, contain just 1 to 64. It may change in future, so its ok as of now.
-
July 29th, 2022, 06:16 AM
#10
Re: stl find
Then just do it as a simple lookup-table. You don't need A - just B with 64 elements.
x5, x5, x5, x5, x5, x5, x5, x4, x4, x4, x4, x4, x4, x4 ,x4.....
etc. Then just check that index is within range and if is use an index into B. If out of range then return x1.
PS make B std::array as static constexpr within GetValue() (you can't have a constexpr std::vector):
Code:
double GetValue(unsigned i) {
static constexpr double x1 { 1 }, x2 { 2 }, x3 { 3 }, x4 { 4 }, x5 { 5 };
static constexpr std::array B { x5, x5, x5, x5, x5, x5, x5, x4, x4, x4, x4, x4, x4, x4, x3/* .....*/}; // required 64 elements
if (i > B.size())
return x1;
// what if i == 0 ??
return B[i - 1];
}
Last edited by 2kaud; July 29th, 2022 at 11:56 AM.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
July 30th, 2022, 03:47 AM
#11
Re: stl find
Originally Posted by pdk5
As of now, the A and B, contain just 1 to 64. It may change in future, so its ok as of now.
It is possible to use 2kaud's approach (in #8) but in a way that reduces the size of B. That can be useful if A grows in the future but still holds numbers that are all powers of 2. The idea is to use the new (C++ 20) bit-manipulation function std::bit_width to turn the members of A into index positions in B. Your example would look something like this
Code:
const std::vector<int> A { 1, 2, 4, 8, 16, 32, 64 }; // 2 and 4 added
const std::vector<double> B { x5, x5, x5, x4, x3, x2, x1 }; // two x5 added
double GetValue(int index) {
// First sanity check all ranges, then
return B[std::bit_width(A[index])];
}
The std::bit_width function should be pretty cheap. It is based on the lzcnt (leading zero count) instruction which is supported by many processors.
Last edited by wolle; July 30th, 2022 at 03:50 AM.
-
July 31st, 2022, 04:20 AM
#12
Re: stl find
std::bit_width() requires an unsigned type for argument.
"This overload participates in overload resolution only if T is an unsigned integer type (that is, unsigned char, unsigned short, unsigned int, unsigned long, unsigned long long, or an extended unsigned integer type). "
https://en.cppreference.com/w/cpp/numeric/bit_width
Use std::array rather than std::vector so that constexpr can be used for compile-time initialisation.
There's no need for A. B can be accessed direct using index. Consider:
Code:
include <iostream>
#include <array>
#include <bit>
#include <algorithm>
auto GetValue(unsigned index) {
static constexpr double x1 { 1 }, x2 { 2 }, x3 { 3 }, x4 { 4 }, x5 { 5 };
static constexpr std::array B { x5, x5, x5, x4, x3, x2, x1 }; // two x5 added
// index == 0 ???
return B[std::min<unsigned>(B.size(), std::bit_width(index)) - 1];
}
int main() {
for (unsigned i {}; (std::cin >> i) && i > 0;)
std::cout << GetValue(i) << '\n';
}
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
July 31st, 2022, 11:46 PM
#13
Re: stl find
Originally Posted by 2kaud
std::bit_width() requires an unsigned type for argument.
Well, I should have tested my code but it was intended more as an illustration for a suggestion. Anyway, the GetValue function can be declared constexpr and noexcept to make it even better.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|