C ++ checks how many elements in a string are in a vector

Question

I have a large vector with 24,000 elements, for example:

(1,1,1,1,3,3,3,3,3,3,5,5,5,...etc) 

and I want to check how many identical elements are in the line, for example: 4-6-3..etc I use this code:

 static int counter=1; vector<int>numbers; for(int n=0;n<numbers.size()-1;n++) { if(numbers[n]==numbers[n+1]) { counter++; } else if(numbers[n]!=numbers[n+1]) { cout<<counter<<endl; counter=1; } } 

is there any algorithm that does the same thing faster;

Answer 1

@rhalbersma basically gave you the correct answer. In addition, if you want to rewrite your algorithm in a more standard way:

 #include <algorithm> #include <vector> #include <iterator> #include <functional> #include <iostream> int main() { std::vector<int> v { 1, 1, 2, 3, 3, 5, 5, 5 }; // or whatever... auto i = begin(v); while (i != end(v)) { auto j = adjacent_find(i, end(v), std::not_equal_to<int>()); if (j == end(v)) { std::cout << distance(i, j); break; } std::cout << distance(i, j) + 1 << std::endl; i = next(j); } } 

Here is a living example .

Also, when the vector is sorted, this will give you the best at best complexity:

 #include <algorithm> #include <vector> #include <iterator> #include <iostream> int main() { std::vector<int> v { 1, 1, 2, 3, 3, 5, 5, 5 }; // must be sorted... auto i = begin(v); while (i != end(v)) { auto ub = upper_bound(i, end(v), *i); std::cout << distance(i, ub) << std::endl; i = ub; } } 

Here is a living example .

Answer 2

Your algorithm is O(N) in time, and it seems to me very optimal, since you need to visit each unique element for comparison. You can still shave off a few cycles here and there, for example. eliminating the condition inside else() or including some compiler options, but algorithmically you are in good shape.

If the input has already been sorted , you can do a series of binary searches . This would give you O(N lg N) worse complexity, but the average case could be significantly lower depending on the average length of equal sequences of elements.

BTW, as @AndyProwl shows in its answer: The standard library is really amazing to make even this low-level algorithmic material. The adjacent_find and upper_bound have well-documented complexities, and the iterator conventions will protect you from the edges that are present in your own code. Once you learn this dictionary, you can easily use them in your own programs (and when ranges come in C ++, we hope that they will also be easier to compile them).

Answer 3

There is some litle optimization that can give you a few ms:

 int size = numbers.size()-1; static int counter=1; static int *num1 = &numbers[0]; static int *num2 = &numbers[1]; for(int n=0;n<size;n++) { if(*num1==*num2) counter++; else { cout << counter << "\n"; counter=1; } num1++; num2++; } cout<<counter<<endl; //Caution, this line is missing in your code!! 

Basicaly:

• Avoid accessing the vector by id: numbers [n] means the computer must multiply n * sizeof (int) and add this result to the numbers. Faster to use the pointer and increase it, it means just add.