std :: find против получения шаблона из вектора - PullRequest
Новая
       31

std :: find против получения шаблона из вектора

3 голосов
/ 12 октября 2010

Я часто использую векторы в своем программировании, и, как правило, для обхода вектора для существующего значения я использую std :: find как в: 

std::vector<int> foo;
std::vector<int>::iterator pos( std::find( foo.begin(), foo.end(), bar );

Это настоящийскука.Итак, я пошел к получению шаблона из std :: vector , чтобы обеспечить метод find : 

template<class T>
class foovector : public std::vector<T>
{
public:
    typename std::vector<T>::iterator find( const T& value )
    {
        return std::find( this->begin(), this->end(), value );
    }
};

И теперь я могу найти более естественный поиск: 

foovector<int> foo;
foovector<int>::iterator pos( foo.find( bar ) );

Мой вопрос заключается в том, что это кажется таким естественным и очевидным расширением вектора, так почему он не является частью STL или даже boost ?Я чувствую, что мне здесь не хватает тайных знаний.

Ответы [ 6 ]

6 голосов
/ 12 октября 2010

  1. Наследование от контейнеров STL не считается хорошей идеей - у них нет виртуальных деструкторов, так как они не были предназначены для этого.

  2. не в том, что он доступен для поиска - для этого есть и другие контейнеры.

  3. Я подозреваю, что большинство людей просто не находят код, который вы заменяете, этот надоедливый.

5 голосов
/ 12 октября 2010

Как насчет того, что вы делаете, чего хотите, и все же не идете по сомнительному пути наследования от std :: vector

определить автономную функцию 

template <typename T>
typename std::vector<T>::const_iterator find( const std::vector<T>& v, const T& value )
 {
     return std::find( v.begin(), v.end(), value );
 }

вы можете поместить это в пространство имен std (что, технически говоря, запрещено) или в другое пространство имен (с компромиссом, который не будет найден ADL, поэтому вам нужно будет его квалифицировать). НТН

P.S. кстати, вы можете обобщить это для всех контейнеров 

template <typename Container, typename T>
typename Container::const_iterator find( const Container& c, const T& value )
{
     return std::find( c.begin(), c.end(), value );
}
5 голосов
/ 12 октября 2010

Проект STL заключается в предоставлении коллекций, имеющих узкий интерфейс, который реализует только те методы, которые нельзя реализовать без доступа к закрытым членам.

Затем они добавляют шаблонные функции на итераторах (не на коллекции).Это означает, что многие из этих функций работают хорошо, даже если вы создаете свою собственную коллекцию, если вы предоставляете стандартные итераторы.Вам не нужно наследование, чтобы сделать эту работу - так что вещи могут оставаться отдельными.

2 голосов
/ 12 октября 2010

Возможно, потому что вектор - это самый простой тип контейнера, и есть лучшие (ассоциативные) контейнеры для использования, если поиск является приоритетом.

Vector имеет O (1) производительность при поиске по индексу, но если вы используете алгоритм поиска, вы теряете все это преимущество.

1 голос
/ 12 октября 2010

На самом деле, я обернул большинство свободных функций, определенных в <algorithm>, версиями, которые принимают контейнеры / диапазоны вместо итераторов.Это не только намного безопаснее (я могу добавить простые проверки, убедиться, что диапазон действителен и т. Д.), Но и гораздо удобнее.

Для вашего случая общий способ сделать это: 

template <typename Container>
typename Container::iterator find(Container& c,
                                  typename Container::value_type const& v)
{
  return std::find(c.begin(), c.end(), v);
}

template <typename Container>
typename Container::const_iterator find(Container const& c,
                                        typename Container::value_type const& v)
{
  return std::find(c.begin(), c.end(), v);
}

Это можно использовать с любым STL-совместимым контейнером.

Конечно, было бы неплохо адаптировать это через Concept для использования функции-члена find, еслиимеется ...

1 голос
/ 12 октября 2010

Потому что, если вам обычно требуется много находок, вы должны использовать набор или карту (или хешированную версию любого из них).Мало того, что это легче написать, но они имеют O(log n) сложность поиска, тогда как несортированный вектор O(n).

С картой: 

map<stuff> m
m[bar] // returns a reference to the element with key bar.

Набор похож.*

...