0

Q:

arr1[]={1,1,1,2,5,5,6,6,6,6,8,7,9}

Ans:

values[]={1,2,5,6,7,9}

Q:

arr1[]={1,1,1,2,5,5,6,6,6,6,8,7,9,101,1502,1502,1,9}

Ans:

values[]={1,2,5,6,7,9,101,1502}

here is what i tried but not working

   for(int i=0;i<(index-1);i++) { 
       if(data[i].age != data[i+1].age) { 
           c=new list; 
           c->value=data[i].age; 
           c->next=NULL; clas++; 
           if(age_head==NULL) { 
                p=c; age_head=c; 
           } 
           for(c=age_head;c!=NULL,c->next!=NULL;p=c,c=c->next) { 
               if(data[i].age!=c->value) 
                   found=false; 
               else 
                   found=true; 
           } 
           if((age_head!=NULL)&& (found=false)) { 
               p->next=c; c->next=NULL; 
           }
       }
   }
7
  • What do you suggest ? Did you try something ?
    – Cedric H.
    Sep 1, 2010 at 8:27
  • If this is homework, please tag it accordingly. Note that we don't do your homework for you - make some effort, show how far you got and where you are stuck, then we are happy to help you :-) Sep 1, 2010 at 8:30
  • i tried n its not a home work Sep 1, 2010 at 8:33
  • here is wat i tried but not wrkng for(int i=0;i<(index-1);i++) { if(data[i].age != data[i+1].age) { c=new list; c->value=data[i].age; c->next=NULL; clas++; if(age_head==NULL) { p=c; age_head=c; } for(c=age_head;c!=NULL,c->next!=NULL;p=c,c=c->next) { if(data[i].age!=c->value) found=false; else found=true; } if((age_head!=NULL)&& (found=false)) { p->next=c; c->next=NULL; } Sep 1, 2010 at 8:33
  • @peter dude its part ov ma office work n its been like 3 years since i wrote a cpp code so dats y i m a bit rusty on ds Sep 1, 2010 at 8:35

8 Answers 8

5

This is not the most efficient, but it has some values:

  1. It uses STL objects
  2. It uses a cool little known template trick for knowing at compile time the size of your C-like arrays

...

int a[] = {1,1,1,2,5,5,6,6,6,6,8,7,9} ;
int b[] = {1,1,1,2,5,5,6,6,6,6,8,7,9,101,1502,1502,1,9} ;

// function setting the set values
template<size_t size>
void findDistinctValues(std::set<int> & p_values, int (&p_array)[size])
{
    // Code modified after Jacob's excellent comment
    p_values.clear() ;
    p_values.insert(p_array, p_array + size) ;

}

void foo()
{
    std::set<int> values ;

    findDistinctValues(values, a) ;
    // values now contain {1, 2, 5, 6, 7, 8, 9}

    findDistinctValues(values, b) ;
    // values now contain {1, 2, 5, 6, 7, 8, 9, 101, 1502}
}

Another version could return the set, instead of taking it by reference. It would then be:

int a[] = {1,1,1,2,5,5,6,6,6,6,8,7,9} ;
int b[] = {1,1,1,2,5,5,6,6,6,6,8,7,9,101,1502,1502,1,9} ;

// function returning the set
template<size_t size>
std::set<int> findDistinctValues(int (&p_array)[size])
{
    // Code modified after Jacob's excellent comment
    return std::set<int>(p_array, p_array + size) ;
}

void foo()
{
    std::set<int> valuesOne = findDistinctValues(a) ;
    // valuesOne now contain {1, 2, 5, 6, 7, 8, 9}

    std::set<int> valuesTwo = findDistinctValues(b) ;
    // valuesTwo now contain {1, 2, 5, 6, 7, 8, 9, 101, 1502}
}
3
  • Since you're clearing p_values anyway, why not just construct a new set from the p_array and assign it to p_values instead? Like this: p_values = std::set<int>( p_array, p_array + size ); Not sure if that shows up right, don't know how to do code in comments.
    – Jacob
    Sep 1, 2010 at 9:13
  • @Cedric H: I've learned it from Microsoft's example for strcpy_s, which is quite great (look at the C++ overload): msdn.microsoft.com/en-us/library/td1esda9.aspx
    – paercebal
    Sep 1, 2010 at 11:23
  • @Jacob: You're SO right. I was too concentrated on the template to remember I should use the iterator constructor and insertion functions for the set object. I modified the code to take account of your comment.
    – paercebal
    Sep 1, 2010 at 11:38
4

The first thing I spot in your code is

if((age_head!=NULL)&& (found=false)) {

you use assignment (=) instead of equality (==). The expression should be

if((age_head!=NULL)&& (found==false)) {

Then, in this loop

       for(c=age_head;c!=NULL,c->next!=NULL;p=c,c=c->next) { 

you are looking for a value in the list. However, in its current form, when the loop terminates, found will show whether the last element in the list equals to c->value. You need to check for found in the loop condition (and you need to AND the expressions instead of listing them separated by comma!):

       for(c=age_head, found = false; !found && c!=NULL && c->next!=NULL; ...) { 

The result of the comma operator is the result of the last subexpression inside - this is definitely not what you want. Moreover, with comma all subexpressions are evaluated, which results in dereferencing a null pointer if c == NULL - whereas the && operator is evaluated lazily, thus c->next!=NULL is evaluated only if c != NULL.

The next thing is that you need to search for the value in the list before you add it to the list! Also note that you are trying to check for two different things: that the actual data element is different from the next one, and that its value is not yet added to the list. The second condition is stronger - it will always work, while the first only works if the input data is ordered. So you can omit the first check altogether. The result of all the above, plus some more simplifications and clarifications, is

for(int i=0;i<index;i++) { 
   for(list* c=age_head, found=false; !found&&c&&c->next; p=c,c=c->next) { 
       if(data[i].age==c->value) 
           found=true; 
   } 
   if(!found) { 
       list* newc=new list;
       newc->value=data[i].age; 
       newc->next=NULL;
       clas++;
       if(age_head==NULL) {
           p=newc; age_head=newc;
       } else {
           p->next=newc; newc->next=NULL;
       }
   }
}

I still don't guarantee that your linked list handling logic is right though :-) In its current form, your code is hard to understand, because the different logical steps are not separated. With a bit of refactoring, the code could look a lot clearer, e.g.

for(int i=0;i<index;i++) { 
   if(!foundInList(data[i].age)) {
       addToList(data[i].age);
   }
}

Of course the simplest and most efficient would be using STL containers/algorithms instead, as shown in other answers. But I think there is much more educational value in improving your first attempt :-)

1
  • if((age_head!=NULL)&& (found==false)) { done but still not wrkng sumthngs wrong Sep 1, 2010 at 8:42
2

If the output need not to be sorted, you can use a Hashtable.

E.g. something like this:

#include <boost/foreach.hpp>
#define foreach BOOST_FOREACH
#include <boost/unordered_set.hpp>
#include <vector>
using namespace std;
using namespace boost;

int main() {
  int arr1[]={1,1,1,2,5,5,6,6,6,6,8,7,9};
  size_t n = sizeof(arr1)/sizeof(int);
  unordered_set<int> h;
  for (size_t i = 0; i < n; ++i)
    h.insert(arr1[i]);
  vector<int> values;
  foreach(int a, h)
    values.push_back(a);
  return 0;
}

The runtime is then in O(n).

An alternative to that is sorting the array and then to eliminate neighboring identical elements (advantage only STL is needed). But then the runtime is in O(n log n):

#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int arr1[]={1,1,1,2,5,5,6,6,6,6,8,7,9};
  size_t n = sizeof(arr1)/sizeof(int);

  sort(arr1, arr1+n);
  int *end = unique(arr1, arr1+n);

  vector<int> values(arr1, end);

  return 0;
}
2

Easily done using STL.

int array[] = { 1, 1, 2, 2, 1, 3, 3, 4, 5, 4, 4, 1, 1, 2 };
int nElements = sizeof(array)/sizeof(array[0]);
std::sort(&array[0], &array[nElements]);
int newSize = std::unique(&array[0], &array[nElements]) - &array[0];
2
  • or instead of &array[0], &array[nElements] you can say array, array + nElements. Sep 1, 2010 at 9:08
  • std::unique does not return the new size of the array, it returns the end address ... Sep 1, 2010 at 9:15
0

first you need to sort the array and than do something like this:

for(int i = 0; i < size -1; i++)
{
     if(array[i]!=array[i+1])
       unique++;

       // store it wherever you want to.
       stored.push(array[i]);
}
1
  • i dunn wanna coun values i wanna store dem Sep 1, 2010 at 8:40
0
#include <vector>
#include <algorithm>
#include <iostream>

int
main ()
{
  int array[] = { 1, 1, 2, 2, 1, 3, 3, 4, 5, 4, 4, 1, 1, 2 };
  std::vector < int >values;
  values.push_back (array[0]);
  for (int i = 1; i < sizeof (array) / sizeof (int); ++i)
    {
      std::vector < int >::iterator it =
        std::find (values.begin (), values.end (), array[i]);
      if (it == values.end ())
        values.push_back (array[i]);
    }

  std::cout << "Result:" << std::endl;
  for (int i = 0; i < values.size (); i++)
    std::cout << values[i] << std::endl;
}
1
  • Note that the runtime of this is in O(n^2), i.e. the runtime of the program grows quadratically with the size of the array. Using (at least) sort + unique is in O(n log n) and is less code. Sep 1, 2010 at 14:58
0

This seems to be a duplicate of Removing duplicates in an array while preserving the order in C++ While the wording of the question is different, the result is the same.

1
  • Which is in itself a duplicate... hm, I don't get the duplicate mechanism on stackoverflow ;) Sep 1, 2010 at 11:20
0

Based on above ideas/codes, I am able to accomplish my job on finding distinct values in C++ array. Thanks every one who replied on this thread.

#include <set>
#include <iostream>
using namespace std;
// function setting the set values
template<size_t size>
void findDistinctValues(std::set<int> & p_values,int (&p_array)[size])
{
    // Code modified after Jacob's excellent comment
    p_values.clear() ;
    p_values.insert(p_array, p_array + size) ;

}

void findDistinctValues2( int arr[],int size)
{
  std::set<int> values_1 ;
  std::set<int>::iterator it_1;
  values_1.clear();
  values_1.insert(arr,arr+size);
  for (it_1=values_1.begin(); it_1!=values_1.end(); ++it_1)
    std::cout << ' ' << *it_1<<endl;

}

int main()
{
  int arr[] = {1,6100,4,94,93,-6,2,4,4,5,5,2500,5,4,5,2,3,6,1,15,16,0,0,99,0,0,34,99,6100,2500};
  std::set<int> values ;
  std::set<int>::iterator it;

  int arr_size = sizeof(arr)/sizeof(int); 
  printf("Total no of array variables: %d\n",arr_size);
  printf("Output from findDistinctValues (function 1)\n ");
  findDistinctValues(values, arr) ;
  for (it=values.begin(); it!=values.end(); ++it)
    std::cout << ' ' << *it<<endl;
  std::cout<<endl;    
  std::cout<<values.size()<<endl; //find the size of distict values

  printf("Output from findDistinctValues (function 2) \n "); 
  findDistinctValues2(arr,arr_size);

  getchar();
  return 0;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.