CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 13 of 13

Thread: stl find

  1. #1
    Join Date
    May 2015
    Posts
    500

    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

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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)

  3. #3
    Join Date
    May 2015
    Posts
    500

    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"

  4. #4
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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)

  5. #5
    Join Date
    May 2015
    Posts
    500

    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...

  6. #6
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,721

    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;
    }

  7. #7
    Join Date
    May 2015
    Posts
    500

    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 ?

  8. #8
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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)

  9. #9
    Join Date
    May 2015
    Posts
    500

    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.

  10. #10
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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)

  11. #11
    Join Date
    Feb 2017
    Posts
    677

    Re: stl find

    Quote Originally Posted by pdk5 View Post
    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.

  12. #12
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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)

  13. #13
    Join Date
    Feb 2017
    Posts
    677

    Re: stl find

    Quote Originally Posted by 2kaud View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured