Is there a shorter way to determine if a given element is in an array?

In summary: If you want a container that enables faster lookups, you need to look at something like a hash map.If you want a container that enables faster lookups, you need to look at something like a hash map.
  • #1
Eclair_de_XII
1,083
91
TL;DR Summary
I am primarily a Python user. I am trying to learn C++ because of a superficial fascination with speed and job prospects. Currently, I am experimenting with C++. I am trying to find a short algorithm to find out if a given element is in a list. I'm not able to figure out one as simple as Python's built-in algorithm. Is there one?
C++:
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main(void) {
    vector <int> v = {0, 5, 9, 3, 2, 1};
    bool nine_exists = false;
    for (int i: v){
        if (i == 9) {
            nine_exists = true;
            break;
        }
    }
    string message = nine_exists ? "No nines found" : "At least one nine found.";
    cout << message << endl;
}

Python:
v = [0, 5, 9, 3, 2, 1]
message = ("At least one nine found" if 9 in v else "No nines found.")
print(message)
 
Technology news on Phys.org
  • #2
Depends on your list. If it’s sorted then a binary search could be applied. On an unsorted list then you must search each element.

You could check Rosettacode.org for some C++ examples of searching a list. They may not be the best examples but can give you some insight on how to do it.
 
  • #3
Let's assume that there is no ordering applied. Are you saying that no easier way exists in C++, other than to declare a Boolean variable, and go through a for-loop in order to determine if a given element exists in an array?
 
  • #4
Yes, how do you think python does it?

I’ve done some tricks where I create a single string from the list and use the string functions to search if the element is present.

As an example, you could make a list of days and concat them into a String like “Monday,Tuesday,Wednesday,Thursday,Friday” and do a search to see if the day you have is in the list using a string function then there’s no need to do a for loop search scheme.

https://cplusplus.com/reference/string/string/find/

Theres the STD framework iterations that could be used as well:

http://www.java2s.com/Tutorial/Cpp/0340__list/Findelementinalist.htm

Im not a c++ programmer but did some programming in it years ago. My main language for the past 25 years was Java, and a smattering of Python.
 
  • #5
Eclair_de_XII said:
Are you saying that no easier way exists in C++, other than to declare a Boolean variable, and go through a for-loop in order to determine if a given element exists in an array?
You are using a C++ vector, for which there is already a built-in function to find an element, std::find. If you look at the source code for that built-in function, I think you will find that what you describe is indeed what it is doing.

If you want a container that enables faster lookups, you need to look at something like a hash map.
 
  • Like
Likes FactChecker
  • #6
PeterDonis said:
If you want a container that enables faster lookups, you need to look at something like a hash map.

I don't want anything like that. I am just looking for a way to determine if an element exists in an array while doing as little typing as possible. I am fairly certain that Python has spoiled me in this respect. Anyway, the code below is closer to what I'm looking for. But I dislike that there is a need to type in "v.begin()", and "v.end" in the arguments of the "find" function.

C++:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void) {
    vector <int> v = {0, 5, 9, 3, 2, 1};
    auto result = find(v.begin(), v.end(), 9);
    cout << (result == v.end()) << endl;
}
 
  • #7
Eclair_de_XII said:
I don't want anything like that. I am just looking for a way to determine if an element exists in an array while doing as little typing as possible.
By choosing an array (or vector) as your data structure, you are choosing to have to potentially look at every element in the array in order to determine if a particular element is in it. Python's built-in list has the same property.

If you don't mind that but just don't like to have to type more verbose code, I think you're better off sticking with Python. C++ is many things, but "not verbose" is not one of them. :wink:
 
  • Like
Likes Vanadium 50, pbuk, FactChecker and 1 other person
  • #9
PeterDonis said:
By choosing an array (or vector) as your data structure, you are choosing to have to potentially look at every element in the array in order to determine if a particular element is in it. Python's built-in list has the same property.

I am aware of this possibility. But one of the main concerns I had with C++ is that if I wanted to do a simple task, such as finding out whether or not an element is in a list, I don't care exactly how either C++ or I have to do it. But if I have to explicitly specify how it is done, then it is a potential deal-breaker for me due to my sheer, possibly unforgivable laziness as an amateur coder. I'd prefer it if a method for what I want to do already exists; I admit that I don't trust myself to write algorithms more efficient than those of the professionals.

jedishrfu said:
Thank you. It's a bit overwhelming how many ways there are to do the one simple task in C++. I get decision paralysis just thinking about it. My figurative OCD is better put at ease when a singular method exists, and is named. I understand that each method may have its own strengths and weakness, when compared to its fellows; this is understandable, given that coders likely want to optimize their code in order to emphasize one of the best aspects of C++. But obsessing over the specifics of how a task is done is not something currently within my interest.
 
  • #10
Eclair_de_XII said:
I am just looking for a way to determine if an element exists in an array while doing as little typing as possible. I am fairly certain that Python has spoiled me in this respect.
That is a very poor reason to pick a particular algorithm. In any case, most C++ programming environments will suggest valid completions of what you type.
 
  • #11
Eclair_de_XII said:
Are you saying that no easier way exists in C++, other than to declare a Boolean variable, and go through a for-loop in order to determine if a given element exists in an array?
https://en.cppreference.com/w/cpp/algorithm/find
See example of usage further down that page.

Using C++20 or later there also a ranges version so you don't have to write begin/end:
https://en.cppreference.com/w/cpp/algorithm/ranges/find

All the algorithms works with general containers that provide iterator access (including plain old arrays), so you your code will look the same if you, say, swap to use list or deque instead of vector.
 
  • #12
Eclair_de_XII said:
I don't want anything like that. I am just looking for a way to determine if an element exists in an array while doing as little typing as possible. I am fairly certain that Python has spoiled me in this respect.
Yes. In many ways, Python is a higher-level programming language than C and languages such as C++ that are derived from it. However, the C++ STL (standard template library) goes quite a way beyond the capabilities of C, with, for example, a number of container classes.

Eclair_de_XII said:
But one of the main concerns I had with C++ is that if I wanted to do a simple task, such as finding out whether or not an element is in a list, I don't care exactly how either C++ or I have to do it.
Which means that you don't really care about performance and program speed, which conflicts somewhat with your "superficial fascination" with speed.

Eclair_de_XII said:
But if I have to explicitly specify how it is done, then it is a potential deal-breaker for me due to my sheer, possibly unforgivable laziness as an amateur coder.
Are you so lazy as to not be curious why finding an element in a sorted list is so much faster than if the list is unsorted, and the code has to iterate over, on average, half the items in the list? If so, then you should probably quit your study of C++ now.
 
  • Like
Likes Eclair_de_XII
  • #13
Eclair_de_XII said:
But obsessing over the specifics of how a task is done is not something currently within my interest.
Then you don't have what it takes to be a C++ programmer.

But don't worry, there are many more jobs for Python programmers than C++ programmers and C++ is only potentially faster than Python when you obsess over the specifics of how a task is done.
 
  • Like
Likes Eclair_de_XII and Mark44
  • #14
There are whole books on this subject. e.g. Knuth. I beleiev it is Voluje III.

This is a classic example why there is more to programming than learning the syntax of Language X, then Language Y, etc, With the right data structure, this is trivial - the data struvture itself will tell you what you want to know.
 
  • #15
Eclair_de_XII said:
I'd prefer it if a method for what I want to do already exists
And you have already been pointed to one: std::find.
 
  • Like
Likes Vanadium 50 and pbuk
  • #16
pbuk said:
Then you don't have what it takes to be a C++ programmer.
Mark44 said:
Are you so lazy as to not be curious why finding an element in a sorted list is so much faster than if the list is unsorted, and the code has to iterate over, on average, half the items in the list? If so, then you should probably quit your study of C++ now.
Thank you both. I will take your respective bits of advice to heart.
 

Similar threads

  • Programming and Computer Science
Replies
12
Views
1K
  • Programming and Computer Science
7
Replies
235
Views
10K
  • Programming and Computer Science
Replies
22
Views
2K
  • Programming and Computer Science
Replies
23
Views
1K
  • Programming and Computer Science
Replies
12
Views
1K
  • Programming and Computer Science
Replies
3
Views
782
  • Programming and Computer Science
Replies
8
Views
1K
  • Programming and Computer Science
Replies
5
Views
2K
  • Programming and Computer Science
Replies
10
Views
1K
  • Programming and Computer Science
Replies
20
Views
1K
Back
Top