Searching through stl containers

[Ch1156]

So I am going through my knowledge of stuff and trying to strengthen up areas that are the weakest. I noticed I do not know how to search through STL containers very well, so I am practicing that. I started with vectors but the code I used below can be pretty much interchanged with any STL container right?

I'd like to know if what I've written below is good enough for general use and if there's any other methods i can use to search through containers to find stuff. Thank you!

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>

using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::iterator;
using std::find;

void SearchStandardVector();

int main()
{
    SearchStandardVector();
}

void SearchStandardVector()
{
    vector<string> stringVector{ };
    string stringToFind{ "%" };

    stringVector.push_back("@");
    stringVector.push_back("#");
    stringVector.push_back("&");
    stringVector.push_back("*");
    stringVector.push_back("%");

    vector<string>::iterator itr = std::find(stringVector.begin(), stringVector.end(), stringToFind);
    int index = std::distance(stringVector.begin(), itr);

    int itemOccurance{ 0 };

    if (itr != stringVector.end())
    {
        cout << "Found " << stringToFind << " in vector, at index: " << index << " which is the #" << index + 1 << " spot in the vector." << endl;
        itemOccurance++;
        if (itemOccurance == 1)
        {
            cout << "Item already exists in vector at index " << index << endl;
        }
    }
    else
    {
        cout << "Did not find " << stringToFind << " in vector, so it was added." << endl;
		stringVector.push_back(stringToFind);

        for (auto& i : stringVector)
        {
            cout << i << endl;
        }
    }
}

[seeplus]

l32 Use auto for type of itr. It's much easier than having to know the actual type!

Same as L33. So you get the type returned from std::distance. Also L33 index can be specified as const as it isn't intended to change.

L35. 0 is the default for int - so needn't be specified.

L40. Unless needed (not here), use pre-increment rather than post-increment. It's doesn't matter much here - but in some cases it can.

L51 as you aren't changing the contents, the specify i as const.

L53 - and others. It's preferable to use '\n' instead of endl. endl does a stream flush (which can be time costly) and just using '\n' doesn't.

[TheIdeasMan]

const std::vector<std::string> stringVector{ "@", "#", "&", "*"};

This is easier than a bunch of pushback's, because the values are hard coded.


https://en.cppreference.com/w/cpp/algorithm/find

In this reference, note that:

cppreference wrote:

Type requirements
-
InputIt must meet the requirements of LegacyInputIterator.
-
ForwardIt must meet the requirements of LegacyForwardIterator.
-
UnaryPredicate must meet the requirements of Predicate.

If you look up these, it may help you when seeing whether std::find can be used with other containers. Look up the reference for each container you want to use, and see what the definitions are for its iterators.

In the example on that page see how they made use of std::end ?

Sometimes one doesn't care where in the container a particular value is: if it's there, use it.

[JLBorges]

> if there's any other methods i can use to search through containers to find stuff.

C++20 has constrained versions of the find algorithms in in the namespace std::ranges.
https://en.cppreference.com/w/cpp/algorithm/ranges/find

"In these algorithms, a range can be specified as a single range argument, and projections and pointer-to-member callables are supported."
https://en.cppreference.com/w/cpp/algorithm/ranges

For example:

#include <iostream>
#include <string>
#include <algorithm>
#include <ranges>
#include <iterator>
#include <vector>
#include <list>

int main()
{
    const std::vector<std::string> vec { "zero", "one", "two", "three", "four", "five" } ;
    const std::string text_to_find = "three" ;

    // find a string in a vector of strings
    if( const auto iter = std::ranges::find( vec, text_to_find ) ; iter != std::ranges::end(vec) )
    {
        std::cout << "found string '" << text_to_find << "' at position "
                  << std::distance( std::ranges::begin(vec), iter ) << '\n' ; // O(1)
    }

    struct A { std::string text ; std::size_t value = 0 ; };

    const std::list<A> lst { {"zero",0}, {"one",11}, {"two",222}, {"three",3333}, {"four",44444}, {"five",555555} } ;

    // find an A with the specified text member in a list
    if( const auto iter = std::ranges::find( lst, text_to_find, &A::text ) ; iter != std::ranges::end(lst) )
    {
        std::cout << "found item with A::text == '" << text_to_find << "' at position "
                  << std::distance( std::ranges::begin(lst), iter ) // O(N)
                  << "  (iter->value == " << iter->value << ")\n" ;
    }

    const std::size_t value_to_find = 44444 ;
    // find an A with the specified value member in the list
    if( const auto iter = std::ranges::find( lst, value_to_find, &A::value ) ; iter != std::ranges::end(lst) )
    {
        std::cout << "found item with A::value == " << value_to_find << " at position "
                  << std::distance( std::ranges::begin(lst), iter ) // O(N)
                  << "  (iter->text == '" << iter->text << "')\n" ;
    }
}

http://coliru.stacked-crooked.com/a/dce244013ac6d9fb

