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

Thread: map search

  1. #1
    Join Date
    May 2015
    Posts
    124

    map search

    Hello,

    I have a function,

    Code:
    class CFEXLIST
    {
    	bool m_bIsAllowed;
    public:
    	bool GetIsAllowed() const 		{ return m_bIsAllowed; }
    	void SetIsAllowed(bool bIsAllowed) {m_bIsAllowed = bIsAllowed;}
    	static bool SaveConfigFlags();
    
    	static std::string className();
    #include "OAM/autogen/HandlerDeclarations_autogen_CFEXLIST.h"
    };
    
    std::map<std::string, CFEXLIST>              m_mTableCFEXLIST;
    
    bool IsNormalisedForwardToNumberAllowed(const string & sNormFwdNumber)
    {
    	bool bMatch = false;
    	string sTestNo, sRecLine;
    	std::map<std::string, CFEXLIST>::iterator iIter = CFEXLISTTable::m_mTableCFEXLIST.find(sNormFwdNumber);
    	if (iIter != CFEXLISTTable::m_mTableCFEXLIST.end())
    	{
    		if( iIter->second.GetIsAllowed() )
    		{
    			bMatch = true;
    		}
    	}
    	else
    	{
    		iIter = CFEXLISTTable::m_mTableCFEXLIST.begin();
    		while (!bMatch && iIter != CFEXLISTTable::m_mTableCFEXLIST.end())
    		{
    			sRecLine = iIter->first;
    			if((sNormFwdNumber.empty() == false) && (sRecLine.empty() == false) && (sRecLine.size() <= sNormFwdNumber.size()))
    			{
    				sTestNo = sNormFwdNumber.substr(0, sRecLine.size());
    				if(sRecLine == sTestNo)
    				{
    					if( iIter->second.GetIsAllowed() )
    					{
    						bMatch = true;
    					}
    				}
    			}
    			if(bMatch)
    				LogTraceS("CFEXLIST", << "Received Forward to number " << sNormFwdNumber << ", config line " << sRecLine << ", derived forward to number " << sTestNo);
    			iIter++;
    		}
    	}
    	return bMatch;
    }
    lets say the table is populated with
    1st element: +18 --> Allow
    2nd element: +1800 --> Deny

    And we pass the +180000000 to the function , we get the first element and returns "Allow". But i want to modify the function, so it returns the best match. i.e 2nd element, and return "Deny".

    Can you help me with this ?

    Pdk
    Last edited by pdk5; May 2nd, 2018 at 09:03 AM.

  2. #2
    Join Date
    May 2015
    Posts
    124

    Re: map search

    I did a quick code changes , and it seems to work:

    Code:
    bool IsNormalisedForwardToNumberAllowed(const string & sFwdNumber)
    {
    	string sForwardNum = const_cast<string &>(sFwdNumber);
    
    	string sNormFwdNumber = System::NormaliseNumber(sForwardNum);
    
    	bool bIsAllowed = false;
    
    	string sTestNo, sRecLine;
    	std::map<std::string, CFEXLIST>::iterator iIter = CFEXLISTTable::m_mTableCFEXLIST.find(sNormFwdNumber);
    	if (iIter != CFEXLISTTable::m_mTableCFEXLIST.end())
    	{
    		bIsAllowed = iIter->second.GetIsAllowed();
    	}
    	else
    	{
    		iIter = CFEXLISTTable::m_mTableCFEXLIST.begin();
    		string tempstring;
    		u16 tempsize=0;
    
    		while ( iIter != CFEXLISTTable::m_mTableCFEXLIST.end())
    		{
    			sRecLine = iIter->first;
    			if((sNormFwdNumber.empty() == false) && (sRecLine.empty() == false) && (sRecLine.size() <= sNormFwdNumber.size()))
    			{
    				sTestNo = sNormFwdNumber.substr(0, sRecLine.size());
    				if((sRecLine == sTestNo) && (tempsize < sRecLine.size()) )
    				{
    					tempstring = sTestNo;
    					tempsize = sRecLine.size();
    					bIsAllowed = iIter->second.GetIsAllowed();
    				}
    			}
    			iIter++;
    		}
    	}
    	return bIsAllowed;
    }
    Not sure whether it is efficient ? Could you please comment ?

  3. #3
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    19,223

    Re: map search

    Well, you could move the condition check
    Code:
    (sNormFwdNumber.empty() == false)
    to be before the while loop.
    And also would change it to look like
    Code:
    (!sNormFwdNumber.empty())
    Victor Nijegorodov

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

    Re: map search

    Code:
    string sForwardNum = const_cast<string &>(sFwdNumber);
    string sNormFwdNumber = System::NormaliseNumber(sForwardNum);
    Why? Why do the copy? Why not just

    Code:
    string sNormFwdNumber = System::NormaliseNumber(sFwdNumber);
    What compiler c++ version are you using - as this looks like old c++98 code?

    For c++17, why not something like (not tried)

    Code:
    bool IsNormalisedForwardToNumberAllowed(const string& sFwdNumber)
    {
    	const string sNormFwdNumber = System::NormaliseNumber(sFwdNumber);
    
    	if (sNormFwdNumber.empty())
    		return false;
    
    	auto& MTable = CFEXLISTTable::m_mTableCFEXLIST;
    
    	if (auto iIter = MTable.find(sNormFwdNumber); iIter != MTable.end())
    		return iIter->second.GetIsAllowed();
    
    	u16 tempsize = 0;
    	bool bIsAllowed = false;
    
    	for (auto iIter : MTable)
    		if (const auto& sRecLine = iIter->first; !sRecLine.empty() && (sRecLine.size() <= sNormFwdNumber.size()))
    			if (const string sTestNo = sNormFwdNumber.substr(0, sRecLine.size()); (tempsize < sRecLine.size()) && (sRecLine == sTestNo))
    				tempsize = sRecLine.size(), bIsAllowed = iIter->second.GetIsAllowed();
    
    	return bIsAllowed;
    }
    PS Once bIsAllowed is found to be true, why not terminate the map iteration? There may be other 'efficiency improvements', but I'm not totally understanding the relationship between what is passed to the function and when .GetIsAllowed() is called within the map iteration?
    Last edited by 2kaud; May 3rd, 2018 at 10:48 AM. Reason: PS
    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++17 Compiler: Microsoft VS2017 (15.8.4)

  5. #5
    Join Date
    Feb 2017
    Posts
    343

    Re: map search

    Quote Originally Posted by pdk5 View Post
    Not sure whether it is efficient ? Could you please comment ?
    I looks like you're accessing the map in two ways. First a random access of the map and if it fails a sequential scan of the map.

    If the random access dominates (the random access is successful most of the time and a scan is very rare) then your code is O(log N) because an std::map is a binary search tree. You could easily improve this and get an O(1) code by simply replacing the map with an std::unordered_map which is a hash table.

    If on the other hand the scan dominates then the above change won't matter much. In that case it may be possible to introduce (set up) a secondary search index (an additional map or unordered_map) that potentially could speed up your code substantially, especially if your data set is big (lots of items to search among).
    Last edited by wolle; May 4th, 2018 at 01:53 AM.

  6. #6
    Join Date
    May 2015
    Posts
    124

    Re: map search

    Thanks a lot kaud for the comments and suggestions, is always very helpful. Because of my c++ skills, it may take time to absorb, so pardon me for that.

    Quote Originally Posted by 2kaud View Post
    Code:
    string sForwardNum = const_cast<string &>(sFwdNumber);
    string sNormFwdNumber = System::NormaliseNumber(sForwardNum);
    Why? Why do the copy? Why not just

    sFwdNumber is a const. But System::NormaliseNumber() function doesnot take const.
    So did a const_cast to sFwdNumber to remove constness.
    Code:
    string sNormFwdNumber = System::NormaliseNumber(sFwdNumber);
    What compiler c++ version are you using - as this looks like old c++98 code?
    yes c++98, it is what my project uses.

    For c++17, why not something like (not tried)

    Code:
    bool IsNormalisedForwardToNumberAllowed(const string& sFwdNumber)
    {
    	const string sNormFwdNumber = System::NormaliseNumber(sFwdNumber);
    
    	if (sNormFwdNumber.empty())
    		return false;
    
    	auto& MTable = CFEXLISTTable::m_mTableCFEXLIST;
    
    	if (auto iIter = MTable.find(sNormFwdNumber); iIter != MTable.end())
    		return iIter->second.GetIsAllowed();
    
    	u16 tempsize = 0;
    	bool bIsAllowed = false;
    
    	for (auto iIter : MTable)
    		if (const auto& sRecLine = iIter->first; !sRecLine.empty() && (sRecLine.size() <= sNormFwdNumber.size()))
    			if (const string sTestNo = sNormFwdNumber.substr(0, sRecLine.size()); (tempsize < sRecLine.size()) && (sRecLine == sTestNo))
    				tempsize = sRecLine.size(), bIsAllowed = iIter->second.GetIsAllowed();
    
    	return bIsAllowed;
    }
    PS Once bIsAllowed is found to be true, why not terminate the map iteration? There may be other 'efficiency improvements', but I'm not totally understanding the relationship between what is passed to the function and when .GetIsAllowed() is called within the map iteration?

    I want to search map for best match than first match. If i terminate the map iteration, the last element may be the best match

    Lets say map has
    1st element: +18 --> Allow
    2nd element: +1800 --> Deny

    And passed number is +180000000 , then i want the search to return the 2nd element. And isallowed = deny.
    Last edited by pdk5; May 4th, 2018 at 04:10 AM.

  7. #7
    Join Date
    May 2015
    Posts
    124

    Re: map search

    wolle, could you please kindly give example ? It will help me

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

    Re: map search

    Code:
    string sNormFwdNumber = System::NormaliseNumber(sForwardNum);
    What is the format of the number produced?

    As you are using the System namespace, is this c++/cli code?

    What about a passed number of +180 - or are all passed numbers 9 digits?

    Have you looked at .upper_bound() (see http://www.cplusplus.com/reference/map/map/upper_bound/).

    Would something like this be what is required (not tried)??

    Code:
    bool IsNormalisedForwardToNumberAllowed(const string & sFwdNumber)
    {
    	const string sNormFwdNumber = System::NormaliseNumber(sFwdNumber);
    
    	if (sNormFwdNumber.empty())
    		return false;
    
    	auto& MTable = CFEXLISTTable::m_mTableCFEXLIST;
    
    	bool bIsAllowed = false;
    	auto iIter = MTable.upper_bound(sNormFwdNumber);
    
    	if (iIter != MTable.begin())
    		iIter = prev(iIter);
    
    	if (const auto& sRecLine = iIter->first; !sRecLine.empty() && (sRecLine.size() <= sNormFwdNumber.size()))
    		if (const string sTestNo = sNormFwdNumber.substr(0, sRecLine.size()); sRecLine == sTestNo)
    			bIsAllowed = iIter->second.GetIsAllowed();
    
    	return bIsAllowed;
    }

    If you could post a sample of the contents of the map (say about a dozen) and a few cases of the passed number and what this should map to, I'll have a further look at it.
    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++17 Compiler: Microsoft VS2017 (15.8.4)

  9. #9
    Join Date
    May 2015
    Posts
    124

    Re: map search

    Quote Originally Posted by 2kaud View Post
    Code:
    string sNormFwdNumber = System::NormaliseNumber(sForwardNum);
    What is the format of the number produced?


    As you are using the System namespace, is this c++/cli code?
    yes

    What about a passed number of +180 - or are all passed numbers 9 digits?
    Passed number can be upto 15 digits

    Have you looked at .upper_bound() (see http://www.cplusplus.com/reference/map/map/upper_bound/).
    Will check that.. thanks a lot

    Would something like this be what is required (not tried)??

    Code:
    bool IsNormalisedForwardToNumberAllowed(const string & sFwdNumber)
    {
    	const string sNormFwdNumber = System::NormaliseNumber(sFwdNumber);
    
    	if (sNormFwdNumber.empty())
    		return false;
    
    	auto& MTable = CFEXLISTTable::m_mTableCFEXLIST;
    
    	bool bIsAllowed = false;
    	auto iIter = MTable.upper_bound(sNormFwdNumber);
    
    	if (iIter != MTable.begin())
    		iIter = prev(iIter);
    
    	if (const auto& sRecLine = iIter->first; !sRecLine.empty() && (sRecLine.size() <= sNormFwdNumber.size()))
    		if (const string sTestNo = sNormFwdNumber.substr(0, sRecLine.size()); sRecLine == sTestNo)
    			bIsAllowed = iIter->second.GetIsAllowed();
    
    	return bIsAllowed;
    }

    If you could post a sample of the contents of the map (say about a dozen) and a few cases of the passed number and what this should map to, I'll have a further look at it.
    DefaultSSFlag y
    DefaultMTCFlag y
    DefaultCLIFlag y
    CFEXLIST Table
    CFEXLIST Mode(Allow/DontAllow)
    +18 Allow
    +1800 Donot Allow
    +18000 Donot Allow
    +189 Donot Allow
    +1890 Donot Allow
    +1900 Donot Allow
    +445678329861 Allow
    +5 Allow
    +55 Allow
    +666 Donot Allow
    +8 Donot Allow
    +88 Allow
    +99 Allow

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

    Re: map search

    Thanks. And some examples of passed numbers and what they should map to?
    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++17 Compiler: Microsoft VS2017 (15.8.4)

  11. #11
    Join Date
    May 2015
    Posts
    124

    Re: map search

    Thanks a lot kaud for trying to help me, The input number example can be +1800000000,

    and it should match to "+18000 Donot Allow " entry
    Last edited by pdk5; May 4th, 2018 at 06:07 AM.

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

    Re: map search

    Yes, but what about inputs say +180, +555, +66
    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++17 Compiler: Microsoft VS2017 (15.8.4)

  13. #13
    Join Date
    May 2015
    Posts
    124

    Re: map search

    +180 should be to => +18 Allow
    +555 => +55 Allow
    +66 => No Match

    As of now, I assumed testno size is always greater or equal to table numbers..This req needs to be crosschecked but !
    Last edited by pdk5; May 4th, 2018 at 06:20 AM.

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

    Re: map search

    Have a play with this and see if it produces what is required.

    Code:
    #include <map>
    #include <string>
    #include <iostream>
    using namespace std;
    
    const map<string, bool> MTable {{"+18", true}, {"+1800", false}, {"+18000", false}, {"+189", false}, {"+1890", false}, {"+1900", false},
    				{"+445678329861", true}, {"+5", true}, {"+55", true}, {"+666", false}, {"+8", false}, {"+88", true}, {"+99", true}};
    
    bool IsNormalisedForwardToNumberAllowed(const string & sFwdNumber)
    {
    	//const string sNormFwdNumber = System::NormaliseNumber(sFwdNumber);
    	const string sNormFwdNumber = sFwdNumber;
    
    	if (sNormFwdNumber.empty())
    		return false;
    
    	//auto& MTable = CFEXLISTTable::m_mTableCFEXLIST;
    
    	bool bIsAllowed = false;
    	auto iIter = MTable.upper_bound(sNormFwdNumber);
    
    	if (iIter != MTable.begin())
    		iIter = prev(iIter);
    
    	if (const auto& sRecLine = iIter->first; !sRecLine.empty() && (sRecLine.size() <= sNormFwdNumber.size()))
    		if (const string sTestNo = sNormFwdNumber.substr(0, sRecLine.size()); sRecLine == sTestNo) {
    			bIsAllowed = iIter->second;  //.GetIsAllowed();
    			cout << "using " << iIter->first << " ";
    		}
    
    	return bIsAllowed;
    }
    
    int main()
    {
    	for (string li; getline(cin, li);)
    		cout << IsNormalisedForwardToNumberAllowed(li) << endl;
    }
    Note the commented code so that the small test program compiles OK.
    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++17 Compiler: Microsoft VS2017 (15.8.4)

  15. #15
    Join Date
    May 2015
    Posts
    124

    Re: map search

    Thanks a lot kaud

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)