CODEWITHSUNDEEP
c++
oldproggy
oldproggy

Reputation: 9

Redefine data area for faster access

New to c++. I've searched but probably using wrong terms.

I want to find which slot in an array of many slots a few bytes long literal value is stored. Currently check each slot sequentially.

If I can use an internal function to scan the whole array as if it was one big string, I feel this would be much faster. (Old COBOL programmer).

Any way I can do this please?

Upvotes: 0

Views: 82

Answers (2)

stefaanv
stefaanv

Reputation: 14392

As you already found out by the comments, "scanning as one big string" is not the way to go in C++.

Typical in C++ when using C-style arrays and normally fast enough for linear search is

auto myStr = "result";
auto it = std::find_if(std::begin(arr), std::end(arr), 
                       [myStr](const char* const str) { return std::strcmp(mystr,str) == 0; });

Remember that string compare function stop at the first wrong character.

More C++ style:

std::vector<std::string> vec = { "res1", "res2", "res3" };
std::string myStr = "res2";
auto it = std::find(vec.begin(), vec.end(), myStr);

If you are interested in very fast lookup for a large container, std::unordered_set is the way to go, but the "slot" has lost its meaning then, but maybe in that case std::unordered_map can be used.

std::unordered_set<std::string> s= { "res1", "res2", "res3" };
std::string myStr = "res2";
auto it = s.find(myStr);

All code is written as example, not compiled/tested

Upvotes: 0

Richard Hodges
Richard Hodges

Reputation: 69912

I want to find which slot in an array of many slots a few bytes long literal value is stored. Currently check each slot sequentially.

OK, I'm going to take a punt and infer that:

  1. you want to store string literals of any length in some kind of container.

  2. the container must be mutable (i.e. you can add literals at will)

  3. there will not be duplicates in the container.

  4. you want to know whether a string literal as been stored in the container previously, and what "position" it was at so that you can remove it if necessary.

  5. the string literals will be inserted in random lexicographical order and need not be sorted.

The container that springs to mind is the std::unordered_set

#include <unordered_set>
std::unordered_set<std::string> tokens;

int main()
{
    tokens.emplace("foo");
    tokens.emplace("bar");
    auto it = tokens.find("baz");
    assert(it == tokens.end());   // not found
    it = tokens.find("bar");      // will be found
    assert(it != tokens.end());
    tokens.erase(it);             // remove the token
}

The search time complexity of this container is O(1).

Upvotes: 1

Related Questions