Tuesday, May 29, 2012

array.contains(obj) in JavaScript


What is the most concise and efficient way to find out if a JavaScript array contains an obj?



This is the only way I know to do it:




contains(a, obj) {
for (var i = 0; i < a.length; i++) {
if (a[i] === obj) {
return true;
}
}
return false;
}



Is there a better and more concise way to accomplish this?



This is very closely related to Stack Overflow question Best way to find an item in a JavaScript Array? which addresses finding objects in an array using indexOf .


Source: Tips4all

14 comments:

  1. Modern browsers have Array#indexOf, which does exactly that; this is in the new(ish) ECMAScript 5th edition specification, but it has been in several browsers for years. Older browsers can be supported using the code listed in the "compatibility" section at the bottom of that page.

    jQuery has a utility function for this:

    $.inArray(value, array)


    It returns the index of a value in an array. It returns -1 if the array does not contain the value.

    jQuery has several useful utility functions.

    An excellent JavaScript utility library is underscore.js:


    _.include (which uses indexOf internally if passed a JavaScript array).


    Some other frameworks:


    Dojo Toolkit: dojo.indexOf(array, value, [fromIndex, findLast]) documentation. Dojo has a lot of utility functions, see http://api.dojotoolkit.org.
    Prototype: array.indexOf(value) documentation
    MooTools: array.indexOf(value) documentation
    MochiKit: findValue(array, value) documentation
    MS Ajax: array.indexOf(value) documentation
    Ext: array.indexOf(value, [from]) documentation


    Notice how some frameworks implement this as a function. While other frameworks add the function to the array prototype.

    In coffeescript, the in operator is the equivalent of contains:

    a = [1, 2, 3, 4]
    alert(2 in a)

    ReplyDelete
  2. Update: As @orip mentions in comments, the linked benchmark was done in 2008, so results may not be relevant for modern browsers. However, you probably need this to support non-modern browsers anyway and they probably haven't been updated since. Always test for yourself.

    As others have said, the iteration through the array is probably the best way, but it has been proven that a decreasing while loop is the fastest way to iterate in JavaScript. So you may want to rewrite your code as follows:

    function contains(a, obj) {
    var i = a.length;
    while (i--) {
    if (a[i] === obj) {
    return true;
    }
    }
    return false;
    }


    Of course, you may as well extend Array prototype:

    Array.prototype.contains = function(obj) {
    var i = this.length;
    while (i--) {
    if (this[i] === obj) {
    return true;
    }
    }
    return false;
    }


    And now you can simply use the following:

    alert([1, 2, 3].contains(2)); // => true
    alert([1, 2, 3].contains('2')); // => false

    ReplyDelete
  3. Here's a Javascript 1.6 compatible implementation of Array.indexOf:

    if (!Array.indexOf)
    {
    Array.indexOf = [].indexOf ?
    function (arr, obj, from) { return arr.indexOf(obj, from); }:
    function (arr, obj, from) { // (for IE6)
    var l = arr.length,
    i = from ? parseInt( (1*from) + (from<0 ? l:0), 10) : 0;
    i = i<0 ? 0 : i;
    for (; i<l; i++) {
    if (i in arr && arr[i] === obj) { return i; }
    }
    return -1;
    };
    }

    ReplyDelete
  4. indexOf maybe, but it's a "JavaScript extension to the ECMA-262 standard; as such it may not be present in other implementations of the standard."

    Example:

    [1, 2, 3].indexOf(1) => 0
    ["foo", "bar", "baz"].indexOf("bar") => 1
    [1, 2, 3].indexOf(4) => -1


    AFAICS Microsoft does not offer some kind of alternative to this, but you can add similar functionality to arrays in Internet Explorer (and other browsers that don't support indexOf) if you want to, as a quick Google search reveals (for example, this one).

    ReplyDelete
  5. Extending the JavaScript Array object is a really bad idea because you introduce new properties (your custom methods) into for-in loops which can break existing scripts. A few years ago the authors of the Prototype library had to re-engineer their library implementation to remove just this kind of thing.

    If you don't need to worry about compatibility with other JavaScript running on your page, go for it, otherwise, I'd recommend the more awkward, but safer free-standing function solution.

    ReplyDelete
  6. Thinking out of the box for a second, if you are in making this call many many times, it is more efficient to use an associative array to do lookups using a hash function.

    ReplyDelete
  7. If you are using JavaScript 1.6 or later (Firefox 1.5 or later) you can use Array.indexOf. Otherwise, I think you are going to end up with something similar to your original code.

    ReplyDelete
  8. If you are checking repeatedly for existence of an object in an array you should maybe look into


    Keeping the array sorted at all times by doing insertion sort in your array (put new objects in on the right place)
    Make updating objects as remove+sorted insert operation and
    Use a binary search lookup in your contains(a, obj).

    ReplyDelete
  9. Here's how Prototype does it:

    /**
    * Array#indexOf(item[, offset = 0]) -> Number
    * - item (?): A value that may or may not be in the array.
    * - offset (Number): The number of initial items to skip before beginning the
    * search.
    *
    * Returns the position of the first occurrence of `item` within the array &mdash; or
    * `-1` if `item` doesn't exist in the array.
    **/
    function indexOf(item, i) {
    i || (i = 0);
    var length = this.length;
    if (i < 0) i = length + i;
    for (; i < length; i++)
    if (this[i] === item) return i;
    return -1;
    }


    Also see here for how they hook it up.

    ReplyDelete
  10. Literally:

    (using Firefox v3.6, with for-in caveats as previously noted
    (HOWEVER the use below might endorse for-in for this very purpose! That is, enumerating array elements that ACTUALLY exist via a property index (HOWEVER, in particular, the array length property is NOT enumerated in the for-in property list!).).)

    (Drag & drop the following complete URI's for immediate mode browser testing.)

    javascript:

    function ObjInRA(ra){var has=false; for(i in ra){has=true; break;} return has;}

    function check(ra){
    return ['There is ',ObjInRA(ra)?'an':'NO',' object in [',ra,'].'].join('')
    }
    alert([
    check([{}]), check([]), check([,2,3]),
    check(['']), '\t (a null string)', check([,,,])
    ].join('\n'));


    which displays:

    There is an object in [[object Object]].
    There is NO object in [].
    There is an object in [,2,3].
    There is an object in [].
    (a null string)
    There is NO object in [,,].


    Wrinkles: if looking for a "specific" object consider:

    javascript: alert({}!={}); alert({}!=={});


    and thus:

    javascript:
    obj={prop:"value"}; ra1=[obj]; ra2=[{prop:"value"}];
    alert(ra1[0]==obj); alert(ra2[0]==obj);


    Often ra2 is considered to "contain" obj as the literal entity {prop:"value"}.

    A very coarse, rudimentary, naive (as in code needs qualification enhancing) solution:

    javascript:
    obj={prop:"value"}; ra2=[{prop:"value"}];
    alert(
    ra2 . toSource() . indexOf( obj.toSource().match(/^.(.*).$/)[1] ) != -1 ?
    'found' :
    'missing' );


    See ref: Searching for objects in JavaScript arrays.

    ReplyDelete
  11. Hmmm... what about

    Array.prototype.contains = function(x){
    var retVal = -1;
    //x is a primitive type
    if(["string","number"].indexOf(typeof x)>=0 ){ retVal = this.indexOf(x);}
    //x is a function
    else if(typeof x =="function") for(var ix in this){
    if((this[ix]+"")==(x+"")) retVal = ix;
    }
    //x is an object...
    else {
    var sx=JSON.stringify(x);
    for(var ix in this){
    if(typeof this[ix] =="object" && JSON.stringify(this[ix])==sx) retVal = ix;
    }
    }
    //Return False if -1 else number if numeric otherwise string
    return (retVal === -1)?false : ( isNaN(+retVal) ? retVal : +retVal);
    }


    I know it's not the best way to go, but since there is no native IComparable way to interact between objects, I guess this is as close as you can get to compare two entities in an array. Also, extending Array object might not be a wise thing to do sometimes it's ok (if you are aware of it and the trade-off)

    ReplyDelete
  12. Haha! I think I have the best version by far!

    b is the value, a is the array

    It returns true or false

    function(a,b){return!!~a.indexOf(b)}

    ReplyDelete
  13. While array.indexOf(x)!=-1 is the most concise way to do this (and has been supported by non-IE browsers for over decade...), it is not O(1), but rather O(N), which is terrible. If your array will not be changing, you can convert your array to a hashtable, then do table[x]!==undefined or ===undefined:

    Array.prototype.toTable = function() {
    var t = {};
    this.forEach(function(x){t[x]=true});
    return t;
    }


    Demo:

    var toRemove = [2,4].toTable();
    [1,2,3,4,5].filter(function(x){return toRemove[x]===undefined})


    (Unfortunately, while you can create an Array.prototype.contains to "freeze" an array and store a hashtable in this._cache in two lines, this would give wrong results if you chose to edit your array later. Javascript has insufficient hooks to let you keep this state, unlike python for example.)

    ReplyDelete
  14. Just another option

    // usage: if ( ['a','b','c','d'].contains('b') ) { ... }
    Array.prototype.contains = function(value){
    for (var key in this)
    if (this[key] === value) return true;
    return false;
    }

    ReplyDelete