[coder777]

but the code I used below can be pretty much interchanged with any STL container right?

No, std::vector is the most general container, it is like an dynamic array. Everythings remains where you put it.

Another container would be std::set. It stores each value only once and sorts them. Thus the values need to obey more requirements. Other containers are std::stack, std::quieue etc.

So it depends on the requirements to the container when you choose one.

[seeplus]

Also note that some containers have their own .find() methods. If they do, then it's usually better to use that .find() method over the general std::find() as the specific ones will be optimised for that container type.

[Ch1156]

Wow thanks for all the replies everyone, some of these i will have to go through more thoroughly. But I made some of the changes to my code already. I had a question about std::distance, I heard that using it isnt a good idea, but I cant remember if it was std::distance or another thing, can anyone clarify?

My use for searching a container is for searching through a game inventory or something like that. So im trying to figure out the proper way to do that, using the most current version of C++.

[JLBorges]

> std::distance, I heard that using it isnt a good idea

If we do need the distance between two iterators, using std::distance (or std::ranges::distance) is a good idea anywhere;
it is a valuable idea in generic code (when there is no guarantee that the iterator is a random access iterator).

Complexity:
Linear.

However, if InputIt additionally meets the requirements of
LegacyRandomAccessIterator, complexity is constant.
https://en.cppreference.com/w/cpp/iterator/distance

Classic C++: abstraction without (an avoidable) performance penalty.


> My use for searching a container is for searching through a game inventory or something like that

Consider using a suitable associative or unordered associative container.
They "implement data structures that can be quickly searched"
https://en.cppreference.com/w/cpp/container#Associative_containers

[Ch1156]

Thank you, yeah I will use something like a map for that or something else, I will have to do some research. Theres quite a few containers to choose from, i'll just have to choose what works best. I just wanted to learn how to do it with a vector just so that I know how in case i ever need to, cant hurt to just have the knowledge.

Quick question, is there a way to print map keys without an iterator? What if i just want to print the key "Health Pack" and not the value associated with it? or in this case compare the key with a string? I cant seem to find anything telling me how to print only the key without an iterator.

    map<string, int> myMap;
    map<string, int>::iterator it;

    myMap["Health Pack"] = 50;
    myMap["9mm Ammo"] = 100;
    myMap[".308 Ammo"] = 150;
    myMap["Shotgun Ammo"] = 200;
    myMap["Weapon Repair Kit"] = 5;

    int enumerator{ 1 };

    for (const auto& i : myMap)
    {
        cout << enumerator++ << ") " << i.first << " - " << i.second << '\n';
    }

    cout << myMap["Health Pack"] << '\n';
    myMap["Health Pack"] -= 20;
    cout << myMap["Health Pack"] << '\n';

[Ganado]

I don't see anything obvious that let's you look up the keys themselves without exposing an iterator in some way. The for-each loop you already have is the cleanest way to avoid directly using an iterator. Why is it a requirement to not use an iterator?

map.find() returns an iterator to the element, or map.end() if not found.

What if i just want to print the key "Health Pack" and not the value associated with it?

Don't print "i.second"? Sorry if that's terse.

[Ch1156]

Well if i want to tell the player what it is rhey picked up, I like to just use the container value, also there may be instances where I want to print an item out on screen to tell rhe player what they've used, and I dont want or need to print the entire contents of the container. I could have swore there was a way, but maybe I'm misremembering. I can't be sure, I only work with vectors so far, but I am trying to expand my knowledge to other stl containers.

[coder777]

To determine whether an item is present you can use the find(...) function of map:

if(myMap.find("Health Pack") != myMap.end())
{
...
}

Note that when you use the operator[] (like so)

cout << myMap["Health Pack"] << '\n';

The entry "Health Pack" and associated data will be created if not already present.

[JLBorges]

#include <iostream>
#include <string>
#include <map>

int main()
{
    const std::map< std::string, int > inventory { { "Health Pack", 50 }, { "9mm Ammo", 100 } /* etc */ } ;

    // print the keys in the map
    // structured binding: https://en.cppreference.com/w/cpp/language/structured_binding
    for( const auto& [ key, value ] : inventory ) std::cout << "key: '" << key << "'\n" ;

    // check if a key is present in the map
    const std::string key_of_interest = "Health Pack" ;
    [[maybe_unused]] const bool found_it = inventory.count(key_of_interest) ; // https://en.cppreference.com/w/cpp/container/map/count
    
    // check if a key is present in the map, and if yes, get its associated mapped data
    const auto iter = inventory.find(key_of_interest) ;
    if( iter != inventory.end() ) // https://en.cppreference.com/w/cpp/container/map/find
    {
        // found it
        std::cout << "key: '" << iter->first << "'  associated data: " << iter->second << '\n' ;
    }

    else std::cout << "key: '" << key_of_interest << "' is not present\n" ;
}

http://coliru.stacked-crooked.com/a/0de4aa03a7eb38bb