C++ :: Fastest Comparison Algorithm Based On A Predefined Container?
Sep 3, 2014
Suppose you have defined a container of elements and you want do define a comparison function between elements based on the ordering of the elements in that container. What algorithm for the comparison would be the most efficient?
My current idea is to simply iterate from the beginning of the container, and whichever of the two elements is found first is the lesser (assuming the second is not the same as the first). It seems kind of naïve though. Any better performing algorithm? This is what I have so far:
Would perhaps forcing the container to have a random access iterator, like vector, and then writing a specialized comparison function based on that perform even faster? Or perhaps force the container to be a map to integers, and compare the elements by comparing the integer mapped values?
Names are std::string no more than 3 characters in length. What built in container or boost container is fastest at finding a name (Key) in it's container.
Finding a name. At the name will be a value double.
I need the most efficient at finding and finding/updating the value. Forget out inserts and deletes.
So I have an insertion sort function implemented that sorts through an array, but I'm having a problem showing the correct number of comparisons to work.
Each time I'm checking a value with another, the counter should update.
For instance, having an array of 10 elements going from 10-1 should give 45 comparisons, but I'm getting 54 comparisons.
void insertionSort(int a[], int& comparisons, const int& numOfElements) { int j, value; for (int i = 1; i < numOfElements; i++) { value = a[i]; for (j = i - 1; j >= 0 && a[j] > value; j--)
How do you find, when you first introduced with say some of the STL container, function or algorithms, what are its requirements? I mean,
1. what operators object should have for specific container? 2. what function args and type it should return for a algo? 3. when extending some container like with custom allocator, char_traits...and what not, what methods should be overridden? What work should they do?
Is it possible to create a class that stores (non-const) references to some objects and enables users direct access by using range-based for loops on them?
Code: class container { public: void add(int& value); void remove(int& value); ... }; int main() { container c; for (auto& value:c) { // `value' should be accessible as type `int&' instead of being a pointer, `std::reference_wrapper<int>' or something like that } }
now using sba or Set Based Algorithm I have to pair it out and towards the end find the size of the resulting set
#include <iostream> #include <set> int main()
[Code]......
this is the code just reads the edges that's 3... that is when we input the code. But what if its in a file? how do I read from there and show the paired count and the time taken?
Also I have the file that works and reads any txt file..but how do i get the code from it?
[URL]
this is the file..you have to run it as ./edgecount for it to work
dynamically allocated arrays. int (*ttt)[2][10]; If I'm not mistaken this declares a pointer (that's all). This pointer has an intrinsic shape that makes it easier to access row, column without doing my own math to calculate the offset.
ttt = malloc(2 * 10 * sizeof(int));
So I should be able to access elements like this: ttt[i][j].
ttt[i][j] = 123;
But the compiler says: error C2440: '=' : cannot convert from 'int' to 'int [10]'...how to go about accessing a monolithic block of allocated memory using 2 or more dimensions, using some sort of casting to a known shaped array if possible. As opposed to doing i * cols + j type stuff.
which adds two rational numbers in following representation : rNumber := s*(n/d)* 2^e struct rNumber{ _byte_t s; // sign (do not consider for this question) uint n; //numerator uint d;// denominator short e;//exponent }
If the exponents of both numbers are not equal, then they have to be made equal in order to add them. This can be made in 4 ways : increase or decrease the n or d of both numbers.
But if we decrease the denominator of a number (a.d =1) by shifting it for example 1 bit to the right, we get 0 which leads to INFINITY for the fraction. In another case decreasing the numerator would lead the n to be 0 which meanse the whole fraction is then 0.
According to this, in worst case, all 4 cases has to be checked for the right result.
So far the UNDERFLOW of n or d is considered. If we try to increase the value of n or d, then OVERFLOW may also occur.
The very first, intuitive solution would be iteratively increase/decrease one of the terms and to check if the change leads to ZERO or INFINITY.
I'm currently building a new data structures that will be used in monte carlo generators (and so will be constructed several million times) and I'm wondering what's the best way (computer-speed-wise) to pass the data to the constructor. I am currently doing it using references and passing arrays as pointers like this:
Code: class particle{ public: particle(double *ar,int &id):IDup(id){ for (int i=0;i<5;++i) Pup[i]=ar[i]; } int IDup; double Pup[5]; };
I'm assuming that since using references has no need to create a temporary memory slot it's more efficient .....
As for the arrays: is there a way for me to pass them as reference as well? (not using c++11), I'm using arrays instead of vectors as much as I can because I assume that vectors, being more advanced data structures, would take more time to create.
I'll process the raw content of a stream which obviously will be loaded one chunk at a time into an buffer.I need to check if every chunk content is x00 filled. If it is, I'll increase the blank chunks counter of 1.On your personal opinion, which is the fastest an less cycles consuming manner to achieve such result?
I was wondering this: is it possible to make an instant XOR of all the buffer content to check if it does return 0 ?the only way is it to cycle through all the bytes and compare each one of them with 0?
I have to compare data in excel and csv based on the file name and update the status of file from CSV into excel file by creating a new column status on weekly basis.
I have a small piece of code that used the set::insert function on a set of myClass. For that, I need to overload the < and > operators, which I have, but I still get a huge error saying it can't compare.
set<MyClass> mySet; MyClass myClass
All the class information gets filled in. Then, I try to insert... mySet.insert(myClass);
bool operator<(MyClass &lhs, MyClass &rhs) { return lhs.name < rhs.name; //name is a string }
The error says ...stl_function.h:230:22: error: no match for 'operator<' in '__x < __y' MyFile.h:80:6: note: candidate is bool operator<(MyClass&, MyClass&)
I'm making a simple game and I'm having trouble creating boundaries for the players movements. The map is a 2D vector. When I compare the vector with the players current position sometimes I get an error during run. When the error isn't occurring the behavior of the boundaries is bizarre. The error tells me that the vector is out of range.
Here is the where the map is created. It's within its own class constructor.
vector< vector<char> > map_parts; map_parts.resize(25); for ( int i = 0; i < 25; i++ ) {
I made a program that allows the user to enter information of credit cards on an array of size 5, however I need to allow the user to compare the five credit cards with each other and I am having problems with this particular part. I made my bool operator functions for the operator< and the operator> but how to make the user be able to select which cards he wants to compare and how to compare them. My code is the following:
#include <iostream> #include <fstream> #include <string> using namespace std; const int SIZE = 5; enum OPCIONES {CARGAR=1, ABONAR, NADA};
This is some code that simulates files and directories the same way an operating system does so. I commented out every std::string occurrence because I got the :
terminate called after throwing an instance of 'std::length_error' what(): basic_string::_S_create
string eg("azertyFTW"); if(eg[one of the letters contained in this string] == 'c') { cout << "eg has the letter c in it"; } else { cout << "not this time :("; }
bool simpleQuestion::checkAnswer(string guess) const { for (int i=0;i<qAnswer.length();i++) if (qAnswer==guess) return true; else return false; }
This is my code and what im trying to accomplish here is making the comparison of the two strings (qAnswer & guess) case insensitive. I know i need to loop through each character of each string and for each character i can use toupper and every char in each string will become uppercase and therefore case insensitive. However, im not sure how to go about this; if any technique used to loop through each character of the string and how to use to upper.
I think I am doing it right but im getting a couple of errors that i cant fix ...
#include <iostream> using namespace std; int main(){ int x [8] [8], r, c; for(c = 0; c <= 8; c++){ cout << " Enter a number from 1 to 7 " << endl;
[Code] .....
these are the errors :
assignment15_meem.cpp: In function âint main()â: assignment15_meem.cpp:7: error: no match for âoperator>>â in âstd::cin >> x[c]â assignment15_meem.cpp:10: error: ISO C++ forbids comparison between pointer and integer
I am trying to count the number of comparisons for each of the following sorting algorithms, Selection, Insertion, Bubble, Merge, and Quick sort. This is using an array of numbers that are sorted, reversed, and randomly arranged.
I currently increment the "number of comparison" variable before every conditional statement that compares two numbers and am getting the following results:
Number of Items in Array = 100 Selection: random = 5049; reverse = 5049; sorted = 5049; Insertion: random = 2640; reverse = 5049; sorted = 99; Bubble: random = 9207; reverse = 9900; sorted = 99; Merge: random = 1221; revere = 988; sorted = 1028; Quick: random = 690; revere = 587; sorted = 636;
